Tournament graph

Tournament graph with 4 nodes.

A tournament graph or tournament is a directed graph in which there is exactly one edge between two different nodes x, y - either an edge from x to y or one from y to x (but not both). In addition, no edge (x, x) may exist for any of its nodes x.

Formalized definition

A tournament graph is a directed graph that meets the following conditions: ${\displaystyle (V,E)}$

• for all with valid or , ${\displaystyle x,y\in V}$ ${\displaystyle x\not =y}$ ${\displaystyle (x,y)\in E}$ ${\displaystyle (y,x)\in E}$
• for all with valid or , ${\displaystyle x,y\in V}$ ${\displaystyle x\not =y}$ ${\displaystyle (x,y)\not \in E}$ ${\displaystyle (y,x)\not \in E}$
• for all true . ${\displaystyle x\in V}$ ${\displaystyle (x,x)\not \in E}$

properties

Every non-empty finite tournament graph contains a Hamilton path . ( Rédei theorem (graph theory) )

Web links

• AA Sapozhenko: Tournament . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
• Eric W. Weisstein : Tournament . In: MathWorld (English).