Figure 1
Geometric Structures: Session IV
Traversability Problems in Graphs and Tress
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk
Many important problems in operations research require that the edges or vertices of a graph (which may or may not have weights on the edges) be visited once and only once. The problem where the tour starts and ends at the same vertex is usually more important for applications than the case where one is allowed to start and end the tour at a different vertex.
Edge tours:
Garbage collection, mail delivery, salt or sand spreading, snow plowing, parking meter enforcement.
Vertex tours:
Component insertion in chip design, sewer inspections, school and camp bus routes, group taxi rides, parcel post and package delivery, meals on wheels delivery, servicing pay phone booths or ATM machines, meter reading.
The important result for traversing the edges in an undirected graph is due to Leonard Euler.
A graph G which is connected has an Eulerian circuit (Euler circuit) if it has an edge tour that starts and ends at the same vertex and traverses each edge once and only once.
Theorem: A connected graph has an Eulerian circuit if and only if it is even-valent.
The graphs which come up in practical situations will rarely have Eulerian circuits so one needs to extend this circle of ideas to the case of general graphs and to consider the case where there are weights on the edges of the graph. A useful special case of this more general case is where the edges all have equal cost or weight. (The weights can represent time, distance, or some other "cost.")
Chinese Postman Problem:
Given a connected graph with weights, find a tour of the edges that starts and ends at the same vertex, traverses each edge at least once, and for which the sum of the weights of the tour is as small as possible.
The important idea is to be able to "duplicate" (deadhead) edges which already exist in the graph with the goal of obtaining a graph which has an Eulerian circuit, and where the total number of duplicated edges is minimized.
This problem is solvable in polynomial time using a complex algorithm developed by Jack Edmonds and Ellis Johnson. The algorithm involves finding a minimum weight matching (a disjoint collection of edges) in a general graph. However, small problems can be solved by trial and error methods. To solve such problems it is useful to have the shortest paths in the graph between vertices which are odd-valent. To find the shortest cost path between two vertices in a graph one can use Dijkstra's algorithm. This is the algorithm which is often used in conjunction with the hardware and software that is increasingly available in automobiles and which displays shortest time routes for driving between two locations.
It turns out that the Chinese Postman Problem for undirected graphs with weights and directed graphs (there is a line with an arrow on the edges) can be solved in polynomial time. Rather surprisingly, if the graph has some directed edges and some undirected edges (such graphs are called mixed graphs), the problem becomes NP-complete.
The terminology of vertex traversal problems honors the Irish mathematician William Rowan Hamilton, though the British "amateur" mathematician Thomas Kirkland studied this circle of ideas earlier.
A connected graph (with at least 3 vertices) has a Hamiltonian circuit (HC) if it has a tour which visits each vertex once and only once and returns to its start vertex. Note that the notation for writing down a circuit shows the same vertex at the start and end of a tour. This is not considered "revisiting" a vertex.
Figure 1 shows an example of a bipartite graph which has no Hamiltonian circuit.
A bipartite graph is one where the vertex set can be divided into two disjoint sets X and Y where any edges present only join vertices in X to Y and never vertices in X or Y to themselves. Bipartite graphs can also be thought of as graphs where the vertices can be colored with two colors so that vertices with the same color are not joined by an edge. When the size of the two sets X and Y in a bipartition of the vertices of a graph have different sizes, then the graph can not have a HC. This follows from the fact that in a bipartite graph the vertices of a HC would have to alternate between the sets X and Y and when the sets X and Y have different cardinality, this is not possible.
The theory of Hamiltonian circuits is very different from that of Eulerian circuits. There is a simple test to tell if a graph has an Eulerian circuit. No such test exists to check if a general graph has a HC. In fact, for many classes of graphs it is known to be NP-complete to determine if the graph has a HC.
The weighted version of the HC problem carried out for the complete graph is very important for applications. It is known as the TSP or Traveling Salesman Problem. Find the minimum cost HC in a weighted complete graph. It is a well known NP-complete problem.
Trees
A very important class of planar graphs and bipartite graphs are the trees. A tree is a connected graph which has no circuits. Trees are important in chemistry as models of molecules, essential for the study of data structures in computer science and for studying the idea of how close to each other drugs, species, genes, or proteins are in biology (phylogenetic trees).
Figure 2 shows two different drawings of a pair of isomorphic trees. One can see the symmetry of this particular tree from both diagrams but they give very different visual appearances. The top diagram has all its vertices on the same circle.
Some important results about trees are:
a. There is a unique (simple) path between every pair of vertices in a tree.
b. If a tree has at least two vertices, it has at least two 1-valent vertices.
c. If two vertices of a tree which are not already joined by an edge are joined by an edge, one gets a unique circuit.
d. If a tree T has |V| vertices and |E| edges, then |V| = |E| + 1.
The statement (d) can be proved using Mathematical Induction by making use of statement (b). (Mathematical Induction says that if one has a family of statements S(n) defined on the positive integers, and one can show that S(1) holds and that if S(k) holds then S(k+1) holds, then S(n) holds for all positive integers n.) Statement (b) can be used by using ideas involving graph distance. If v and w are two vertices in a connected graph, the distance from v to w is the smallest number of edges in any path from v to w.
In Figure 3 the distance between vertex 1 and vertices 2, 6, 7, and 8 are, respectively, 1, 2, 2, and 3.
The eccentricity of a vertex v is the farthest any vertex can be from v. The eccentricity of vertex 1 (Figure 3) is 3 and the eccentricity of vertex 4 is 2. The eccentricity of vertex 2 is 4. The vertices with minimal eccentricity are called central vertices. The intuition is that if one needs to provide service at a vertex of a graph, then a good place to provide the service (hospital, firehouse, etc.) would be at a central vertex. The diameter of a graph is the largest distance that any two vertices can be apart. The diameter of the graph in Figure 3 is 4. The vertices 2 and 8 cannot be joined by a path of length less than 4. In a tree, the vertices of largest eccentricity must be 1-valent.