Hamiltonkreisproblem

Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Die Frage, ob ein solcher Kreis in einem gegebenen Graphen existiert, ist ein wichtiges Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem ein Kreis gesucht wird, der alle Kanten genau einmal durchläuft, ist das Hamiltonkreisproblem NP-vollständig.

Man unterscheidet das Gerichtete Hamiltonkreisproblem in gerichteten Graphen und das Ungerichtete Hamiltonkreisproblem in ungerichteten Graphen. Eine Verallgemeinerung des Hamiltonkreisproblems ist das Problem des Handlungsreisenden, bei dem nach einem kürzesten Hamiltonkreis in einem 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 M. 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$ heißt 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 heißt $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 kleiner gleich $d$ haben. Offenbar gilt $G=G^{1}\subseteq G^{2}\subseteq G^{3}\subseteq \ldots$.

Ein beliebiges Tupel $(a_{1},\dotsc ,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},\dotsc ,d_{n})$ heißt dabei punktweise größer als $(a_{1},\dotsc ,a_{n})$, wenn $d_{i}\geq a_{i}$ gilt für alle $i$.

Ein Graph $G$ heißt hypohamiltonsch, wenn er keinen hamiltonschen Kreis besitzt, aber zu jedem seiner Knoten ein Kreis existiert, der alle anderen Knoten enthält.

Der Hamiltonabschluss eines Graphen $G$ ist der Obergraph von $G$ mit identischer Knotenmenge und zusätzlich iterativ eingefügten Kanten, die nichtadjazente Knoten mit Gradsumme größer gleich $n$ miteinander verbinden, solange dies möglich ist. Der Hamiltonabschluss eines Graphen ist eindeutig.

Eigenschaften

Jeder Hamiltonkreis kann durch Entfernen einer seiner Kanten in einen Hamiltonweg umgewandelt werden. Ein Hamiltonweg kann jedoch nur dann zu einem Hamiltonkreis erweitert werden, wenn seine Endknoten benachbart sind.

Alle hamiltonschen Graphen sind 2-zusammenhängend, aber ein 2-zusammenhängender Graph muss nicht hamiltonsch sein, zum Beispiel der Petersen-Graph.

Ein eulerscher Graph, also ein zusammenhängender Graph, in dem jeder Knoten einen geraden Grad hat, besitzt notwendigerweise einen Eulerkreis, wobei der geschlossene Weg genau einmal durch jede Kante verläuft. Dieser Weg entspricht einem Hamiltonkreis im zugehörigen Kantengraphen, sodass der Kantengraph jedes eulerschen Graphen ein hamiltonscher Graph ist. Kantengraphen können andere Hamiltonkreise haben, die nicht den Eulerkreisen entsprechen, und insbesondere ist der Kantengraph jedes hamiltonschen Graphen selbst hamiltonsch, unabhängig davon, ob der Graph ein eulerscher Graph ist.

Ein Turniergraph mit mehr als zwei Knoten ist genau dann ein hamiltonscher Graph, wenn er stark zusammenhängend ist.

Die Anzahl der verschiedenen Hamiltonkreise in einem vollständigen ungerichteten Graphen mit $n$ Knoten beträgt ${\tfrac {1}{2}}\cdot (n-1)!$ und in einem vollständigen gerichteten Graphen mit $n$ Knoten $(n-1)!$. Dabei werden Hamiltonkreise, die bis auf ihren Startknoten gleich sind, nicht mehrfach gezählt.

Sätze über Hamiltonkreise

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 einfache Graph $G$ mit Minimalgrad mindestens ${\tfrac {n}{2}}$ hat einen Hamiltonkreis.

• W. T. Tutte (1956): Jeder 4-zusammenhängende planare Graph hat einen Hamiltonkreis.

• Ø. Ore (1960): Ist die Summe der Grade je zweier nicht-adjazenter Knoten eines einfachen Graphen mindestens $n$, so ist $G$ hamiltonsch.

