Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# networkx.algorithms.tournament.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.