05 Cycles, Euler Tours, Hamiltonian Cycles, Traveling Salesman Problem

In our exploration of graph theory, we now turn to the concept of cycles, closed paths within graphs. Cycles are not merely closed walks; they represent fundamental structural elements with significant implications in graph properties and algorithmic problems. We will examine two specific types of cycles that are of particular interest: Euler tours and Hamilton cycles. These cycles, while both traversing a graph in a closed loop, differ fundamentally in whether they traverse edges or vertices exactly once.

Euler Tours (1.5.1)

An Euler tour (named after Leonhard Euler) is a closed walk that traverses every edge of a graph exactly once. A graph that contains an Euler tour is called Eulerian. The quest for Euler tours originated from the famous Königsberg bridge problem, which Euler solved in 1736, marking the inception of graph theory.

A fundamental property of Eulerian graphs is that every vertex must have an even degree. This is because, in an Euler tour, each time we enter a vertex, we must also leave it via a different edge. Thus, for every edge entering a vertex, there must be a corresponding edge leaving it, implying that the degree of each vertex must be even. Remarkably, for connected graphs, this condition is also sufficient for the existence of an Euler tour.

Definition 1.30: An Euler tour in a graph $G = (V, E)$ is a closed walk (cycle) that traverses each edge of the graph exactly once. A graph that contains an Euler tour is called Eulerian.

Theorem 1.31:

(a) A connected graph $G = (V, E)$ is Eulerian if and only if the degree of every vertex is even.

(b) In a connected Eulerian graph, an Euler tour can be found in $O (∣ E ∣)$ time.

Proof of (a) (Necessity): As argued above, if a graph $G$ has an Euler tour, then for every vertex $v \in V$ , every time the Euler tour enters $v$ , it must also leave $v$ . Thus, every vertex must have an even degree.

Proof of (a) (Sufficiency) and (b) (Algorithm): We will prove sufficiency and provide an algorithm to find an Euler tour simultaneously. The algorithm, Eulertour(G, vstart), starts at an arbitrary vertex $v_{s t a r t}$ and explores a path, greedily choosing any available edge at each vertex and removing it from the graph as it is traversed.

Algorithm: Eulertour(G, vstart)
Input: Connected graph G = (V, E) with even degrees, starting vertex vstart
Output: Euler tour W
 
// Fast runner (Schneller Läufer)
W = RandomtourG(vstart)
 
// Slow runner (Langsamer Läufer)
v_langsam = Startknoten of W
 
while v_langsam is not the last vertex in W:
    v = Nachfolger of v_langsam in W
    if NG(v) != Ø: // NG(v) are edges from v in G
        W' = RandomtourG(v)
        // Augment W = W1 + v + W2 with tour W' = v -> ... -> v
        W = W1 + W' + W2  // Concatenate tours
    v_langsam = Nachfolger of v_langsam in W
 
return W

The subroutine RandomtourG(vstart) generates a path starting from vstart by randomly choosing and traversing edges until no further edges are available from the current vertex. It removes each traversed edge from the graph to avoid reusing edges.

Algorithm: RandomtourG(vstart)
Input: Graph G, starting vertex vstart
Output: Path W (which is a cycle in Eulerian graphs)
 
v = vstart
W = [v] // Initialize walk W with start vertex
 
while NG(v) is not empty: // While there are edges incident to v
    Choose vnext from NG(v) arbitrarily
    Append vnext to tour W
    e = {v, vnext}
    Remove e from G // Mark edge as used
    v = vnext
 
return W

The algorithm maintains two “runners”: a fast runner S which explores and constructs cycles, and a slow runner L which traverses the Euler tour being built. The slow runner only advances when the fast runner gets stuck at a vertex with no unused edges. The algorithm leverages the property that in an Eulerian graph, every vertex has an even degree, ensuring that any path started by RandomtourG will eventually return to its starting vertex, forming a cycle. By repeatedly finding and splicing in cycles, the algorithm constructs an Euler tour that covers all edges. The time complexity of this algorithm is $O (∣ E ∣)$ , as each edge is traversed and processed a constant number of times.

Hamilton Cycles (1.5.2)

