Satz von Tutte (Hamiltonkreisproblem)

In der Topologischen Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Tutte zum Hamiltonkreisproblem einer der Lehrsätze des britisch-kanadischen Graphentheoretikers William Thomas Tutte (1917–2002). Tutte publizierte den Satz im Jahre 1956 und verknüpft dabei – an ein Resultat von Hassler Whitney aus dem Jahre 1931 anschließend – das Hamiltonkreisproblem mit der Frage der Plättbarkeit und des mehrfachen Zusammenhangs. Der Satz ist bedeutsam in Bezug auf das Vier-Farben-Problem.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:[1]

Ist ein endlicher schlichter Graph plättbar und -fach zusammenhängend, so enthält einen hamiltonschen Kreis.

Der Satz lässt sich auch so formulieren:[2]

In jedem endlichen schlichten Graphen , der plättbar ist und keinen minimalen Schnitt mit drei oder weniger Knoten enthält, gibt es einen hamiltonschen Kreis.

Der whitneysche Satz

Der von Hassler Whitney 1931 vorgelegte Satz macht die gleiche Aussage wie der tuttesche Satz, tut dies allerdings unter einer zusätzlichen Voraussetzung. Es soll nämlich hier der den Graphen darstellenden Streckengraph zusätzlich der Bedingung genügen, dass jedes Land seiner topologischen Landkarte eine Dreiecksfläche in der euklidischen Ebene ist.[1]

Bezug zum Vier-Farben-Problem

Wie Hansjoachim Walther/Heinz-Jürgen Voß[1] und Øystein Ore[3] ausführen, ist für die topologischen Landkarten der betrachteten Graphen das Vier-Farben-Problem gelöst. Denn ein solcher Graph lässt sich stets derart in die Oberfläche der Einheitskugel einbetten, dass die Knoten des hamiltonschen Kreises sämtlich auf dem Äquators der Kugeloberfläche zu liegen kommen. Davon ausgehend lässt sich durch vollständige Induktion nachweisen, dass sowohl die Länder der Nordhalbkugel der zugehörigen topologischen Landkarte als auch ihre Länder auf der Südhalbkugel stets eine zulässige Färbung mit zwei Farben besitzen, weswegen die gesamte topologische Landkarte eine zulässige Färbung mit vier Farben gestattet.[4]

Literatur

Einzelnachweise und Fußnoten
  1. Hansjoachim Walther, Heinz-Jürgen Voß: Über Kreise in Graphen. 1974, S. 26
  2. Øystein Ore: The Four-Color Problem. 1967, S. 74
  3. Ore, op. cit., S. 105–108
  4. Das bedeutet etwa für den Beweis des Vierfarbensatzes, dass im Rahmen eines Widerspruchsbeweises das angenommene kleinste Gegenbeispiel als ebener nicht -fach zusammenhängender Streckengraph vorausgesetzt werden kann.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.