Top-Fragen
Zeitleiste
Chat
Kontext

Turniergraph

Art von Graph Aus Wikipedia, der freien Enzyklopädie

Turniergraph
Remove ads

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.

Thumb
Turniergraph mit 4 Knoten

Formalisierte Definition

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 .
Remove ads

Eigenschaften

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

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads