4.1 GRAPH THEORY 1151. Start at s, as before, and travel along edges A, E, C until we reach vertex u.
- Now travel along the subgraph (edges J, K, L, I), returning to u.
- Finish the trip along the edges D, E, F, G, H, reaching vertex f.
This method will work in general. We may have to repeat the "remove the traveled
edges and travel the subgraph" step several times (since we could have gotten stuck
back at the starting point without traversing all of the edges of the subgraph), but since
the graph is finite, eventually we will finish. _
- 1.4 If you aren't convinced about the argument above, try the algorithm on the fol
lowing multigraph. Then you will understand the algorithm.
4.1. 5 A directed graph (also called digraph) is a graph (or multigraph) where each
edge is given a direction (usually indicated by an arrow). In other words, a directed
graph is like a network of one-way streets. Find necessary and sufficient conditions
for a directed graph or multi graph to have an Eulerian path.
The "dual" of an Eulerian path is a Hamiltonian path (named after a 1 9th-century
Irish mathematician), a path that visits each vertex exactly once. If the path is closed,
it is called a Hamiltonian cycle. While Eulerian paths possess a "complete theory ,"
very little is known about Hamiltonian paths. At present, the necessary and sufficient
conditions for Hamiltonian paths are unknown. This is unfortunate, because many
practical problems involve Hamiltonian paths. For example, suppose we want to seat
people around a table in such a way that no one sits next to someone that she dislikes.
Then we can make a graph where the people are vertices and we connect edges be
tween friends. A Hamilton path, if one exists, gives us a seating plan. Many problems
involving scheduling and optimization of network paths can be recast as searches for
Hamiltonian paths.
The following is a rather weak statement that gives a sufficient condition for
Hamiltonian paths.
4.1.6 Let G be a graph (not a multigraph) with v vertices. If each vertex has degree at
least v /2, then G has a Hamiltonian cycle.