In graph theory, a tournament is a directed graph with exactly one edge between each two vertices, in one of the two possible directions. Equivalently, a tournament is an orientation of an undirected complete graph. (However, as directed graphs, tournaments are not complete: complete directed graphs have two edges, in both directions, between each two vertices.) Equivalently, a tournament is a complete asymmetric relation. The name tournament comes from interpreting the graph as the outcome of a round-robin tournament, a game where each player is paired against every other exactly once. In a tournament, the vertices represent the players, and the edges between players point from the winner to the loser. Many of the important properties of tournaments were investigated by H. G. Landau in 1953 to model dominance relations in flocks of chickens. Tournaments are also heavily studied in voting theory, where they can represent partial information about voter preferences among multiple candidates, and are central to the definition of Condorcet methods. If every player beats the same number of other players (indegree − outdegree = 0) the tournament is called regular. The number of unlabeled regular tournaments with 2n+1 vertices goes: 1, 1, 1, 3, 15, 1223, 1495297, 18400989629, 2406183070160597,... (sequence A096368 in the OEIS)
Paths and cycles
Any tournament on a finite number n {\displaystyle n} of vertices contains a Hamiltonian path, i.e., directed path on all n {\displaystyle n} vertices (Rédei 1934). This is shown by induction on n {\displaystyle n} : suppose that the statement holds for n {\displaystyle n} , and consider any tournament T {\displaystyle T} on n + 1 {\displaystyle n+1} vertices. Choose a vertex v 0 {\displaystyle v_{0}} of T {\displaystyle T} and consider a directed path v 1 , v 2 , … , v n {\displaystyle v_{1},v_{2},\ldots ,v_{n}} in T ∖ { v 0 } {\displaystyle T\smallsetminus \{v_{0}\}} . There is some i ∈ { 0 , … , n } {\displaystyle i\in \{0,\ldots ,n\}} such that ( i = 0 ∨ v i → v 0 ) ∧ ( v 0 → v i + 1 ∨ i = n ) {\displaystyle (i=0\vee v_{i}\rightarrow v_{0})\wedge (v_{0}\rightarrow v_{i+1}\vee i=n)} . (One possibility is to let i ∈ { 0 , … , n } {\displaystyle i\in \{0,\ldots ,n\}} be maximal such that for every j ≤ i , v j → v 0 {\displaystyle j\leq i,v_{j}\rightarrow v_{0}} . Alternatively, let i {\displaystyle i} be minimal such that ∀ j > i , v 0 → v j {\displaystyle \forall j>i,v_{0}\rightarrow v_{j}} .)
v 1 , … , v i , v 0 , v i + 1 , … , v n {\displaystyle v_{1},\ldots ,v_{i},v_{0},v_{i+1},\ldots ,v_{n}}
… excerpt ends here. Continue reading the full article.
