Satz von Ghouila-Houri
# Satz von Ghouila-Houri

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)\geq 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)\geq {\frac {n(D)}{2}}$
    und
       $d_{G}^{+}(v)\geq {\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})\geq 2n(D)-1$.
    erfüllt, so besitzt $D$ einen hamiltonschen Zyklus.
