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:

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.

Examples

>>> from networkx.algorithms import tournament
>>> G = nx.DiGraph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])
>>> tournament.hamiltonian_path(G)
[0, 1, 2, 3]