Satz von Ghouila-Houri
Zur Navigation springen
Zur Suche springen
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.[1][2][3]
Formulierung des Satzes
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]Der Satz von Ghouila-Houri wurde von mehreren Autoren verschärft; so im Jahre 1973 von M. Meyniel wie folgt:[4]
- 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
[Bearbeiten | Quelltext bearbeiten]- 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).