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:
“Happy are those who find wisdom, and those who get understanding, for her income is better than silver, and her revenue better than gold. She is more precious than jewels, and nothing you desire can compare with her. Long life is in her right hand; in her left hand are riches and honor. Her ways are ways of pleasantness, and all her paths are peace. She is a tree of life to those who lay hold of her; those who hold her fast are called happy.”
—Bible: Hebrew, Proverbs 3:13-18.
“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)