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.Rudolf Halin: Graphentheorie. 1989, S. 110Robin J. Wilson: Einführung in die Graphentheorie. 1976, S. 111–112Frank Harary: Grapentheorie. 1974, S. 220
Formulierung des Satzes Der Satz lässt sich zusammengefasst angeben wie folgt: Gegeben sei ein endlicher gerichteter Graph . sei stark zusammenhängend und habe zudem die Eigenschaft, dass an jedem Knoten für den Grad in Bezug auf die Knotenzahl durchweg die Ungleichung
erfüllt ist. Dann besitzt einen hamiltonschen Zyklus, also einen Zyklus, auf dem alle Knoten von genau einmal vorkommen. Insbesondere gilt diese Aussage für den Fall, dass an jedem Knoten hinsichtlich Eingangsgrad und Ausgangsgrad die beiden Ungleichungen
und
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:Halin, op. cit., S. 110, 304 Ist ein endlicher stark zusammenhängender gerichteter Graph, der für je zwei verschiedene nicht benachbarte Knoten und die Ungleichung . erfüllt, so besitzt einen hamiltonschen Zyklus.
Literatur
Einzelnachweise
Ghouila-Houri Ghouila-Houri