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).