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.

Literatur

• Alain Ghouila-Houri: Une condition suffisante d'existence d'un circuit hamiltonien. In: Comptes rendus de l’Académie des sciences Paris. Band 251, 1960, S. 495–497 (MR0114771). 
• Rudolf Halin: Graphentheorie. 2., überarbeitete und erweiterte Auflage. Wissenschaftliche Buchgesellschaft, Darmstadt 1989, ISBN 3-534-10140-5 (MR1068314). 
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• M. Meyniel: Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente. In: Journal of Combinatorial Theory. Series B. Band 14, 1973, S. 137–147 (MR0317997). 
• Robin J. Wilson: Einführung in die Graphentheorie. Aus dem Englischen übersetzt von Gerd Wegner (= Moderne Mathematik in elementarer Darstellung. Band 15). Vandenhoeck & Ruprecht, Göttingen 1976 (MR0434854 – Englische Vorlage: Introduction to Graph Theory, Longman, London 1975).