Turniergraph
# Turniergraph

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 $(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

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

