- Turniergraph
-
Ein Turniergraph 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 (V,E), der die folgenden Bedingungen erfüllt:
- für alle
mit
gilt
oder
,
- für alle
mit
gilt
oder
,
- für alle
gilt
.
Eigenschaften
Jeder nichtleere endliche Turniergraph enthält einen Hamiltonpfad.
- für alle
Wikimedia Foundation.