The study of networks - systems of points joined by lines. A famous unsolved problem is the travelling salesman problem: given a number of towns and the roads between them, what is the shortest route that enables a salesman to visit every one? This exemplifies the way problems in graph theory are not amenable to the calculus, and defy even the largest computers when the number of possible routes becomes vast. A more conceptual side concerns graphs of various types, and asks if there is a route visiting each vertex exactly once. Colouring questions ask if each edge and/or each vertex can be coloured with a given set of paints so that no two adjacent edges or vertices have the same colour. The four-colour theorem can be formulated as a question about graphs. It asks: given a map of n countries on the sphere and four colours, can each country be so coloured that no two with a common boundary have the same colour? On replacing each country by its capital, and joining capitals by a line if and only if the countries have a common border, it becomes a question about the corresponding graph.
"Graphs" in this context are not to be confused with "graphs of functions" and other kinds of graphs.History
The paper written by Leonhard Euler on the Seven Bridges of Königsberg and published in 1736 is regarded as the first paper in the history of graph theory.
More than one century after Euler's paper on the bridges of Königsberg and while Listing introduced topology, Cayley was led by the study of particular analytical forms arising from differential calculus to study a particular class of graphs, the trees.
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?". The study and the generalization of this problem by Tait, Heawood, Ramsey and Hadwiger has in particular led to the study of the colorings of the graphs embedded on surfaces with arbitrary genus. The works of Ramsey on colorations and more specially the results obtained by Turán in 1941 is at the origin of another branch of graph theory, the extremal graph theory.
The autonomous development of topology from 1860 and 1930 fertilized graph theory back through the works of Jordan, Kuratowski and Whitney.
The introduction of probabilistic methods in graph theory, specially in the study of Erdös and Rényi of the asymptotic probability of graph connexity is at the origin of yet another branch, known as random graph theory.
Drawing graphs
Graphs are represented graphically by drawing a dot for every vertex, and drawing an arc between two vertices if they are connected by an edge.
A graph drawing should not be confused with the graph itself (the abstract, non-graphical structure) as there are several ways to structure the graph drawing.
Graph-theoretic data structures
There are different ways to store graphs in a computer system. The data structure used depends on both the graph structure and the algorithm used for manipulating the graph.
Matrix structures
Incidence matrix - The graph is represented by a matrix of E (edges) by V (vertices), where [edge, vertex] contains the edge's data (simplest case: 1 - connected, 0 - not connected).Problems in graph theory
Problems about subgraphs
A common problem, called subgraph isomorphism problem, is finding subgraphs in a given graph. Many graph properties are hereditary, which means that a graph has a property if and only if all subgraphs have it too. For example a graph is planar if it contains neither the complete bipartite graph K3,3 (See Three cottage problem) nor the complete graph K5.
Finding the largest complete graph is called the clique problem (NP-complete) Finding the largest independent set is called the independent set problem (NP-complete)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:
Reconstruction conjectureGraph coloring
Many problems have to do with various ways of coloring graphs, for example:
The four-color theorem The strong perfect graph theorem The Erdős-Faber-Lovász conjecture (unsolved) The total coloring conjecture (unsolved) The list coloring conjecture (unsolved)Route problems
Hamiltonian path and cycle problems Seven Bridges of Königsberg Minimum spanning tree Steiner tree Shortest path problem Route inspection problem (also called the "Chinese Postman Problem") Traveling salesman problem (NP-Complete)Network flow
There are numerous problems arising especially from applications that have to do with various notions of flows in networks, for example:
Max flow min cut theoremVisibility graph problems
Museum guard problemCovering problems
Covering problems are specific instances of subgraph-finding problems, and they tend to be closely related to the clique problem or the independent set problem.
Set cover problem Vertex cover problemApplications
Applications of graph theory are primarily, but not exclusively, concerned with labeled graphs and various specializations of these.
Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be represented by graphs. The link structure of a website 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 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. A digraph with weighted edges in the context of graph theory is called a network.
Networks have many uses in the practical side of graph theory, network analysis (for example, to model and analyze traffic networks).
Many applications of graph theory exist in the form of network analysis.
Graph theory is also used to study molecules in chemistry and physics.
Related topics
| Algebraic graph theory Conceptual graph Data structure Disjoint-set data structure Entitative graph | Existential graph Graph data structure Graph coloring Graph drawing | Logical graph Loop Null graph Spectral graph theory Strongly regular graphs Tree data structure |
Algorithms
| Bellman-Ford algorithm Dijkstra's algorithm Ford-Fulkerson algorithm | Kruskal's algorithm Nearest neighbour algorithm Prim's algorithm |
Subareas
| Algebraic graph theory Geometric graph theory Extremal graph theory | Metric graph theory Probabilistic graph theory Topological graph theory |
Related areas of mathematics
| Combinatorics Group theory | Knot theory Ramsey theory |
Prominent graph theorists
| Berge, Claude Bollobás, Béla Dirac, Gabriel Andrew Erdős, Paul Faudree, Ralph Graham, Ronald | Harary, Frank König, Denes Lovász, László Nešetřil, Jaroslav Rényi, Alfréd Robertson, Neil | Seymour, Paul Szemerédi, Endre Thomas, Robin Thomassen, Carsten Turán, Pál Tutte, W.T. |
User Comments Add a comment…