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:
“Now it is the time of night
That the graves, all gaping wide,
Every one lets forth his sprite
In the church-way paths to glide.”
—William Shakespeare (1564–1616)
“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)