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.
Formalisierte Definition
Ein Turniergraph ist ein gerichteter Graph <math>(V,E)</math>, der die folgenden Bedingungen erfüllt:
- für alle <math>x,y \in V</math> mit <math>x \not= y</math> gilt <math>(x,y) \in E</math> oder <math>(y,x) \in E</math>,
- für alle <math>x,y \in V</math> mit <math>x \not= y</math> gilt <math>(x,y) \not\in E</math> oder <math>(y,x) \not\in E</math>,
- für alle <math>x \in V</math> gilt <math>(x,x) \not\in E</math>.
Eigenschaften
Jeder nichtleere endliche Turniergraph enthält einen Hamiltonpfad. (Satz von Rédei (Graphentheorie))
Weblinks
- Eric W. Weisstein: Tournament. In: MathWorld (englisch).