Graph theory
Graph theory is the branch of mathematics that examines the properties of graphs.
A graph is a set of dots, called vertices or nodes, connected by links, called edges or arcs. Depending on the applications, edges may or may not have a direction; edges joining a vertex to itself may or may not be allowed, and vertices and/or edges may be assigned weights, i.e. numbers. If the edges have a direction associated with them (indicated by an arrow in the graphical representation) we have a directed graph.
Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be formulated as questions about certain graphs. For example directed graphs are used to represent finite state machines. The development of algorithms to compute certain properties of graphs is therefore of major interest in computer science.
Definitions of Graphs and Digraphs
The basic definitions in graph theory vary in the literature. Here are the conventions used in this encyclopedia.
A directed graph (also called digraph or quiver) consists of
- a set V of vertices, and
- a set E of edges, and
- maps s, t : E → V, where s(e) is the source and t(e) is the target of the directed edge e.
An undirected graph (or graph for short) is given by
- a set V of vertices,
- a set E of edges,
- a function w : E → P(V) which associates to each edge a two- or one-element subset of V, interpreted as the endpoints of the edge.
A loop in a graph or digraph is an edge e in E whose endpoints are the same.
A digraph or graph is called simple if there are no loops and there is at most one edge between any pair of vertices.
In a weighted graph or digraph, an additional function E → R associates a value with each edge; such graphs arise in optimal route problems such as the traveling salesman problem.
Glossary of basic graph theory concepts
The example graph pictured to the right is a simple graph with vertex set V = {1, 2, 3, 4, 5, 6} and edge set E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} (with the map w being the identity).
An edge connects two vertices; these two vertices are said to be incident to the edge. The valency (or degree) of a vertex is the number of edges incident to it, with loops being counted twice. In the example graph vertices 1 and 3 have a valency of 2, vertices 2,4 and 5 have a valency of 3 and vertex 6 has a valency of 1. If E is finite, then the total valency of the vertices is equal to twice the number of edges. In a digraph, we distinguish the out degree (=the number of edges leaving a vertex) and the in degree (=the number of edges entering a vertex). The degree of a vertex is equal to the sum of the out degree and the in degree.
Two vertices are considered adjacent if an edge exists between them. In the above graph, vertices 1 and 2 are adjacent, but vertices 2 and 4 are not. The set of neighbors for a vertex consists of all vertices adjacent to it. In the example graph, vertex 1 has two neighbors: vertex 2 and node 5. For a simple graph, the number of neighbors that a vertex has coincides with its valency.
A path is a sequence of vertices in that each vertex is adjacent to both the preceding and succeding vertex. A path is considered simple if none of the nodes in the path are repeated. The length of a path is the number of edges that the path uses, counting multiple edges multiple times.
In the example graph, (1, 2, 5, 1, 2, 3) is a path with length 5, and (5, 2, 1) is a simple path of length 2.
If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be connected.
A cycle (or circuit) is a path that begins and ends with the same vertex and has length at least two. In the example graph, (1, 2, 3, 4, 5, 2, 1) is a cycle of length 6. A simple cycle is a cycle in which the beginning node only appears once more, as the ending node and other nodes appear only once. In the above graph (1, 5, 2, 1) is a simple cycle. Simple cycles of length 1 are loops. A graph is called acyclic if it contains no simple cycles.
The girth of a graph is the length of the shortest simple cycle in the graph. The girth of an acyclic graph is defined to be infinity.
A tree is a connected acyclic simple graph. Sometimes, one vertex of the tree is distinguished, and called the root. Trees are commonly used as data structures in computer science (see tree data structure).
A forest is a set of trees; equivalently, a forest is any acyclic graph.
A subgraph of the graph G is a graph whose vertex set is a subset of the vertex set of G, whose edge set is a subset of the edge set of G, and such that the map w is the restriction of the map from G.
A spanning subgraph of a graph G is a subgraph with the same vertex set as G. A spanning tree is a spanning subgraph that is a tree. Every graph has a spanning tree.
A complete graph is a simple graph in which every node is adjacent to every other node. The example graph is not complete. The complete graph on n vertices is often denoted by Kn. It has n(n-1)/2 edges (corresponding to all possible choices of pairs of vertices).
A planar graph is one which can be drawn in the plane without any two edges intersecting. The example graph is planar; the complete graph on n vertices, for n> 4, is not planar.
An Eulerian path in a graph is a path that uses each edge precisely once. If such a path exists, the graph is called traversable. An Eulerian cycle is a cycle with uses each edge precisely once. (See Leonhard_Euler's Seven Bridges of Konigsberg problem.) There is a dual to this concept: a Hamiltonian path in a graph is a path that visits each vertex once and only once; and a Hamiltonian cycle is a cycle which visits each vertex once and only once. The example graph does not contain an Eulerian path, but it does contain a Hamiltonian path.
The null graph is the graph whose edge set and vertex set are empty.
An independent set in a graph is a set of pairwise nonadjacent vertices. In the example above, vertices 1,3, and 6 form an independent set and 3,5, and 6 are another independent set.
A clique (pronounced click) in a graph is a set of pairwise adjacent vertices. In the example graph above, vertices 1, 2 and 5 form a clique.
Graph Problems
- Coloring graphs: the four color theorem
- Route problems:
- Minimum spanning tree
- Shortest path problem
- Route inspection problem (aka "Chinese Postman Problem")
- Traveling salesman problem
- Flows:
Important Algorithms
Generalizations
In a hypergraph an edge can connect more than two vertices.
An undirected graph can be seen as a complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs.