|
|
|
|
|
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:
Any tournament on a finite number  of vertices contains a Hamiltonian path, i.e., directed path on all  vertices. 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 all  with
 . Then
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  -paradoxical tournament. More generally, a tournament  is called  -paradoxical if for every  -subset  of  there is a
 such that
 for all  . By means of the probabilistic method Erdős showed that if  is sufficiently large, then almost every tournament on  is  -paradoxical.
A transitive tournament is a tournament in which, for all vertices  ,  and  , if there is an edge from  to  and an edge from  to  then there is also an edge from  to  .
|
"tournament" is owned by yark. [ full author list (3) | owner history (2) ]
|
|
(view preamble)
See Also: complete graph, graph theory
| Other names: |
directed complete graph |
| Also defines: |
paradoxical tournament, transitive tournament |
|
|
Cross-references: probabilistic method, games, points, arrow, player, outcome, interpretation, graph's, vertex, induction, path, Hamiltonian path, contains, finite, vertices, complete graph, edge, directed graph
There are 4 references to this entry.
This is version 4 of tournament, born on 2002-10-11, modified 2007-01-06.
Object id is 3518, canonical name is Tournament.
Accessed 5722 times total.
Classification:
| AMS MSC: | 05C20 (Combinatorics :: Graph theory :: Directed graphs , tournaments) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![\begin{displaymath}\begin{xy} *!C\xybox{ \xymatrix{ 1 \ar[dr] \ar[r] &2 \ar[d]\ 3 \ar[u] \ar[ur] &4 \ar[l]} } \end{xy}\end{displaymath}](http://images.planetmath.org:8080/cache/objects/3518/l2h/img1.png "\begin{displaymath}\begin{xy} *!C\xybox{ \xymatrix{ 1 \ar[dr] \ar[r] &2 \ar[d]\ 3 \ar[u] \ar[ur] &4 \ar[l]} } \end{xy}\end{displaymath}")
