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:
“She had no longer any relish for her once favorite amusement of reading. And mostly she disliked those authors who have penetrated deeply into the intricate paths of vanity in the human mind, for in them her own folly was continually brought to her remembrance and presented to her view.”
—Sarah Fielding (1710–1768)
“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)