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: G (NetworkX graph) – A directed graph representing a tournament. Returns: Whether the given graph is a tournament graph. Return type: bool Notes
This is a recursive implementation with an asymptotic running time of
O(n^2)
, ignoring multiplicative polylogarithmic factors, wheren
is the number of nodes in the graph.