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.

Turniergraph mit 4 Knoten.

Formalisierte DefinitionBearbeiten

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  .

EigenschaftenBearbeiten

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

WeblinksBearbeiten