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 Bearbeiten
Ein Turniergraph ist ein gerichteter Graph , der die folgenden Bedingungen erfüllt:
- für alle mit gilt oder ,
- für alle mit gilt oder ,
- für alle gilt .
Eigenschaften Bearbeiten
Jeder nichtleere endliche Turniergraph enthält einen Hamiltonpfad. (Satz von Rédei (Graphentheorie))
Weblinks Bearbeiten
- 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).