A Hamiltonian graph is a graph that contains a special kind of closed path called a Hamiltonian cycle, which visits every vertex in the graph exactly once before returning to its starting point.
What is a Hamiltonian Graph?
A Hamiltonian graph is defined by the presence of a Hamiltonian cycle within its structure. This cycle is a closed path (or circuit) that has a unique characteristic: it traverses every single vertex of the graph precisely one time, ultimately concluding its journey back at the vertex where it began. The sequence of vertices and edges forming this cycle must include all vertices of the graph.
Unlike an Eulerian circuit, which focuses on visiting every edge exactly once, a Hamiltonian cycle's primary concern is visiting every vertex exactly once.
Key Characteristics of a Hamiltonian Cycle:
- Visits Every Vertex: The path must include all vertices present in the graph.
- Visits Exactly Once: No vertex, except for the start/end vertex, can be revisited during the cycle.
- Closed Path: The cycle must start and end at the same vertex, forming a closed loop.
Example of a Hamiltonian Graph
Consider a simple graph with five vertices and five edges, shaped like a pentagon.
Vertex | Edges to |
---|---|
A | B, E |
B | A, C |
C | B, D |
D | C, E |
E | D, A |
Let's visualize this graph (we'll represent it as a cycle).
Vertices: A, B, C, D, E
Edges: (A, B), (B, C), (C, D), (D, E), (E, A)
In this graph, a Hamiltonian cycle can be easily traced:
A → B → C → D → E → A
Let's break down why this is a Hamiltonian cycle:
- Visits Every Vertex: The path includes A, B, C, D, and E, covering all vertices in the graph.
- Visits Exactly Once: Each vertex (B, C, D, E) is visited only once during the traversal, and A is visited once as the start and once as the end point.
- Closed Path: The path starts at A and ends back at A, forming a complete cycle.
This pentagonal graph is therefore a Hamiltonian graph because it contains at least one Hamiltonian cycle. Other examples of Hamiltonian graphs include all complete graphs ($K_n$ for $n \ge 3$) and hypercube graphs.
Practical Insights
Hamiltonian cycles and graphs have significant applications in various fields, including:
- Operations Research: Optimizing delivery routes (e.g., the Traveling Salesperson Problem, which seeks the shortest Hamiltonian cycle).
- Computer Science: Designing network topologies and analyzing algorithms.
- Biology: Understanding genetic sequences and protein structures.
For further exploration of graph theory concepts, you can refer to resources like Wikipedia's article on Hamiltonian Path.