Editing Tournament (graph theory) (section)

{{Short description|Directed graph where each vertex pair has one arc}}
{{Infobox graph
 | name = Tournament
 | image = [[Image:4-tournament.svg|180px]]
 | image_caption = A tournament on 4 vertices
 | vertices = <math>n</math>
 | edges = <math>\binom{n}{2}</math>
}}
In [[graph theory]], a '''tournament''' is a [[directed graph]] with exactly one edge between each two [[vertex (graph theory)|vertices]], in one of the two possible directions. Equivalently, a tournament is an [[Orientation (graph theory)|orientation]] of an [[complete graph|undirected complete graph]]. (However, as directed graphs, tournaments are not complete: complete directed graphs have two edges, in both directions, between each two vertices.<ref>{{mathworld |title=Tournament |id=Tournament|mode=cs2}}</ref>) Equivalently, a tournament is a [[Connected_relation|complete]] [[Asymmetric_relation|asymmetric]] [[Binary_relation|relation]].<ref>{{cite journal |last1=Moulin |first1=Hervé |author-link1=Hervé Moulin |date=1986 |title=Choosing from a tournament |url=https://link.springer.com/article/10.1007/BF00292732 |journal=Social Choice and Welfare |volume=3 |issue=4 |pages=271–291 |doi=10.1007/BF00292732 |access-date=January 19, 2025 |quote=A tournament is any complete asymmetric relation over a finite set A of outcomes describing pairwise comparisons.}}</ref><ref>{{cite journal |last1=Laffond |first1=Gilbert |last2=Laslier |first2=Jean-Francois |last3=Le Breton |first3=Michel |date=January 1993 |title=The Bipartisan Set of a Tournament Game |url=https://www.sciencedirect.com/science/article/abs/pii/S0899825683710109 |journal=Games and Economic Behavior |volume=5 |issue=1 |pages=182–201 |doi=10.1006/game.1993.1010 |access-date=January 19, 2025 |quote=A tournament is a complete asymmetric binary relation U over a finite set X of outcomes.}}</ref>

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.{{sfnp|Landau|1953}} Tournaments are also heavily studied in [[social choice theory|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 ([[Copeland score|indegree − outdegree]] = 0) the tournament is called ''regular''.