Hamiltonsch

Das Hamiltonkreisproblem ist ein fundamentales, NP-vollständiges Problem der Graphentheorie. Es fragt, ob in einem gegebenen Graph ein sogenannter Hamiltonkreis existiert. Ein Hamiltonkreis ist dabei ein Kreis, der alle Knoten des Graphen enthält (und keinen Knoten zweimal durchläuft oder überschreitet).

Man unterscheidet das Gerichtete Hamiltonkreisproblem in gerichteten Graphen und das Ungerichtete Hamiltonkreisproblem in ungerichteten Graphen. Ein bekannter Spezialfall des Hamiltonkreisproblems ist das Problem des Handlungsreisenden, bei welchem nach einem kürzesten Hamiltonkreis in einem gerichteten Graphen mit Kantengewichten gefragt wird.

Geschichte

Das Dodekaeder ist, wie alle platonischen Körper, hamiltonsch.

Namensgeber des Problems ist der irische Astronom und Mathematiker Sir William Rowan Hamilton, der 1857 das Spiel „The Icosian Game“ erfand (und später verbesserte zum „Traveller's Dodecahedron or A Voyage Round The World“).

Der „Traveller's Dodecahedron“ besteht aus einem hölzernen, regulären Dodekaeder, wobei die 20 Knoten mit Namen bekannter Städte assoziiert sind. Ziel ist es, eine Reiseroute entlang der Kanten des Dodekaeders zu finden, die jede Stadt genau einmal besucht und dort aufhört, wo sie beginnt.

Zunächst erscheint die Aufgabenstellung ähnlich dem 1736 von Leonhard Euler (verneinend) gelösten Königsberger Brückenproblem, einem Spezialfall des Eulerkreisproblems und Grundsteinlegung der Graphentheorie. Während für das Eulerkreisproblem aber besonders effiziente Lösungs-Algorithmen existieren, ist bekannt, dass beide Varianten des Hamiltonkreisproblems besonders schwer algorithmisch lösbare Probleme sind. Sowohl die gerichtete als auch die ungerichtete Variante des Hamiltonkreisproblems gehört zur Liste der 21 klassischen NP-vollständigen Probleme, für die Richard Karp 1972 in seinem berühmten Artikel die Zugehörigkeit zu dieser Klasse von Problemen nachgewiesen hat.

Definitionen

Sei $G=(V,E)\!$ ein Graph mit $|V|=n\!$ Knoten (oder Ecken) und $|E|=m\!$ Kanten.

$G\!$ ist hamiltonsch, wenn er einen Hamiltonkreis zulässt, d.h., wenn es einen Kreis in $G\!$ gibt, der alle Knoten aus $V\!$ enthält. Ein Hamiltonpfad ist ein Pfad in $G\!$, der alle Knoten aus $V\!$ enthält. Hat $G\!$ Hamiltonpfade, jedoch keinen Hamiltonkreis, so ist $G\!$ semihamiltonsch.

Zur Potenz eines Graphen: Für einen Graphen $G\!$ und $d \in \mathbb{N}$ bezeichnet $G^d\!$ den Graphen auf $V\!$, bei dem zwei Knoten genau dann benachbart sind, wenn sie in $G\!$ einen Abstand (oder Distanz) $\leq d$ haben. Offenbar gilt $G=G^1\subseteq G^2\subseteq G^3\subseteq...$.

Ist $G\!$ ein Graph mit $n\!$ Knoten und Knotengraden $d_{1}\leq...\leq d_{n}$, so nennt man das Tupel $(d_{1},...,d_{n})\!$ die Gradsequenz (oder Valenzfolge) von $G\!$, welche eindeutig bestimmt ist. Ein beliebiges Tupel $(a_{1},...,a_{n})\!$ natürlicher Zahlen heißt hamiltonsch, wenn jeder Graph mit $n\!$ Knoten und punktweise größerer Gradsequenz hamiltonsch ist. (Eine Gradsequenz $(d_{1},...,d_{n})\!$ ist punktweise größer als $(a_{1},...,a_{n})\!$, wenn $d_{i}\geq a_{i}$ gilt für alle $i\!$.)

Wichtige Aussagen und Sätze

Welche Bedingungen an einen Graphen $G\!$ mit $n\geq 3$ haben die Existenz eines Hamiltonkreises zur Folge? Besonders wichtige Theoreme sind folgend chronologisch aufgelistet:

Sätze

G. A. Dirac (1952), der historische Ausgangspunkt der Entdeckung einer ganzen Reihe von Bedingungen:

Jeder Graph $G\!$ mit mindestens Minimalgrad $\frac{n}{2}$ hat einen Hamiltonkreis.

W. T. Tutte (1956):

Jeder 4-zusammenhängende planare (oder plättbare) Graph hat einen Hamiltonkreis.

Ø. Ore (1960):

Ist die Summe des Grades (oder Valenz) zweier nicht-adjazenter Knoten mindestens $n\!$, so ist $G\!$ hamiltonsch.

Ø. Ore (1960):

Ist die Summe der Grade zweier nicht-adjazenter Knoten $x,y\!$ mindestens $n\!$, so gilt: $G+\{x,y\}\!$ hamiltonsch $\Rightarrow G$ hamiltonsch.

L. Pósa (1962) mit einer Verallgemeinerung früherer Ergebnisse von G. A. Dirac und Ø. Ore:

Wenn für jedes $p\!$, $1\leq p<\frac{n-1}{2}$, die Anzahl der Knoten von Grad $\leq p$ kleiner als $p\!$ und für ungerade $n\!$, die Anzahl der Knoten von Grad $\leq \frac{n-1}{2}$ nicht größer als $\frac{n-1}{2}$ gilt, so ist $G\!$ hamiltonsch.

V. Chvátal (1972):

Ein Tupel $(a_{1},...,a_{n})\!$ natürlicher Zahlen mit $a_{1}\leq...\leq a_{n}<n$ ist genau dann hamiltonsch, wenn für jedes $i<\frac{n}{2}$ gilt: $a_{i}\leq i \Rightarrow a_{n-i}\geq n-i$.

V. Chvátal & P. Erdős (1972):

Ist $G\!$ k-zusammenhängend und die Mächtigkeit jeder Menge unabhängiger Knoten aus $G\!$ $\leq k$, so ist $G\!$ hamiltonsch.

H. Fleischner (1974):

Ist $G\!$ 2-zusammenhängend, so hat $G^2\!$ einen Hamiltonkreis.

J. A. Bondy & V. Chvátal (1976):

$G\!$ ist genau dann hamiltonsch, wenn sein Hamiltonabschluss hamiltonsch ist.

Weitere hinreichende Eigenschaften

• Jeder vollständige Graph mit $n\geq 3$ ist hamiltonsch.
• $G\!$ ist hamiltonsch, falls $G\!$ Kantengraph eines Eulerschen oder hamiltonschen Graphen ist.
• $G\!$ ist genau dann hamiltonsch, wenn $G\!$ einen Teilgraphen (oder Subgraph) - bei dem nur Kanten entfernt wurden - besitzt, der Kantengraph eines Eulerschen oder hamiltonschen Graphen ist.
• Jeder panzyklische Graph ist hamiltonsch.

Notwendige Kriterien

Nach der Vorstellung hinreichender Bedingungen nun eine Auswahl notwendiger Kriterien für die Existenz von Hamiltonkreisen. Besitzt $G\!$ einen Hamiltonkreis, so gilt:

• $G\!$ besitzt keinen Schnittknoten,
• $G\!$ besitzt keine Brücke,
• der Blockgraph von $G\!$ ist ein isolierter Knoten,
• $G\!$ besitzt einen 2-Faktor,
• $G\!$ ist 2-zusammenhängend,
• der Minimalgrad ist mindestens 2 und
• der Durchmesser von $G\!$ ist höchstens $\frac{n}{2}$.

Vermutungen

In diesem Zusammenhang wurden diese wichtigen - nicht allgemein gelösten - Vermutungen geäußert:

D. W. Barnette (1969):

Jeder 3-zusammenhängende bipartite kubische planare Graph ist hamiltonsch.

P. Seymour (1974):

Ist der Minimalgrad von $G\!$ $\delta(G)\geq \frac{k}{k+1}n$, so hat $G\!$ einen Hamiltonkreis $H\!$ mit $H^k \subseteq G$.
Für $k=1\!$ entspricht dies dem Satz von G. A. Dirac, 1952, (siehe oben).
Die Aussage für $k=2\!$ war bereits 1963 von L. Pósa vermutet worden und wurde 1996 für hinreichend große $n\!$ von J. Komlós, G. N. Sárközy & E. Szemerédi bewiesen.

Siehe auch

• Eulerkreisproblem - ähnliches Problem, bei dem alle Kanten statt Knoten durchlaufen werden müssen

Weblinks

• Hamiltonkreis-Applet der Martin-Luther-Universität Halle-Wittenberg
• Eric W. Weisstein. „Hamiltonian Circuit.“ From MathWorld--A Wolfram Web Resource. (Englisch)
• The Hamiltonian Page (G. Gutin & P. Moscato) (Englisch)
• Puzzlemuseum: Hamiltons Spiele „The Icosian Game“ und „Traveller's Dodecahedron“ (Englisch)