Tournament (graph theory)
From Wikipedia, the free encyclopedia
A tournament is a directed graph obtained by choosing a direction for each edge in an undirected complete graph. For example, here is a tournament on 4 vertices:
The name tournament originates from such a graph's interpretation as the outcome of some sports competition in which every player encounters every other player exactly once, and in which no draws occur; let us say that an arrow points from the winner to the loser. If player a beats player b, then it is said that a dominates b.
Any tournament on a finite number n of vertices contains a Hamiltonian path, i.e., directed path on all n vertices. This is easily shown by induction on n: suppose that the statement holds for n, and consider any tournament T on n + 1 vertices. Choose a vertex v0 of T and consider a directed path 
in 
. Now let 
be maximal such that 
for all j with 
. Then
is a directed path as desired.
Similarly, any strongly connected tournament on 
vertices contains cycles of length 
. As a corollary, a tournament is strongly connected if and only if it has a Hamiltonian cycle.
A player who wins all games would naturally be the tournament's winner. However, as the above example shows, there might not be such a player; a tournament for which there isn't is called a 1-paradoxical tournament. More generally, a tournament T = (V,E) is called k-paradoxical if for every k-subset V' of V there is a 
such that 
for all 
. By means of the probabilistic method Paul Erdős showed that if 
is sufficiently large, then almost every tournament on V is k-paradoxical.
This article incorporates material from tournament on PlanetMath, which is licensed under the GFDL.
