Satz von Ghouila-Houri

aus Wikipedia, der freien Enzyklopädie
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.

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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Rudolf Halin: Graphentheorie. 1989, S. 110
  2. Robin J. Wilson: Einführung in die Graphentheorie. 1976, S. 111–112
  3. Frank Harary: Grapentheorie. 1974, S. 220
  4. Halin, op. cit., S. 110, 304