Turniergraph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Turniergraph mit 4 Knoten.

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 (V,E), der die folgenden Bedingungen erfüllt:

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

Eigenschaften[Bearbeiten]

Jeder nichtleere endliche Turniergraph enthält einen Hamiltonpfad.