Skip to main content
`Ctrl`+`K`

# 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:
    path list

      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

      >>> G = nx.DiGraph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)])
      >>> nx.is_tournament(G)
      True
      >>> nx.tournament.hamiltonian_path(G)
      [0, 1, 2, 3]