A Hamilton cycle (named after William Rowan Hamilton) is a cycle that visits every vertex of a graph exactly once. A graph that contains a Hamilton cycle is called Hamiltonian. Unlike Euler tours, there is no simple characterization of Hamiltonian graphs, and determining whether a graph is Hamiltonian is a notoriously difficult problem (NP-complete).

Definition 1.32: A Hamilton cycle in a graph $G = (V, E)$ is a cycle that visits every vertex in $V$ exactly once. A graph containing a Hamilton cycle is called Hamiltonian.

Difficulty of Finding Hamilton Cycles

The problem of finding Hamilton cycles is computationally challenging. In 1972, Richard Karp demonstrated that determining whether a Hamilton cycle exists in a graph is NP-complete. This implies that, under the widely believed assumption that P ≠ NP, there is no polynomial-time algorithm to solve the Hamilton cycle problem.

Exponential Algorithm

Despite the computational hardness, we can devise an exponential-time algorithm to find Hamilton cycles. A brute-force approach would involve checking all possible permutations of vertices to see if they form a Hamilton cycle. This leads to a complexity of approximately $O (n!)$ , where $n$ is the number of vertices. A slightly more efficient approach utilizes dynamic programming and has a complexity of $O (n^{2} 2^{n})$ .

Algorithm: Hamiltonkreis (G = ([n], E))

Algorithm: Hamiltonkreis(G = ([n], E))
Input: Graph G = ([n], E)
Output: True if G contains a Hamilton cycle, False otherwise
 
// Initialization
for all x ∈ [n], x ≠ 1:
    if {1, x} ∈ E:
        P[{1,x},x] = 1
    else:
        P[{1,x},x] = 0
 
// Recursion
for s = 3 to n:
    for all S ⊆ [n] with 1 ∈ S and |S| = s:
        for all x ∈ S, x ≠ 1:
            P[S,x] = max{ P[S\{x},x'] | x' ∈ S ∩ N(x), x' ≠ 1 }
 
// Ausgabe (Output)
if there exists x ∈ N(1) such that P[[n],x] = 1:
    return True // G contains Hamilton cycle
else:
    return False // G does not contain Hamilton cycle

This algorithm uses dynamic programming to compute values $P [S, x]$ , which indicate whether there is a path starting at vertex 1, ending at vertex $x$ , and visiting exactly the vertices in set $S$ . The complexity of this algorithm is $O (n^{2} 2^{n})$ , which is significantly better than $O (n!)$ but still exponential.

Special Cases and the Traveling Salesman Problem (TSP)

While the general Hamilton cycle problem is intractable, certain special classes of graphs admit polynomial-time solutions or have interesting properties related to Hamiltonicity.

Grid Graphs ( $M_{m, n}$ ): Grid graphs, formed by vertices arranged in a grid and edges connecting adjacent vertices, are Hamiltonian if and only if at least one dimension ( $m$ or $n$ ) is even. This can be shown using a parity argument.
Hypercubes ( $H_{d}$ ): d-dimensional hypercubes ( $d \geq 2$ ) are always Hamiltonian. A Hamilton cycle in a hypercube corresponds to a Gray code, a binary encoding where successive codes differ in only one bit position.
Dirac’s Theorem: Dirac’s Theorem provides a sufficient condition for Hamiltonicity based on vertex degrees. If every vertex in a graph with $n \geq 3$ vertices has a degree of at least $n /2$ , then the graph is Hamiltonian. This theorem guarantees Hamiltonicity for dense graphs.

The Traveling Salesman Problem (TSP) is a classic optimization problem closely related to Hamilton cycles. Given a complete graph with edge weights, the TSP seeks to find a Hamilton cycle of minimum total weight. The TSP is also NP-hard, and finding efficient algorithms, even approximation algorithms, remains a major challenge. However, for metric TSP (where edge weights satisfy the triangle inequality), approximation algorithms with approximation ratios of 2 and even 3/2 exist. The metric TSP has practical applications in routing and logistics.

The study of cycles, particularly Hamilton cycles and the TSP, reveals the intricate complexity of graph problems and the challenges in designing efficient algorithms for seemingly simple tasks.

Prev: 04 Connectivity, Articulation Points, Bridges, Block Decomposition | Next: 06 Matchings, Colorings

CS Notes

Explorer