Turniergraph

Datei:4-tournament.svg

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

Ein Turniergraph ist ein gerichteter Graph <math>(V,E)</math>, der die folgenden Bedingungen erfüllt:

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

Eigenschaften

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

Weblinks

• {{#invoke:Vorlage:Literatur|f}}{{#if:|Vorlage:EoM/id}}
• {{#if: | | Eric W. Weisstein }}: Tournament. In: MathWorld (englisch). {{#if: Tournament | {{#ifeq: {{#property:P2812}} | Tournament | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}

{{#ifeq: s | p | | {{#if: 4473306-9 | |

}} }}{{#ifeq:||{{#if: | [[Kategorie:Wikipedia:GND fehlt {{#invoke:Str|left|{{{GNDCheck}}}|7}}]] }}{{#if: | {{#if: | | }} }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#ifeq: s | p | {{#if: 4473306-9 | | {{#if: {{#statements:P227}} | | }} }} }}{{#ifeq: s | p | {{#if: 4473306-9 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P227}} | | }} }} }} }}{{#ifeq: s | p | {{#if: | | {{#if: {{#statements:P244}} | | }} }} }}{{#ifeq: s | p | {{#if: | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P244}} | | }} }} }} }}{{#ifeq: s | p | {{#if: | | {{#if: {{#statements:P214}} | | }} }} }}{{#ifeq: s | p | {{#if: | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P214}} | | }} }} }} }}Vorlage:Wikidata-Registrierung