Satz von Ghouila-Houri

Vorlage:Dieser Artikel In der Theorie der gerichteten Graphen, einem der Teilgebiete der Graphentheorie, ist der Satz von Ghouila-Houri das Pendant zum Satz von Dirac in der Theorie der ungerichteten Graphen. Der Satz geht auf eine Arbeit des französischen Mathematikers Alain Ghouila-Houri aus dem Jahre 1960 zurück. Von mehreren Autoren wird hervorgehoben, dass der Beweis des Ghouila-Houri'schen Satzes um einiges schwieriger sei als der des diracschen.

Formulierung des Satzes

Der Satz lässt sich zusammengefasst angeben wie folgt:

Gegeben sei ein endlicher gerichteter Graph $D$.

$D$ sei stark zusammenhängend und habe zudem die Eigenschaft, dass an jedem Knoten $v$ für den Grad $d_G(v)=d_G^{-}(v)+d_G^{+}(v)$ in Bezug auf die Knotenzahl $n(D)$ durchweg die Ungleichung

$d_G(v)\ge n(D)$

erfüllt ist.

Dann besitzt $D$ einen hamiltonschen Zyklus, also einen Zyklus, auf dem alle Knoten von $D$ genau einmal vorkommen.

Insbesondere gilt diese Aussage für den Fall, dass an jedem Knoten $v$ hinsichtlich Eingangsgrad und Ausgangsgrad die beiden Ungleichungen

$d_G^{-}(v)\ge \frac{n(D)}{2}$

und

$d_G^{+}(v)\ge \frac{n(D)}{2}$

erfüllt sind.

Verschärfung

Der Satz von Ghouila-Houri wurde von mehreren Autoren verschärft; so im Jahre 1973 von M. Meyniel wie folgt:

Ist $D$ ein endlicher stark zusammenhängender gerichteter Graph, der für je zwei verschiedene nicht benachbarte Knoten $v_1$ und $v_2$ die Ungleichung

$d_G(v_1)+d_G(v_2)\ge 2n(D)-1$.

erfüllt, so besitzt $D$ einen hamiltonschen Zyklus.

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur