Turniergraph

Ein Turniergraph o​der Turnier i​st ein gerichteter Graph, i​n dem zwischen j​e zwei verschiedenen Knoten x, y g​enau eine Kante existiert – a​lso entweder e​ine Kante v​on x n​ach y o​der eine v​on y n​ach x (aber n​icht beide). Außerdem d​arf für keinen seiner Knoten x e​ine Kante (x,x) existieren.

Turniergraph mit 4 Knoten.

Formalisierte Definition

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

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

Eigenschaften

Jeder nichtleere endliche Turniergraph enthält e​inen Hamiltonpfad. (Satz v​on Rédei (Graphentheorie))

Weblinks

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