Hamiltonian Paths and Cycles (Extension) (VCE SSCE General Mathematics): Revision Notes
Hamiltonian Paths and Cycles (Extension)
Introduction to Hamiltonian concepts
When studying graphs and networks, it's important to understand the difference between two key concepts:
- Eulerian trails and circuits focus on edges (the lines connecting vertices)
- Hamiltonian paths and cycles focus on vertices (the points in a graph)
This distinction is crucial for solving different types of problems in graph theory.
The fundamental difference between Eulerian and Hamiltonian concepts lies in what they prioritize: Eulerian concepts require using every edge exactly once, while Hamiltonian concepts require visiting every vertex exactly once. Understanding this distinction will help you recognize which approach to apply to different problems.
Hamiltonian path
A Hamiltonian path is a route through a graph that passes through each vertex exactly once, without repeating any vertex. Unlike Eulerian trails, you don't need to use every edge in the graph.
Key definition: A Hamiltonian path visits every vertex of a graph, with no repeated vertices.
In the graph shown above, the path is a Hamiltonian path. Notice how:
- The path starts at vertex and ends at vertex
- Every vertex is visited exactly once
- Not all edges are used (some edges are not part of this particular path)
A Hamiltonian path does not have to involve all edges of the graph. It only needs to visit all vertices. This is a key difference from Eulerian trails, which must use all edges.
Hamiltonian cycle
A Hamiltonian cycle is similar to a Hamiltonian path, but with one crucial difference: it returns to the starting vertex, creating a closed loop.
Key definition: A Hamiltonian cycle visits every vertex of a graph with no repeated vertices, except for starting and finishing at the same vertex.
For example, consider a path . This is a Hamiltonian cycle because:
- It starts and finishes at vertex
- Every vertex is visited exactly once (except , which appears at both the start and end)
- It forms a complete circuit
Like Hamiltonian paths, a Hamiltonian cycle does not have to involve all edges of the graph. The focus is entirely on visiting all vertices.
No simple rules
Critical Difference from Eulerian Concepts:
Unlike Eulerian trails and circuits, there is no straightforward test to determine whether a graph contains a Hamiltonian path or cycle. Instead, you must rely on trial and error or systematic inspection. This makes finding Hamiltonian paths and cycles more challenging than finding Eulerian trails.
Identifying Hamiltonian paths and cycles
Let's work through a detailed example to understand how to identify Hamiltonian paths and determine if cycles exist.
Worked Example: Identifying Hamiltonian paths and cycles
For each of the following graphs:
- i) Identify a Hamiltonian path, starting at vertex
- ii) State whether a Hamiltonian cycle is possible or not. If possible, identify one. If not possible, explain why not.
Solution:
Graph (a):
i) Hamiltonian path:
This path starts at and visits each vertex exactly once, ending at .
ii) Hamiltonian cycle:
A Hamiltonian cycle is not possible for this graph.
Explanation: Whichever vertex you start at, you cannot return to the same vertex without repeating at least one other vertex. Try starting at any vertex and attempting to create a cycle – you'll find it's impossible to visit all vertices and return to the start without going through one vertex twice.
Graph (b):
i) Hamiltonian path:
This path starts at and visits each vertex exactly once, ending at .
ii) Hamiltonian cycle:
Yes, a Hamiltonian cycle is possible for this graph.
One example:
This cycle starts at , visits every vertex exactly once, and returns to .
Exam tip:
When identifying Hamiltonian paths and cycles:
- Start systematically from the given vertex
- Keep track of which vertices you've visited
- For cycles, check if you can return to the start without repeating vertices
- Try multiple routes if your first attempt doesn't work
- Remember: there may be several valid Hamiltonian paths or cycles for the same graph
Applications of Hamiltonian paths and cycles
Understanding Hamiltonian paths and cycles has many practical applications in everyday life.
Hamiltonian path applications
A Hamiltonian path applies to situations where you want to visit multiple locations without visiting any location more than once, such as:
- Road trip planning: You plan a trip from Melbourne to Mildura, with visits to Bendigo, Halls Gap, Horsham, Stawell and Ouyen along the way, but you don't want to visit any town more than once.
The key feature is that you start at one point and end at a different point, visiting all locations exactly once.
Hamiltonian cycle applications
A Hamiltonian cycle relates to situations where you want to return to your starting point after visiting all locations, such as:
- Delivery routes: A courier leaves their depot to make deliveries to various locations before returning to the depot. They don't want to pass each location more than once.
- Tourist itineraries: A tourist plans to visit all historic sites in a city without visiting each site more than once, returning to their starting point.
- Round trip planning: You're planning a trip from Melbourne to visit Shepparton, Wodonga, Bendigo, Swan Hill, Natimuk, Warrnambool and Geelong before returning to Melbourne. You don't want to visit any town more than once.
Considering additional factors
In all these situations, there could be several suitable Hamiltonian paths or cycles. However, other factors such as time taken or distance travelled may need to be considered to determine the best route. This leads to the study of weighted graphs and networks, where edges have values representing distances, times, or costs.
Key Points to Remember:
-
Hamiltonian path: A walk that visits every vertex of a graph exactly once, with no repeated vertices
-
Hamiltonian cycle: A walk that visits every vertex of a graph exactly once (except for starting and ending at the same vertex), creating a closed loop
-
Key difference: Eulerian concepts focus on edges, while Hamiltonian concepts focus on vertices
-
No simple test: Unlike Eulerian trails and circuits, there are no straightforward rules for determining if a Hamiltonian path or cycle exists – you must use trial and error or systematic inspection
-
Not all edges required: Both Hamiltonian paths and cycles can exist without using every edge in the graph