Turniergraph

Ein Turniergraph oder Turnier ist ein gerichteter Graph, in dem zwischen je zwei verschiedenen Knoten x, y genau eine Kante existiert – also entweder eine Kante von x nach y oder eine von y nach x (aber nicht beide). Außerdem darf für keinen seiner Knoten x eine Kante (x,x) existieren.

Ein Turniergraph ist ein gerichteter Graph ( V , E ) {\displaystyle (V,E)} , der die folgenden Bedingungen erfüllt:

• für alle x , y ∈ V {\displaystyle x,y\in V} mit x ≠ y {\displaystyle x\not =y} gilt ( x , y ) ∈ E {\displaystyle (x,y)\in E} oder ( y , x ) ∈ E {\displaystyle (y,x)\in E} ,
• für alle x , y ∈ V {\displaystyle x,y\in V} mit x ≠ y {\displaystyle x\not =y} gilt ( x , y ) ∉ E {\displaystyle (x,y)\not \in E} oder ( y , x ) ∉ E {\displaystyle (y,x)\not \in E} ,
• für alle x ∈ V {\displaystyle x\in V} gilt ( x , x ) ∉ E {\displaystyle (x,x)\not \in E} .

Jeder nichtleere endliche Turniergraph enthält einen Hamiltonpfad. (Satz von Rédei (Graphentheorie))

• A.A. Sapozhenko: Tournament. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org). 
• Eric W. Weisstein: Tournament. In: MathWorld (englisch).