Applications of graph theory

Planar graphs

A graph G is said to be planar if it can be represented on a plane in such a fashion that the vertices are all distinct points, the edges are simple curves, and no two edges meet one another except at their terminals. For example, K₄, the complete graph on four vertices, is planar, as Figure 4A shows.

Two graphs are said to be homeomorphic if both can be obtained from the same graph by subdivisions of edges. For example, the graphs in Figure 4A and Figure 4B are homeomorphic.

The K_m,n graph is a graph for which the vertex set can be divided into two subsets, one with m vertices and the other with n vertices. Any two vertices of the same subset are nonadjacent, whereas any two vertices of different subsets are adjacent. The Polish mathematician Kazimierz Kuratowski in 1930 proved the following famous theorem:

A necessary and sufficient condition for a graph G to be planar is that it does not contain a subgraph homeomorphic to either K₅ or K_3,3 shown in Figure 5.

An elementary contraction of a graph G is a transformation of G to a new graph G₁, such that two adjacent vertices u and υ of G are replaced by a new vertex w in G₁ and w is adjacent in G₁ to all vertices to which either u or υ is adjacent in G. A graph G* is said to be a contraction of G if G* can be obtained from G by a sequence of elementary contractions. The following is another characterization of a planar graph due to the German mathematician K. Wagner in 1937.

A graph is planar if and only if it is not contractible to K₅ or K_3,3.

The four-colour map problem

For more than a century the solution of the four-colour map problem eluded every analyst who attempted it. The problem may have attracted the attention of Möbius, but the first written reference to it seems to be a letter from one Francis Guthrie to his brother, a student of Augustus De Morgan, in 1852.

The problem concerns planar maps—that is, subdivisions of the plane into nonoverlapping regions bounded by simple closed curves. In geographical maps it has been observed empirically, in as many special cases as have been tried, that, at most, four colours are needed in order to colour the regions so that two regions that share a common boundary are always coloured differently, and in certain cases that at least four colours are necessary. (Regions that meet only at a point, such as the states of Colorado and Arizona in the United States, are not considered to have a common boundary). A formalization of this empirical observation constitutes what is called “the four-colour theorem.” The problem is to prove or disprove the assertion that this is the case for every planar map. That three colours will not suffice is easily demonstrated, whereas the sufficiency of five colours was proved in 1890 by the British mathematician P.J. Heawood.

In 1879 A.B. Kempe, an Englishman, proposed a solution of the four-colour problem. Although Heawood showed that Kempe’s argument was flawed, two of its concepts proved fruitful in later investigation. One of these, called unavoidability, correctly states the impossibility of constructing a map in which every one of four configurations is absent (these configurations consist of a region with two neighbours, one with three, one with four, and one with five). The second concept, that of reducibility, takes its name from Kempe’s valid proof that if there is a map that requires at least five colours and that contains a region with four (or three or two) neighbours, then there must be a map requiring five colours for a smaller number of regions. Kempe’s attempt to prove the reducibility of a map containing a region with five neighbours was erroneous, but it was rectified in a proof published in 1976 by Kenneth Appel and Wolfgang Haken of the United States. Their proof attracted some criticism because it necessitated the evaluation of 1,936 distinct cases, each involving as many as 500,000 logical operations. Appel, Haken, and their collaborators devised programs that made it possible for a large digital computer to handle these details. The computer required more than 1,000 hours to perform the task, and the resulting formal proof is several hundred pages long.

Eulerian cycles and the Königsberg bridge problem

A multigraph G consists of a non-empty set V(G) of vertices and a subset E(G) of the set of unordered pairs of distinct elements of V(G) with a frequency f ≥ 1 attached to each pair. If the pair (x₁, x₂) with frequency f belongs to E(G), then vertices x₁ and x₂ are joined by f edges.

An Eulerian cycle of a multigraph G is a closed chain in which each edge appears exactly once. Euler showed that a multigraph possesses an Eulerian cycle if and only if it is connected (apart from isolated points) and the number of vertices of odd degree is either zero or two.

This problem first arose in the following manner. The Pregel River, formed by the confluence of its two branches, runs through the town of Königsberg and flows on either side of the island of Kneiphof. There were seven bridges, as shown in Figure 6A. The townspeople wondered whether it was possible to go for a walk and cross each bridge once and once only. This is equivalent to finding an Eulerian cycle for the multigraph in Figure 6B. Euler showed it to be impossible because there are four vertices of odd order.

Directed graphs

A directed graph G consists of a non-empty set of elements V(G), called vertices, and a subset E(G) of ordered pairs of distinct elements of V(G). Elements (x, y) of E(G) may be called edges, the direction of the edge being from x to y. Both (x, y) and (y, x) may be edges.

A closed path in a directed graph is a sequence of vertices x₀x₁x₂ · · · x_n = x₀, such that (x_i, x_{i + 1}) is a directed edge for i = 0, 1, · · ·, n − 1. To each edge (x, y) of a directed graph G there can be assigned a non-negative weight function f(x, y). The problem then is to find a closed path in G traversing all vertices so that the sum of the weights of all edges in the path is a minimum. This is a typical optimization problem. If the vertices are certain cities, the edges are routes joining cities, and the weights are the lengths of the routes, then this becomes the travelling-salesman problem—that is, can he visit each city without retracing his steps? This problem still remains unsolved except for certain special cases.