Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.tournament.hamiltonian_path

hamiltonian_path(G)

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, where \(n\) is the number of nodes in the graph.