2003:D8:3F14:DE00:E9E4:A139:CE4C:8852 am 4. Februar 2025 um 09:56 Uhr

2025-02-04T09:56:24Z

Neue Seite

Ein '''Hamiltonkreis''' ist ein geschlossener [[Weg (Graphentheorie)|Pfad]] in einem [[Graph (Graphentheorie)|Graphen]], der jeden [[Knoten (Graphentheorie)|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 [[Kante (Graphentheorie) |Kanten]] genau einmal durchläuft, ist das '''Hamiltonkreisproblem''' [[NP-Vollständigkeit|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 ==
[[Datei:Hamiltonian path 3d.svg|mini|Das Dodekaeder ist, wie alle [[Platonische Körper|platonischen Körper]], hamiltonsch.]]
[[Datei:Натурализация гамильтоновых циклов.jpg|thumb|Drei Beispiele für Hamiltonkreise auf einem 8x8 [[Gittergraph]].]]

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 [[Kante (Graphentheorie)|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 [[Eulerkreisproblem]]s 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 [[Karps 21 NP-vollständige Probleme|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 <math>G=(V,E)</math> ein Graph mit <math>|V|=n</math> [[Knoten (Graphentheorie)|Knoten]] (oder Ecken) und <math>|E|=m</math> [[Kante (Graphentheorie)|Kanten]].

<math>G</math> heißt ''hamiltonsch'', wenn er einen ''Hamiltonkreis'' zulässt, d. h., wenn es einen [[Kreis (Graphentheorie)|Kreis]] in <math>G</math> gibt, der alle Knoten aus <math>V</math> enthält. Ein ''Hamiltonpfad'' ist ein [[Weg (Graphentheorie)|Pfad]] in <math>G</math>, der alle Knoten aus <math>V</math> enthält. Hat <math>G</math> einen Hamiltonpfad, so heißt <math>G</math> ''semihamiltonsch''. (Offensichtlich ist jeder hamiltonsche Graph auch semihamiltonsch.)

Zur ''Potenz eines Graphen'': Für einen Graphen <math>G</math> und <math>d \in \mathbb{N}</math> bezeichnet <math>G^d</math> den Graphen auf <math>V</math>, bei dem zwei Knoten genau dann [[Nachbarschaft (Graphentheorie)|benachbart]] sind, wenn sie in <math>G</math> einen [[Abstand (Graphentheorie)|Abstand]] kleiner gleich <math>d</math> haben. Offenbar gilt <math>G=G^1\subseteq G^2\subseteq G^3\subseteq \ldots</math>.

Ein beliebiges Tupel <math>(a_{1},\dotsc,a_{n})</math> [[Natürliche Zahl|natürlicher Zahlen]] heißt ''hamiltonsch'', wenn jeder Graph mit <math>n</math> Knoten und punktweise größerer [[Gradsequenz]] hamiltonsch ist. Eine Gradsequenz <math>(d_{1},\dotsc,d_{n})</math> heißt dabei ''punktweise größer'' als <math>(a_{1},\dotsc,a_{n})</math>, wenn <math>d_{i}\geq a_{i}</math> gilt für alle <math>i</math>.

Ein Graph <math>G</math> 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 <math>G</math> ist der [[Teilgraph|Obergraph]] von <math>G</math> mit identischer Knotenmenge und zusätzlich [[Iteration|iterativ]] eingefügten Kanten, die nichtadjazente Knoten mit Gradsumme größer gleich <math>n</math> miteinander verbinden, solange dies möglich ist. Der Hamiltonabschluss eines Graphen ist eindeutig.

== Eigenschaften ==
Jeder Hamiltonkreis kann durch Entfernen einer seiner [[Kante (Graphentheorie)|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ängender Graph|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 (Graphentheorie)|Knoten]] einen geraden [[Grad (Graphentheorie)|Grad]] hat, besitzt notwendigerweise einen Eulerkreis, wobei der geschlossene Weg genau einmal durch jede [[Kante (Graphentheorie)|Kante]] verläuft. Dieser [[Weg (Graphentheorie)|Weg]] entspricht einem Hamiltonkreis im zugehörigen [[Kantengraph]]en, 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 (Graphentheorie)|Knoten]] ist genau dann ein hamiltonscher Graph, wenn er [[stark zusammenhängend]] ist.

Die Anzahl der verschiedenen Hamiltonkreise in einem [[Vollständiger Graph|vollständigen]] [[Ungerichteter Graph|ungerichteten Graphen]] mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] beträgt <math>\tfrac{1}{2} \cdot (n - 1)!</math> und in einem vollständigen [[Gerichteter Graph|gerichteten Graphen]] mit <math>n</math> Knoten <math>(n - 1)!</math>. Dabei werden Hamiltonkreise, die bis auf ihren Startknoten gleich sind, nicht mehrfach gezählt.

== Sätze über Hamiltonkreise ==
Welche Bedingungen an einen Graphen <math>G</math> mit <math>n\geq 3</math> haben die Existenz eines Hamiltonkreises zur Folge? Besonders wichtige Theoreme sind folgend chronologisch aufgelistet.

=== Sätze ===
* [[Gabriel Andrew Dirac|G. A. Dirac]] (1952), der historische Ausgangspunkt der Entdeckung einer ganzen Reihe von Bedingungen: Jeder [[Einfacher Graph|einfache Graph]] <math>G</math> mit [[Minimalgrad]] mindestens <math>\tfrac{n}{2}</math> hat einen Hamiltonkreis.<ref name=SachsI />

* [[William T. Tutte|W. T. Tutte]] (1956): Jeder [[k-Zusammenhang|4-zusammenhängende]] [[Planarer Graph|planare Graph]] hat einen Hamiltonkreis.

* [[Øystein Ore|Ø. Ore]] (1960): Ist die Summe der Grade je zweier nicht-adjazenter Knoten eines einfachen Graphen mindestens <math>n</math>, so ist <math>G</math> hamiltonsch.<ref name=SachsI />

* [[Lajos Pósa|L. Pósa]] (1962) mit einer Verallgemeinerung früherer Ergebnisse von G. A. Dirac und Ø. Ore: Sei <math>G</math> ein [[einfacher Graph]] mit <math>n\geq3</math> [[Knoten (Graphentheorie)|Knoten]]. Es gelte außerdem für alle natürlichen Zahlen <math>k<\tfrac{n-1}{2}</math>, dass die Anzahl der Knoten mit [[Grad (Graphentheorie)|Grad]] <math>v\leq k</math> kleiner als <math>k</math> ist. Falls <math>n</math> ungerade ist, sei die Anzahl aller Knoten mit Grad <math>v\leq\tfrac{n-1}{2}</math> kleiner oder gleich <math>\tfrac{n-1}{2}</math>. Dann besitzt <math>G</math> einen Hamiltonkreis.<ref name=SachsI />

* [[Paul Erdős|P. Erdős]] (1962): Sei <math>G^n_l(k)</math> ein einfacher Graph mit <math>n</math> Knoten und <math>l</math> Kanten. Jeder Knoten <math>P</math> in <math>G^n_l(k)</math> habe einen Grad <math>v(P)\geq k</math>. Es gelte <math>1\leq k <\tfrac{n}{2}</math> und es sei <math>l(k,n)=1+\max_{k\leq t<\tfrac{n}{2}} \binom {n-t}{2}+t^2</math>. Dann gilt:
** 1. Jeder Graph <math>G^n_l(k)</math> mit <math>l\geq l(k,n)</math> besitzt einen Hamiltonkreis.
** 2. Es existiert ein Graph <math>G^n_{l(k,n)-1}(k)</math>, der keinen Hamiltonkreis besitzt.<ref name="SachsI" />

* [[Vašek Chvátal|V. Chvátal]] (1972): Ein Tupel <math>(a_{1},\dotsc,a_{n})</math> [[Natürliche Zahl|natürlicher Zahlen]] mit <math>a_{1}\leq\cdots\leq a_{n}<n</math> ist genau dann hamiltonsch, wenn für jedes <math>i<\tfrac{n}{2}</math> gilt: <math>a_{i}\leq i \Rightarrow a_{n-i}\geq n-i</math>.

* V. Chvátal und [[Paul Erdős|P. Erdős]] (1972): Ist <math>G</math> k-[[Zusammenhängender Graph|zusammenhängend]] und die [[Mächtigkeit (Mathematik)|Mächtigkeit]] jeder Menge unabhängiger Knoten aus <math>G</math> <math>\leq k</math>, so ist <math>G</math> hamiltonsch.

* [[Herbert Fleischner|H. Fleischner]] (1974): Ist <math>G</math> 2-zusammenhängend, so hat <math>G^2</math> einen Hamiltonkreis.

* [[John A. Bondy|J. A. Bondy]] und V. Chvátal (1976): <math>G</math> ist genau dann hamiltonsch, wenn sein Hamiltonabschluss hamiltonsch ist.

=== Weitere hinreichende Eigenschaften ===
Ein [[Graph (Graphentheorie)|Graph]] ist hamiltonsch, wenn er

* ein [[vollständiger Graph]] mit mindestens drei [[Knoten (Graphentheorie)|Knoten]] ist.
* [[Kantengraph]] eines [[Eulerscher Graph|Eulerschen]] oder hamiltonschen Graphen ist.
* einen [[Teilgraph]]en, bei dem nur Kanten entfernt wurden, besitzt, der Kantengraph eines Eulerschen oder hamiltonschen Graphen ist.
* ein [[Zyklus (Graphentheorie)#Panzyklischer Graph|panzyklischer Graph]] ist.

=== Notwendige Eigenschaften ===
Hat ein [[Graph (Graphentheorie)|Graph]] einen Hamiltonkreis, dann

* hat er keinen [[Schnittknoten]].
* hat er keine [[Trenner (Graphentheorie)|Brücke]].
* ist sein [[Blockgraph]] ein [[Knoten (Graphentheorie)#Spezielle Knoten|isolierter Knoten]].
* hat er einen 2-[[Faktor (Graphentheorie)|Faktor]].
* ist er 2-[[Zusammenhängender Graph|zusammenhängend]].
* ist sein [[Minimalgrad]] mindestens 2.
* ist sein [[Durchmesser (Graphentheorie)|Durchmesser]] höchstens <math>\tfrac{n}{2}</math>.
* ist er 1-tough, d. h. für jede nicht-leere Menge von <math>s</math> [[Knoten (Graphentheorie)|Knoten]] gilt, dass der [[Graph (Graphentheorie)|Graph]] ohne diese Knoten höchstens <math>s</math> 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 – [[Vermutung (Mathematik)|Vermutung]]en geäußert:

* [[David W. Barnette|D. W. Barnette]] (1969): Jeder 3-zusammenhängende [[Bipartiter Graph|bipartite]] [[Kubischer Graph|kubische]] planare Graph ist hamiltonsch.

* [[Paul Seymour (Mathematiker)|P. Seymour]] (1974): Ist der Minimalgrad von <math>G</math> <math>\delta(G)\geq \tfrac{k}{k+1}n</math>, so hat <math>G</math> einen Hamiltonkreis <math>H</math> mit <math>H^k \subseteq G</math>. Für <math>k=1</math> entspricht dies dem Satz von G. A. Dirac, 1952, (siehe oben). <br />Die Aussage für <math>k=2</math> war bereits 1963 von L. Pósa vermutet worden und wurde 1996 für hinreichend große <math>n</math> von [[Janos Komlos|J. Komlós]], [[Gabor N. Sarkozy|G. N. Sárközy]] & [[Endre Szemerédi|E. Szemerédi]] bewiesen.

== Siehe auch ==
* Ein Spezialfall des Hamiltonkreises ist das sogenannte [[Springerproblem]].
* Die [[Gray-Code]]s sind die Lösungen des Hamiltonkreisproblems für einen Hyperwürfel.
* [[Selbstmeidender Pfad]]

== Weblinks ==
{{commonscat|Hamiltonian paths}}
* [https://mathworld.wolfram.com/HamiltonianCycle.html Eric W. Weisstein. „Hamiltonian Cycle.“ From ''MathWorld''--A Wolfram Web Resource] (englisch)
* [https://www.puzzlemuseum.com/month/picm02/200207icosian.htm Puzzlemuseum: Hamiltons Spiele „The Icosian Game“ und „Traveller's Dodecahedron“] (englisch)

== Einzelnachweise ==
<references>
<ref name=SachsI>
{{Literatur| Autor= [[Horst Sachs]] | Titel= Einführung in die Theorie der endlichen Graphen (Band 1) | Auflage= 1. | Verlag= BSB B.G. Teubner Verlagsgesellschaft | Ort= Leipzig | Jahr= 1970}}
</ref>
</references>

{{Navigationsleiste Karps 21 NP-vollständige Probleme}}

{{Normdaten|TYP=s|GND=4504638-4}}

[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Problem (Graphentheorie)]]
[[Kategorie:William Rowan Hamilton als Namensgeber]]

Hamiltonkreisproblem - Versionsgeschichte

2003:D8:3F14:DE00:E9E4:A139:CE4C:8852 am 4. Februar 2025 um 09:56 Uhr