• L. Pósa (1962) mit einer Verallgemeinerung früherer Ergebnisse von G. A. Dirac und Ø. Ore: Sei $G$ ein einfacher Graph mit $n\geq 3$ Knoten. Es gelte außerdem für alle natürlichen Zahlen $k<{\tfrac {n-1}{2}}$, dass die Anzahl der Knoten mit Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v\leq k} kleiner als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} ist. Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} ungerade ist, sei die Anzahl aller Knoten mit Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v\leq\tfrac{n-1}{2}} kleiner oder gleich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{n-1}{2}} . Dann besitzt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} einen Hamiltonkreis.

• P. Erdős (1962): Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G^n_l(k)} ein einfacher Graph mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Knoten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l} Kanten. Jeder Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G^n_l(k)} habe einen Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v(P)\geq k} . Es gelte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1\leq k <\tfrac{n}{2}} und es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l(k,n)=1+\max_{k\leq t<\tfrac{n}{2}} \binom {n-t}{2}+t^2} . Dann gilt:
  • 1. Jeder Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G^n_l(k)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l\geq l(k,n)} besitzt einen Hamiltonkreis.
  • 2. Es existiert ein Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G^n_{l(k,n)-1}(k)} , der keinen Hamiltonkreis besitzt.

• V. Chvátal (1972): Ein Tupel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a_{1},\dotsc,a_{n})} natürlicher Zahlen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{1}\leq\cdots\leq a_{n}<n} ist genau dann hamiltonsch, wenn für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i<\tfrac{n}{2}} gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{i}\leq i \Rightarrow a_{n-i}\geq n-i} .

• V. Chvátal und P. Erdős (1972): Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} k-zusammenhängend und die Mächtigkeit jeder Menge unabhängiger Knoten aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \leq k} , so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} hamiltonsch.

• H. Fleischner (1974): Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} 2-zusammenhängend, so hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G^2} einen Hamiltonkreis.

• J. A. Bondy und V. Chvátal (1976): Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist genau dann hamiltonsch, wenn sein Hamiltonabschluss hamiltonsch ist.

Weitere hinreichende Eigenschaften

Ein Graph ist hamiltonsch, wenn er

• ein vollständiger Graph mit mindestens drei Knoten ist.
• Kantengraph eines Eulerschen oder hamiltonschen Graphen ist.
• einen Teilgraphen, bei dem nur Kanten entfernt wurden, besitzt, der Kantengraph eines Eulerschen oder hamiltonschen Graphen ist.
• ein panzyklischer Graph ist.

Notwendige Eigenschaften

Hat ein Graph einen Hamiltonkreis, dann

• hat er keinen Schnittknoten.
• hat er keine Brücke.
• ist sein Blockgraph ein isolierter Knoten.
• hat er einen 2-Faktor.
• ist er 2-zusammenhängend.
• ist sein Minimalgrad mindestens 2.
• ist sein Durchmesser höchstens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{n}{2}} .
• ist er 1-tough, d. h. für jede nicht-leere Menge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} Knoten gilt, dass der Graph ohne diese Knoten höchstens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} Zusammenhangskomponenten besitzt.
• ist path-tough, d. h. für jeden Knoten gilt, dass der Graph ohne diesen Knoten einen Hamiltonschen Weg besitzt, das ist ein Weg, der alle Knoten des Graphen enthält.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta(G)\geq \tfrac{k}{k+1}n} , so hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} einen Hamiltonkreis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H^k \subseteq G} . Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k=1} entspricht dies dem Satz von G. A. Dirac, 1952, (siehe oben).
  Die Aussage für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k=2} war bereits 1963 von L. Pósa vermutet worden und wurde 1996 für hinreichend große Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} von J. Komlós, G. N. Sárközy & E. Szemerédi bewiesen.

Siehe auch

• Ein Spezialfall des Hamiltonkreises ist das sogenannte Springerproblem.
• Die Gray-Codes sind die Lösungen des Hamiltonkreisproblems für einen Hyperwürfel.

Weblinks

Commons: Hamiltonian paths – Sammlung von Bildern, Videos und Audiodateien

• Eric W. Weisstein. „Hamiltonian Cycle.“ From MathWorld--A Wolfram Web Resource (englisch)
• Puzzlemuseum: Hamiltons Spiele „The Icosian Game“ und „Traveller's Dodecahedron“ (englisch)

Karps 21 NP-vollständige Probleme

Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt