Hamilton Paths and Hamilton Circuits: Video e Problemi di Pratica
Hamilton Paths and Hamilton Circuits focus on traveling through a graph by visiting vertices in a specific way. A Hamilton path visits each vertex of the graph exactly once. A Hamilton circuit also visits each vertex exactly once, but it starts and ends at the same vertex. The only repeated vertex allowed in a Hamilton circuit is the starting vertex at the end; if any other vertex appears more than once, the sequence is neither a Hamilton path nor a Hamilton circuit.
In a complete graph, every pair of vertices is connected by an edge, so Hamilton circuits must exist. The number of unique Hamilton circuits in a complete graph with \\(n\\) vertices can be found with \(\frac{(n-1)!}{2}\). Some settings may instead use \((n-1)!\) if reverse directions are counted as different circuits.
Hamilton Paths and Hamilton Circuits
Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.
H.P.
H.C.
NEITHER
Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.
H.P.
H.C.
NEITHER
Using the graph below, determine if the sequence of vertices describes a Hamilton path (H.P.), a Hamilton circuit (H.C.), or neither.
H.P.
H.C.
NEITHER
Hamilton Paths and Hamilton Circuits Example 1
Hamilton Paths and Hamilton Circuits Example 2
Number of Hamilton Circuits in a Complete Graph
Determine if the graph must have Hamilton circuits. If so, how many?
Note: We will be using the formula below.
Complete? ☐
# of vertices: ___
# of Hamilton circuits: ___
Complete? Yes; # of vertices: 60; # of Hamilton circuits: 6
Complete? No; # of vertices: 60; # of Hamilton circuits: 6
Complete? Yes; # of vertices: 6; # of Hamilton circuits: 120
Complete? Yes; # of vertices: 6; # of Hamilton circuits: 60
How many Hamilton circuits exist in a complete graph with the given number of vertices, ?
Note: We will be using the formula below.
1
3
2
6
How many Hamilton circuits exist in a complete graph with the given number of vertices, ?
Note: We will be using the formula below.
Number of Hamilton Circuits in a Complete Graph Example 3
Weighted Graphs
The weights on the graph below represent distances (in miles). Find the total distance (weight) of each path or circuit.
Home, Grocery Store, Post Office, Bank
17 mi
20 mi
18 mi
13 mi
The weights on the graph below represent distances (in miles). Find the total distance (weight) of each path or circuit.
Home, Grocery Store, Post Office, Bank, Home
22 mi
23 mi
25 mi
27 mi
Weighted Graphs Example 4
Weighted Graphs Example 5
Brute Force Method
Brute Force Method Example 6
Brute Force Method Example 7
Ecco cosa chiedono gli studenti su questo argomento:
A Hamilton path is a path in a graph that visits each vertex exactly once without repeating any vertex. In contrast, a Hamilton circuit (or Hamiltonian cycle) also visits each vertex exactly once but starts and ends at the same vertex, forming a closed loop. The only vertex that appears twice in a Hamilton circuit is the starting vertex, which is repeated at the end to complete the cycle. If any other vertex is repeated, the sequence is neither a Hamilton path nor a Hamilton circuit. Understanding this distinction is crucial when analyzing graphs for these special paths or cycles.
In a complete graph, every pair of vertices is connected by an edge. Because of this, a Hamilton circuit always exists in a complete graph with \(n\) vertices, provided \(n \geq 3\). This is because you can start at any vertex and travel through all other vertices exactly once before returning to the starting point, thanks to the full connectivity. The completeness guarantees that there are edges between every pair of vertices, making it possible to form such a circuit.
The number of unique Hamilton circuits in a complete graph with \(n\) vertices is given by the formula: . This formula accounts for the fact that circuits that are the same but traveled in reverse order are considered identical. Some contexts may count reverse directions as different circuits, in which case the number of Hamilton circuits is . This factorial-based formula arises because you fix one vertex as the start to avoid counting rotations of the same circuit multiple times, then arrange the remaining vertices in all possible orders.
In a Hamilton circuit, the path must start and end at the same vertex to form a closed loop, so the starting vertex is repeated at the end to complete the cycle. This repetition is allowed and necessary to define the circuit. In contrast, a Hamilton path does not require returning to the starting vertex; it simply visits each vertex exactly once without repetition. Therefore, the starting vertex is not repeated in a Hamilton path because the path is open-ended, not a cycle.
A sequence of vertices cannot be both a Hamilton path and a Hamilton circuit simultaneously because they have different definitions. A Hamilton path visits each vertex exactly once without returning to the start, while a Hamilton circuit visits each vertex exactly once and returns to the starting vertex, forming a cycle. However, every Hamilton circuit contains a Hamilton path if you remove the last edge that returns to the start. So, while related, they are distinct concepts.
