Tournament (graph theory)

Tournament
A tournament on 4 vertices
Vertices	${\displaystyle n}$
Edges	${\displaystyle {\binom {n}{2}}}$
Table of graphs and parameters

In graph theory, a tournament is a directed graph with exactly one edge between each two vertices, in one of the two possible directions. Equivalently, a tournament is an orientation of an undirected complete graph. (However, as directed graphs, tournaments are not complete: complete directed graphs have two edges, in both directions, between each two vertices.^[1]) Equivalently, a tournament is a complete asymmetric relation.^[2][3]

The name tournament comes from interpreting the graph as the outcome of a round-robin tournament, a game where each player is paired against every other exactly once. In a tournament, the vertices represent the players, and the edges between players point from the winner to the loser.

Many of the important properties of tournaments were investigated by H. G. Landau in 1953 to model dominance relations in flocks of chickens.^[4] Tournaments are also heavily studied in voting theory, where they can represent partial information about voter preferences among multiple candidates, and are central to the definition of Condorcet methods.

If every player beats the same number of other players (indegree − outdegree = 0) the tournament is called regular.