Tournament
A complete oriented graph (Skiena 1990, p. 175), i.e., a graph in which every pair of nodes is connected by a single uniquely directed edge. The first and second 3-node tournaments shown above are called a transitive triple and cyclic triple, respectively (Harary 1994, p. 204).
Tournaments (also called tournament graphs) are so named because an 
-node tournament
graph correspond to a tournament in which each member of a group of 
players plays all
other 
players, and each game results in a win for one
player and a loss for the other. A so-called score
sequence can be associated with every tournament giving the set of scores that
would be obtained by the players in the tournament, with each win counting as one
point and each loss counting as no points. (A different scoring system is used to
compute a tournament's so-called tournament matrix,
with 1 point awarded for a win and 
points for a
loss.) The score sequence for a given tournament is obtained from the set of outdegrees
sorted in nondecreasing order.
The number 
of nonisomorphic tournaments on 
, 3, 4, ... nodes are 1, 2, 4, 12, 56, 456, ... (OEIS A000568;
Moon 1968; Goldberg and Moon 1970; Harary and Palmer 1973, pp. 126 and 245;
Reid and Beineke 1978). Davis (1954) and Harary (1957) obtained a formula for these
numbers as a function of 
using the Pólya
enumeration theorem. For a symmetric group 
, define
 |
(1)
|
where
 |
(2)
|
with 
the number of group elements in the conjugacy
class of 
in 
, and 
is the number
of cycles of length 
in the disjoint-cycle representation
of any member of the class. Define
 |
(3)
|
where 
is the greatest
common divisor of 
and 
. Then
 |
(4)
|
(Davis 1954).
Every tournament contains an odd number of Hamiltonian paths (Rédei 1934; Szele 1943; Skiena 1990, p. 175). However, a tournament has a directed Hamiltonian cycle iff it is strongly connected (Foulkes 1960; Harary and Moser 1966; Skiena 1990, p. 175).
The term "tournament" also refers to an arrangement by which teams or players play against certain other teams or players in order to determine who is the best.
In a "cup" tournament of 
teams, teams
play pairwise in a sequence of 
-finals,
..., 1/8-finals, quarterfinals, semifinals, and finals, with winners from each round
playing other winners in the next round and losers being eliminated at each round.
The second-place prize is usually awarded to the team that loses in the finals. However,
this practice is unfair since the second-place team has not been required to play
against the teams that were eliminated by the first-place (and presumably best) team,
and therefore might actually be worse than one of the teams eliminated earlier by
the best team (Steinhaus 1999).
In general, to fairly determine the best two players from 
contestants, 
rounds are required (Steinhaus 1999,
p. 55).
Contact the MathWorld Team
Apollonian network
