Paths and Cycles
Any tournament on a finite number of vertices contains a Hamiltonian path, i.e., directed path on all vertices (Rédei 1934). This is easily shown by induction on : suppose that the statement holds for, and consider any tournament on vertices. Choose a vertex of and consider a directed path in . Now let be maximal such that for every there is a directed edge from to .
is a directed path as desired. This argument also gives an algorithm for finding the Hamiltonian path. More efficient algorithms, that require examining only of the edges, are known.
This implies that a strongly connected tournament has a Hamiltonian cycle (Camion 1959). More strongly, every strongly connected tournament is vertex pancyclic: for each vertex v, and each k in the range from three to the number of vertices in the tournament, there is a cycle of length k containing v. Moreover, if the tournament is 4‑connected, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980).
Read more about this topic: Tournament (graph Theory)
Famous quotes containing the words paths and/or cycles:
“Fair is my Love, and cruel as she’s fair
Her brow shades frowns, although her eyes are sunny;
Her smiles are lightning, though her pride despair;
And her disdains are gall, her favours honey.
A modest maid, decked with a blush of honour,
Whose feet do tread green paths of youth and love,”
—Samuel Daniel (1562–1619)
“The stars which shone over Babylon and the stable in Bethlehem still shine as brightly over the Empire State Building and your front yard today. They perform their cycles with the same mathematical precision, and they will continue to affect each thing on earth, including man, as long as the earth exists.”
—Linda Goodman (b. 1929)