In
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
,
graph theory is the study of
graphsIn mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of
verticesIn graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
or 'nodes' and a collection of
edges that connect pairs of vertices. A graph may be
undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be
directed from one vertex to another; see
graph (mathematics)In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
for more detailed definitions and for other variations in the types of graphs that are commonly considered. The graphs studied in graph theory should not be confused with
graphs of functionsIn mathematics, the graph of a function f is the collection of all ordered pairs . In particular, if x is a real number, graph means the graphical representation of this collection, in the form of a curve on a Cartesian plane, together with Cartesian axes, etc. Graphing on a Cartesian plane is...
or other kinds of graphs.
Graphs are one of the prime objects of study in
discrete mathematicsDiscrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
.
Refer to
glossary of graph theoryGraph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
for basic definitions in graph theory.
Applications
Graphs are among the most ubiquitous models of both natural and human-made structures. They can be used to model many types of relations and process dynamics in physical, biological and social systems. Many problems of practical interest can be represented by graphs.
In
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. One practical example: The link structure of a
websiteA website, also written as Web site, web site, or simply site, is a collection of related web pages containing images, videos or other digital assets. A website is hosted on at least one web server, accessible via a network such as the Internet or a private local area network through an Internet...
could be represented by a directed graph. The vertices are the web pages available at the website and a directed edge from page
A to page
B exists if and only if
A contains a link to
B. A similar approach can be taken to problems in travel, biology, computer chip design, and many other fields. The development of
algorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s to handle graphs is therefore of major interest in computer science. There, the transformation of graphs is often formalized and represented by
graph rewrite systemsGraph transformation, or Graph rewriting, concerns the technique of creating a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms....
. They are either directly used or properties of the rewrite systems (e.g. confluence) are studied. Complementary to graph transformation systems focussing on rule-based in-memory manipulation of graphs are
graph databaseA graph database uses graph structures with nodes, edges, and properties to represent and store data. By definition, a graph database is any storage system that provides index-free adjacency. General graph databases that can store any graph are distinct from specialized graph databases such as...
s geared towards
transactionA transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
-safe,
persistentPersistence in computer science refers to the characteristic of state that outlives the process that created it. Without this capability, state would only exist in RAM, and would be lost when this RAM loses power, such as a computer shutdown....
storing and querying of
graph-structured dataIn computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
.
Graph-theoretic methods, in various forms, have proven particularly useful in
linguisticsLinguistics is the scientific study of human language. Linguistics can be broadly broken into three categories or subfields of study: language form, language meaning, and language in context....
, since natural language often lends itself well to discrete structure. Traditionally,
syntaxIn linguistics, syntax is the study of the principles and rules for constructing phrases and sentences in natural languages....
and compositional semantics follow tree-based structures, whose expressive power lies in the
Principle of CompositionalityIn mathematics, semantics, and philosophy of language, the Principle of Compositionality is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them. This principle is also called Frege's Principle,...
, modeled in a hierarchical graph. Within
lexical semanticsLexical semantics is a subfield of linguistic semantics. It is the study of how and what the words of a language denote . Words may either be taken to denote things in the world, or concepts, depending on the particular approach to lexical semantics.The units of meaning in lexical semantics are...
, especially as applied to computers, modeling word meaning is easier when a given word is understood in terms of related words;
semantic networkA semantic network is a network which represents semantic relations among concepts. This is often used as a form of knowledge representation. It is a directed or undirected graph consisting of vertices, which represent concepts, and edges.- History :...
s are therefore important in
computational linguisticsComputational linguistics is an interdisciplinary field dealing with the statistical or rule-based modeling of natural language from a computational perspective....
. Still other methods in phonology (e.g.
Optimality TheoryOptimality theory is a linguistic model proposing that the observed forms of language arise from the interaction between conflicting constraints. OT models grammars as systems that provide mappings from inputs to outputs; typically, the inputs are conceived of as underlying representations, and...
, which uses
lattice graphThe terms lattice graph, mesh graph, or grid graph refer to a number of categories of graphs whose drawing corresponds to some grid/mesh/lattice, i.e., its vertices correspond to the nodes of the mesh and its edges correspond to the ties between the nodes.-Square grid graph:A common type of a...
s) and morphology (e.g. finite-state morphology, using finite-state transducers) are common in the analysis of language as a graph. Indeed, the usefulness of this area of mathematics to linguistics has borne organizations such as
TextGraphs, as well as various 'Net' projects, such as
WordNetWordNet is a lexical database for the English language. It groups English words into sets of synonyms called synsets, provides short, general definitions, and records the various semantic relations between these synonym sets...
,
VerbNetThe VerbNet project maps PropBank verb types to their corresponding Levin classes. It is a lexical resource that incorporates both semantic and syntactic information about its contents...
, and others.
Graph theory is also used to study molecules in
chemistryChemistry is the science of matter, especially its chemical reactions, but also its composition, structure and properties. Chemistry is concerned with atoms and their interactions with other atoms, and particularly with the properties of chemical bonds....
and
physicsPhysics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
. In
condensed matter physicsCondensed matter physics deals with the physical properties of condensed phases of matter. These properties appear when a number of atoms at the supramolecular and macromolecular scale interact strongly and adhere to each other or are otherwise highly concentrated in a system. The most familiar...
, the three dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. For example, Franzblau's shortest-path (SP) rings. In chemistry a graph makes a natural model for a molecule, where vertices represent
atomThe atom is a basic unit of matter that consists of a dense central nucleus surrounded by a cloud of negatively charged electrons. The atomic nucleus contains a mix of positively charged protons and electrically neutral neutrons...
s and edges
bondsA chemical bond is an attraction between atoms that allows the formation of chemical substances that contain two or more atoms. The bond is caused by the electromagnetic force attraction between opposite charges, either between electrons and nuclei, or as the result of a dipole attraction...
. This approach is especially used in computer processing of molecular structures, ranging from
chemical editorsA molecule editor is a computer program for creating and modifying representations of chemical structures.Molecule editors can manipulate chemical structure representations in either two- or three-dimensions. Two-Dimensional editors generate output used as illustrations or for querying chemical...
to database searching. In statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such
systems.
Graph theory is also widely used in
sociologySociology is the study of society. It is a social science—a term with which it is sometimes synonymous—which uses various methods of empirical investigation and critical analysis to develop a body of knowledge about human social activity...
as a way, for example, to
measure actors' prestigeSix Degrees of Kevin Bacon is a trivia game based on the concept of the small world phenomenon and rests on the assumption that any individual involved in the Hollywood, California film industry can be linked through his or her film roles to actor Kevin Bacon within six steps. The name of the game...
or to explore
diffusionMolecular diffusion, often called simply diffusion, is the thermal motion of all particles at temperatures above absolute zero. The rate of this movement is a function of temperature, viscosity of the fluid and the size of the particles...
mechanisms, notably through the use of social network analysis software.
Likewise, graph theory is useful in
biologyBiology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...
and conservation efforts where a vertex can represent regions where certain species exist (or habitats) and the edges represent migration paths, or movement between the regions. This information is important when looking at breeding patterns or tracking the spread of disease, parasites or how changes to the movement can affect other species.
In mathematics, graphs are useful in geometry and certain parts of topology, e.g. Knot Theory. Algebraic graph theory has close links with group theory.
A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example if a graph represents a road network, the weights could represent the length of each road.
A digraph with weighted edges in the context of graph theory is called a network.
Network analysisNetwork theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...
have many practical applications, for example, to model and analyze traffic networks. Applications of network analysis split broadly into three categories:
- First, analysis to determine structural properties of a network, such as the distribution of vertex degrees and the diameter
In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance...
of the graph. A vast number of graph measures exist, and the production of useful ones for various domains remains an active area of research.
- Second, analysis to find a measurable quantity within the network, for example, for a transportation network
A transportation network is a type of directed, weighted graph or network.Transportation networks are used to model the flow of commodity, information, or traffic ....
, the level of vehicular flow within any portion of it.
- Third, analysis of dynamical properties
Sequential dynamical systems are a class of graph dynamical systems. They are discrete dynamical systems which generalize many aspects of for example classical cellular automata, and they provide a framework for studying asynchronous processes over graphs...
of networks.
History
The first text book on graph theory was written by
Denes KonigDénes Kőnig was a Jewish Hungarian mathematician who worked in and wrote the first textbook on the field of graph theory....
, but this book was very hard to understand.
Richard RadoRichard Rado FRS was a Jewish German mathematician. He earned two Ph.D.s: in 1933 from the University of Berlin, and in 1935 from the University of Cambridge. He was interviewed in Berlin by Lord Cherwell for a scholarship given by the chemist Sir Robert Mond which provided financial support to...
said he was unable to understand Konig's proof of
Rado's TheoremIn mathematics, Rado's theorem is a result about harmonic functions, named after Tibor Radó. Informally, it says that any "nice looking" shape without holes can be smoothly deformed into a disk....
. The first readable book was by
Frank HararyFrank Harary was a prolific American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory....
and was enormously popular. This book enabled mathematicians, chemists, electrical engineers and social scientists to talk to each other. He donated all of the proceeds to fund the
Polya PrizeThe Pólya Prize is either of two prizes in the field of mathematics named after Hungarian mathematician George Pólya.*Pólya Prize , a prize awarded by the Society for Industrial and Applied Mathematics...
.
The paper written by
Leonhard EulerLeonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
on the
Seven Bridges of KönigsbergThe Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology....
and published in 1736 is regarded as the first paper in the history of graph theory. This paper, as well as the one written by
VandermondeAlexandre-Théophile Vandermonde was a French musician, mathematician and chemist who worked with Bézout and Lavoisier; his name is now principally associated with determinant theory in mathematics. He was born in Paris, and died there.Vandermonde was a violinist, and became engaged with...
on the
knight problemThe knight's tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from...
, carried on with the
analysis situs initiated by
LeibnizGottfried Wilhelm Leibniz was a German philosopher and mathematician. He wrote in different languages, primarily in Latin , French and German ....
. Euler's formula relating the number of edges, vertices, and faces of a convex polyhedron was studied and generalized by
CauchyBaron Augustin-Louis Cauchy was a French mathematician who was an early pioneer of analysis. He started the project of formulating and proving the theorems of infinitesimal calculus in a rigorous manner, rejecting the heuristic principle of the generality of algebra exploited by earlier authors...
and L'Huillier, and is at the origin of
topologyTopology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
.
More than one century after Euler's paper on the bridges of
KönigsbergKönigsberg was the capital of East Prussia from the Late Middle Ages until 1945 as well as the northernmost and easternmost German city with 286,666 inhabitants . Due to the multicultural society in and around the city, there are several local names for it...
and while
ListingJohann Benedict Listing was a German mathematician.J. B. Listing was born in Frankfurt and died in Göttingen. He first introduced the term "topology", in a famous article published in 1847, although he had used the term in correspondence some years earlier...
introduced topology,
CayleyArthur Cayley F.R.S. was a British mathematician. He helped found the modern British school of pure mathematics....
was led by the study of particular analytical forms arising from
differential calculusIn mathematics, differential calculus is a subfield of calculus concerned with the study of the rates at which quantities change. It is one of the two traditional divisions of calculus, the other being integral calculus....
to study a particular class of graphs, the
treesIn mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
. This study had many implications in theoretical
chemistryChemistry is the science of matter, especially its chemical reactions, but also its composition, structure and properties. Chemistry is concerned with atoms and their interactions with other atoms, and particularly with the properties of chemical bonds....
. The involved techniques mainly concerned the enumeration of graphs having particular properties. Enumerative graph theory then rose from the results of Cayley and the fundamental results published by
PólyaGeorge Pólya was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory...
between 1935 and 1937 and the generalization of these by
De BruijnNicolaas Govert de Bruijn is a Dutch mathematician, affiliated as professor emeritus with the Eindhoven University of Technology. He received his Ph.D. in 1943 from Vrije Universiteit Amsterdam....
in 1959. Cayley linked his results on trees with the contemporary studies of chemical composition. The fusion of the ideas coming from mathematics with those coming from chemistry is at the origin of a part of the standard terminology of graph theory.
In particular, the term "graph" was introduced by
SylvesterJames Joseph Sylvester was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory and combinatorics...
in a paper published in 1878 in
NatureNature, first published on 4 November 1869, is ranked the world's most cited interdisciplinary scientific journal by the Science Edition of the 2010 Journal Citation Reports...
, where he draws an analogy between "quantic invariants" and "co-variants" of algebra and molecular diagrams:
- "[...] Every invariant and co-variant thus becomes expressible by a graph precisely identical with a Kekuléan
Friedrich August Kekule von Stradonitz was a German organic chemist. From the 1850s until his death, Kekule was one of the most prominent chemists in Europe, especially in theoretical chemistry...
diagram or chemicograph. [...] I give a rule for the geometrical multiplication of graphs, i.e. for constructing a graph to the product of in- or co-variants whose separate graphs are given. [...]" (italics as in the original).
One of the most famous and productive problems of graph theory is the four color problem: "Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?" This problem was first posed by
Francis GuthrieFrancis Guthrie was a South African mathematician and botanist who first posed the Four Colour Problem in 1852. At the time, Guthrie was a student of Augustus De Morgan at University College London. He studied under John Lindley, Professor of Botany at the University of London. Guthrie obtained...
in 1852 and its first written record is in a letter of
De MorganAugustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, making its idea rigorous. The crater De Morgan on the Moon is named after him....
addressed to
HamiltonSir William Rowan Hamilton was an Irish physicist, astronomer, and mathematician, who made important contributions to classical mechanics, optics, and algebra. His studies of mechanical and optical systems led him to discover new mathematical concepts and techniques...
the same year. Many incorrect proofs have been proposed, including those by Cayley, Kempe, and others. The study and the generalization of this problem by
TaitPeter Guthrie Tait FRSE was a Scottish mathematical physicist, best known for the seminal energy physics textbook Treatise on Natural Philosophy, which he co-wrote with Kelvin, and his early investigations into knot theory, which contributed to the eventual formation of topology as a mathematical...
,
HeawoodPercy John Heawood was a British mathematician educated at Queen Elizabeth's School, Ipswich, and Exeter College, Oxford....
,
RamseyFrank Plumpton Ramsey was a British mathematician who, in addition to mathematics, made significant and precocious contributions in philosophy and economics before his death at the age of 26...
and
HadwigerHugo Hadwiger was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.-Biography:...
led to the study of the colorings of the graphs embedded on surfaces with arbitrary
genusIn mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. It...
. Tait's reformulation generated a new class of problems, the
factorization problems, particularly studied by
PetersenJulius Peter Christian Petersen was a Danish mathematician.-Biography:Petersen's interests in mathematics were manifold .His famous paper Die Theorie der regulären graphs was a fundamental...
and
KőnigDénes Kőnig was a Jewish Hungarian mathematician who worked in and wrote the first textbook on the field of graph theory....
. The works of Ramsey on colorations and more specially the results obtained by
TuránPaul Turán was a Hungarian mathematician who worked primarily in number theory. He had a long collaboration with fellow Hungarian mathematician Paul Erdős, lasting 46 years and resulting in 28 joint papers.- Life and education :...
in 1941 was at the origin of another branch of graph theory,
extremal graph theoryExtremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth...
.
The four color problem remained unsolved for more than a century. In 1969
Heinrich HeeschHeinrich Heesch was a German mathematician. He was born in Kiel and died in Hanover.In Göttingen he worked on Group theory. In 1933 Heesch witnessed the National Socialist purges among the university staff...
published a method for solving the problem using computers. A computer-aided proof produced in 1976 by
Kenneth AppelKenneth Ira Appel is a mathematician who in 1976, with colleague Wolfgang Haken at the University of Illinois at Urbana-Champaign, solved one of the most famous problems in mathematics, the four-color theorem...
and
Wolfgang HakenWolfgang Haken is a mathematician who specializes in topology, in particular 3-manifolds.In 1976 together with colleague Kenneth Appel at the University of Illinois at Urbana-Champaign, Haken solved one of the most famous problems in mathematics, the four-color theorem...
makes fundamental use of the notion of "discharging" developed by Heesch. The proof involved checking the properties of 1,936 configurations by computer, and was not fully accepted at the time due to its complexity. A simpler proof considering only 633 configurations was given twenty years later by
RobertsonG. Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor at the Ohio State University. He earned his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. According to the criteria of the Erdős Number...
, Seymour, Sanders and
ThomasRobin Thomas is a mathematician working in graph theory at the Georgia Institute of Technology.Thomas received his doctorate in 1985 from Charles University in Prague, Czechoslovakia , under the supervision of Jaroslav Nešetřil...
.
The autonomous development of topology from 1860 and 1930 fertilized graph theory back through the works of
JordanMarie Ennemond Camille Jordan was a French mathematician, known both for his foundational work in group theory and for his influential Cours d'analyse. He was born in Lyon and educated at the École polytechnique...
,
KuratowskiKazimierz Kuratowski was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics.-Biography and studies:...
and
WhitneyHassler Whitney was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, and characteristic classes.-Work:...
. Another important factor of common development of graph theory and topology came from the use of the techniques of modern algebra. The first example of such a use comes from the work of the physicist
Gustav KirchhoffGustav Robert Kirchhoff was a German physicist who contributed to the fundamental understanding of electrical circuits, spectroscopy, and the emission of black-body radiation by heated objects...
, who published in 1845 his
Kirchhoff's circuit lawsKirchhoff's circuit laws are two equalities that deal with the conservation of charge and energy in electrical circuits, and were first described in 1845 by Gustav Kirchhoff...
for calculating the
voltageVoltage, otherwise known as electrical potential difference or electric tension is the difference in electric potential between two points — or the difference in electric potential energy per unit charge between two points...
and
currentElectric current is a flow of electric charge through a medium.This charge is typically carried by moving electrons in a conductor such as wire...
in electric circuits.
The introduction of probabilistic methods in graph theory, especially in the study of
ErdősPaul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and
RényiAlfréd Rényi was a Hungarian mathematician who made contributions in combinatorics, graph theory, number theory but mostly in probability theory.-Life:...
of the asymptotic probability of graph connectivity, gave rise to yet another branch, known as
random graph theoryIn mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
, which has been a fruitful source of graph-theoretic results.
Drawing graphs
Graphs are represented graphically by drawing a dot or circle for every vertex, and drawing an arc between two vertices if they are connected by an edge. If the graph is directed, the direction is indicated by drawing an arrow.
A graph drawing should not be confused with the graph itself (the abstract, non-visual structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout. In practice it is often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.
Graph-theoretic data structures
There are different ways to store graphs in a computer system. The
data structureIn computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
used depends on both the graph structure and the
algorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for sparse graphs as they have smaller memory requirements. Matrix structures on the other hand provide faster access for some applications but can consume huge amounts of memory.
List structures
Incidence listIn graph theory, the incidence list is a variant of the adjacency list that allows for the description of the edges at the cost of additional edges. Instead of storing adjacent vertices, the list stores all of the edges that contain the referencing vertex. Edges are required to have two vertices....
: The edges are represented by an array containing pairs (tuples if directed) of vertices (that the edge connects) and possibly weight and other data. Vertices connected by an edge are said to be
adjacent.
Adjacency listIn graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node...
: Much like the incidence list, each vertex has a list of which vertices it is adjacent to. This causes redundancy in an undirected graph: for example, if vertices A and B are adjacent, A's adjacency list contains B, while B's list contains A. Adjacency queries are faster, at the cost of extra storage space.
Matrix structures
Incidence matrixIn mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related ...
: The graph is represented by a
matrixIn mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
of size |
V | (number of vertices) by |
E| (number of edges) where the entry [vertex, edge] contains the edge's endpoint data (simplest case: 1 - incident, 0 - not incident).
Adjacency matrixIn mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
: This is an
n by
n matrix
A, where
n is the number of vertices in the graph. If there is an edge from a vertex
x to a vertex
y, then the element
is 1 (or in general the number of
xy edges), otherwise it is 0. In computing, this matrix makes it easy to find subgraphs, and to reverse a directed graph.
Laplacian matrixIn the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be...
or "Kirchhoff matrix" or "Admittance matrix" : This is defined as
D −
A, where
D is the diagonal
degree matrixIn the mathematical field of graph theory the degree matrix is a diagonal matrix which contains information about the degree of each vertex. It is used together with the adjacency matrix to construct the Laplacian matrix of a graph.-Definition:...
. It explicitly contains both adjacency information and degree information. (However, there are other, similar matrices that are also called "Laplacian matrices" of a graph.)
Distance matrixIn mathematics, computer science and graph theory, a distance matrix is a matrix containing the distances, taken pairwise, of a set of points...
: A symmetric
n by
n matrix
D, where
n is the number of vertices in the graph. The element
is the length of a shortest path between
x and
y; if there is no such path
= infinity. It can be derived from powers of
A
-
Enumeration
There is a large literature on graphical enumeration: the problem of counting graphs meeting specified conditions. Some of this work is found in Harary and Palmer (1973).
Subgraphs, induced subgraphs, and minors
A common problem, called the
subgraph isomorphism problemIn theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H....
, is finding a fixed graph as a subgraph in a given graph. One reason to be interested in such a question is that many graph properties are
hereditary for subgraphs, which means that a graph has the property if and only if all subgraphs have it too.
Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem.
- Finding the largest complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
is called the clique problemIn computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
(NP-complete).
A similar problem is finding induced subgraphs in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example,
- Finding the largest edgeless induced subgraph, or independent set
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
, called the independent set problem (NP-complete).
Still another such problem, the
minor containment problem, is to find a fixed graph as a minor of a given graph. A
minorIn graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
or
subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. A famous example:
- A graph is planar
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
if it contains as a minor neither the complete bipartite graphIn the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
(See the Three-cottage problem) nor the complete graph 
.
Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their
point-deleted subgraphs, for example:
- The reconstruction conjecture
Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.-Formal statements:...
.
Graph coloring
Many problems have to do with various ways of
coloring graphsIn graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
, for example:
- The four-color theorem
- The strong perfect graph theorem
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
- The Erdős–Faber–Lovász conjecture
In graph theory, the Erdős–Faber–Lovász conjecture is an unsolved problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972...
(unsolved)
- The total coloring conjecture
In graph theory, total coloring is a type of coloring on the vertices and edges of a graph.When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.The...
(unsolved)
- The list coloring conjecture (unsolved)
- The Hadwiger conjecture (graph theory)
In graph theory, the Hadwiger conjecture states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph...
(unsolved).
Route problems
- Hamiltonian path and cycle problems
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph . Both problems are NP-complete...
- Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
- Route inspection problem
In graph theory, a branch of mathematics, the Chinese postman problem , postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a undirected graph. When the graph has an Eulerian circuit , that circuit is an optimal solution.Alan Goldman of...
(also called the "Chinese Postman Problem")
- Seven Bridges of Königsberg
The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology....
- Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
- Steiner tree
The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
- Three-cottage problem
- Traveling salesman problem (NP-hard)
Network flow
There are numerous problems arising especially from applications that have to do with various notions of
flows in networksIn graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
, for example:
Covering problems
Covering problems are specific instances of subgraph-finding problems, and they tend to be closely related to the
clique problemIn computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
or the independent set problem.
- Set cover problem
The set covering problem is a classical question in computer science and complexity theory.It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms...
- Vertex cover problem
Graph classes
Many problems involve characterizing the members of various classes of graphs. Overlapping significantly with other types in this list, this type of problem includes, for instance:
- Enumerating
In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the graph...
the members of a class
- Characterizing a class in terms of forbidden substructures
- Ascertaining relationships among classes (e.g., does one property of graphs imply another)
- Finding efficient algorithms to decide
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
membership in a class
- Finding representations
In mathematics, representation is a very general relationship that expresses similarities between objects. Roughly speaking, a collection Y of mathematical objects may be said to represent another collection X of objects, provided that the properties and relationships existing among the...
for members of a class.
See also
- Gallery of named graphs
Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different...
- Glossary of graph theory
Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
- List of graph theory topics
- Publications in graph theory
Related topics
- Graph property
In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.-Definitions:...
- Algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches...
- Conceptual graph
Conceptual graphs are a formalism for knowledge representation. In the first published paper on CGs, John F. Sowa used them to represent the conceptual schemas used in database systems...
- Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
- Disjoint-set data structure
In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...
- Entitative graph
An entitative graph is an element of the diagrammatic syntax for logic that Charles Sanders Peirce developed under the name of qualitative logic beginning in the 1880's, taking the coverage of the formalism only as far as the propositional or sentential aspects of logic are concerned...
- Existential graph
An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote on graphical logic as early as 1882, and continued to develop the method until his death in 1914.-The graphs:...
- Graph data structure
In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
- Graph algebras
- Graph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
- Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
- Graph database
A graph database uses graph structures with nodes, edges, and properties to represent and store data. By definition, a graph database is any storage system that provides index-free adjacency. General graph databases that can store any graph are distinct from specialized graph databases such as...
- Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
- Graph equation
Graph equations are equations in which the unknowns are graphs. One of the central questions of graph theory concerns the notion of isomorphism. We ask: When are two graphs the same ? The graphs in question may be expressed differently in terms of graph equations.What are the graphs G and H such...
- Graph rewriting
Graph transformation, or Graph rewriting, concerns the technique of creating a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms....
- Graph sandwich problem
In graph theory and computer science, the graph sandwich problem is the study of incomplete models of pairwise relations between objects from a certain collection, and how to complete them.Given a vertex set V, a mandatory edge set E1,...
- Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...
- Logical graph
A logical graph is a special type of diagramatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic....
- Loop
In graph theory, a loop is an edge that connects a vertex to itself. A simple graph contains no loops....
- Network theory
Network theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...
- Null graph
In the mathematical field of graph theory, the null graph may refer either to the order zero graph, or alternatively, to any edgeless graph .-Order zero graph:...
- Pebble motion problems
The pebble motion problems, or pebble motion on graphs, are a set of related problems in graph theory dealing with the movement of multiple objects from vertex to vertex in a graph with a constraint on the number of pebbles that can occupy a vertex at any time...
- Percolation
In physics, chemistry and materials science, percolation concerns the movement and filtering of fluids through porous materials...
- Perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
- Quantum graph
In mathematics and physics, a quantum graph is a linear, network-shaped structure of vertices connected by bonds with a differential or pseudo-differential operator acting on functions defined on the bonds. Such systems were first studied by Pauling as models of free electrons in organic...
- Random regular graphs
- Spectral graph theory
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....
- Strongly regular graph
In graph theory, a discipline within mathematics, a strongly regular graph is defined as follows. Let G = be a regular graph with v vertices and degree k...
s
- Symmetric graph
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
s
- Tree data structure
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
Algorithms
- Bellman-Ford algorithm
The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem....
- Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
- Ford-Fulkerson algorithm
The Ford–Fulkerson Method computes the maximum flow in a flow network. It was published in 1956...
- Kruskal's algorithm
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
- Nearest neighbour algorithm
The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. In it, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited...
- Prim's algorithm
In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized...
- Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
- Breadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
Subareas
- Algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches...
- Geometric graph theory
In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs...
- Extremal graph theory
Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth...
- Probabilistic graph theory
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
- Topological graph theory
In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs....
Related areas of mathematics
- Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
- Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
- Knot theory
In topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life in shoelaces and rope, a mathematician's knot differs in that the ends are joined together so that it cannot be undone. In precise mathematical language, a knot is an embedding of a...
- Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
Online textbooks
Other resources