hamiltonian_path¶
- hamiltonian_path(G)[source]¶
Returns a Hamiltonian path in the given tournament graph.
Each tournament has a Hamiltonian path. If furthermore, the tournament is strongly connected, then the returned Hamiltonian path is a Hamiltonian cycle (by joining the endpoints of the path).
- Parameters
- GNetworkX graph
A directed graph representing a tournament.
- Returns
- pathlist
A list of nodes which form a Hamiltonian path in
G
.
Notes
This is a recursive implementation with an asymptotic running time of \(O(n^2)\), ignoring multiplicative polylogarithmic factors, where \(n\) is the number of nodes in the graph.