Top-Fragen
Zeitleiste
Chat
Kontext
Turniergraph
Art von Graph Aus Wikipedia, der freien Enzyklopädie
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.

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))
Weblinks
- 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).
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads