Tournament (graph theory)
From Freepedia
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:
Image:Tournament (graph theory).png
Any tournament on a finite number <math>n</math> of vertices contains a Hamiltonian path, i.e., directed path on all <math>n</math> vertices. This is easily shown by induction on <math>n</math>: suppose that the statement holds for <math>n</math>, and consider any tournament <math>T</math> on <math>n+1</math> vertices. Choose a vertex <math>v_0</math> of <math>T</math> and consider a directed path <math>v_1,v_2,\ldots,v_n</math> in <math>T\setminus \{v_0\}</math>. Now let <math>i \in \{0,\ldots,n\}</math> be maximal such that <math>v_j \rightarrow v_0</math> for all <math>j</math> with <math>1 \leq j \leq i</math>. Then
- <math>v_1,\ldots,v_i,v_0,v_{i+1},\ldots,v_n</math>
is a directed path as desired.
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.
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 <math>1</math>-paradoxical tournament. More generally, a tournament <math>T=(V,E)</math> is called <math>k</math>-paradoxical if for every <math>k</math>-subset <math>V'</math> of <math>V</math> there is a <math>v_0 \in V \setminus V'</math> such that <math>v_0 \rightarrow v</math> for all <math>v \in V'</math>. By means of the probabilistic method Paul Erdős showed that if <math>\vert V\vert</math> is sufficiently large, then almost every tournament on <math>V</math> is <math>k</math>-paradoxical.
This article incorporates material from tournament on PlanetMath, which is licensed under the GFDL.
