Hamiltonkreisproblem - LinkFang.de





Hamiltonkreisproblem


Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält. Ob ein solcher Kreis in einem gegebenen Graph besteht, ist ein fundamentales Problem der Graphentheorie. Im Gegensatz zum leicht lösbaren Eulerkreisproblem, bei dem alle Kanten genau einmal durchlaufen werden, ist das Hamiltonkreisproblem NP-vollständig.

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

Geschichte

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 [math]G=(V,E)[/math] ein Graph mit [math]|V|=n[/math] Knoten (oder Ecken) und [math]|E|=m[/math] Kanten.

[math]G[/math] heißt hamiltonsch, wenn er einen Hamiltonkreis zulässt, d. h., wenn es einen Kreis in [math]G[/math] gibt, der alle Knoten aus [math]V[/math] enthält. Ein Hamiltonpfad ist ein Pfad in [math]G[/math], der alle Knoten aus [math]V[/math] enthält. Hat [math]G[/math] Hamiltonpfade, jedoch keinen Hamiltonkreis, so heißt [math]G[/math] 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 benachbart sind, wenn sie in [math]G[/math] einen Abstand (oder Distanz) 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ü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 (oder Hülle; [math]n[/math]-Hülle) eines Graphen [math]G[/math] ist der Obergraph von [math]G[/math] mit identischer Knotenmenge und zusätzlich iterativ eingefügten Kanten, die nichtadjazente (oder nichtbenachbarte; nichtverbundene) Knoten mit Gradsumme größer gleich [math]n[/math] miteinander verbinden, solange dies möglich ist. Der Hamiltonabschluss eines Graphen ist eindeutig.

Wichtige Aussagen und Sätze

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

  • G. A. Dirac (1952), der historische Ausgangspunkt der Entdeckung einer ganzen Reihe von Bedingungen: Jeder einfache Graph [math]G[/math] mit Minimalgrad mindestens [math]\tfrac{n}{2}[/math] hat einen Hamiltonkreis. [1]
  • Ø. 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. [1]
  • 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. Es gelte außerdem für alle natürlichen Zahlen [math]k\lt\tfrac{n-1}{2}[/math], dass die Anzahl der Knoten mit 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. [1]
  • 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 \lt\tfrac{n}{2}[/math] und es sei [math]l(k,n)=1+\max_{k\leq t\lt\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. [1]
  • V. Chvátal (1972): Ein Tupel [math](a_{1},\dotsc,a_{n})[/math] natürlicher Zahlen mit [math]a_{1}\leq\cdots\leq a_{n}\ltn[/math] ist genau dann hamiltonsch, wenn für jedes [math]i\lt\tfrac{n}{2}[/math] gilt: [math]a_{i}\leq i \Rightarrow a_{n-i}\geq n-i[/math].
  • V. Chvátal und P. Erdős (1972): Ist [math]G[/math] k-zusammenhängend und die Mächtigkeit jeder Menge unabhängiger Knoten aus [math]G[/math] [math]\leq k[/math], so ist [math]G[/math] hamiltonsch.
  • H. Fleischner (1974): Ist [math]G[/math] 2-zusammenhängend, so hat [math]G^2[/math] einen Hamiltonkreis.
  • J. A. Bondy und V. Chvátal (1976): [math]G[/math] ist genau dann hamiltonsch, wenn sein Hamiltonabschluss hamiltonsch ist.

Weitere hinreichende Eigenschaften

  • Jeder vollständige Graph mit [math]n\geq 3[/math] ist hamiltonsch.
  • [math]G[/math] ist hamiltonsch, falls [math]G[/math] Kantengraph eines Eulerschen oder hamiltonschen Graphen ist.
  • [math]G[/math] ist genau dann hamiltonsch, wenn [math]G[/math] 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 [math]G[/math] einen Hamiltonkreis, so gilt:

  • [math]G[/math] besitzt keinen Schnittknoten,
  • [math]G[/math] besitzt keine Brücke,
  • der Blockgraph von [math]G[/math] ist ein isolierter Knoten,
  • [math]G[/math] besitzt einen 2-Faktor,
  • [math]G[/math] ist 2-zusammenhängend,
  • der Minimalgrad ist mindestens 2,
  • der Durchmesser von [math]G[/math] ist höchstens [math]\tfrac{n}{2}[/math],
  • [math]G[/math] ist 1-tough, d. h. für jede nicht-leere Menge von [math]s[/math] Knoten gilt, dass der Graph ohne diese Knoten höchstens [math]s[/math] Zusammenhangskomponenten besitzt, und
  • [math]G[/math] 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:

  • 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).
    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 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.

Einzelnachweise

  1. 1,0 1,1 1,2 1,3 Horst Sachs: Einführung in die Theorie der endlichen Graphen (Band 1). 1. Auflage. BSB B.G. Teubner Verlagsgesellschaft, Leipzig 1970.

Weblinks


Kategorien: Komplexitätstheorie | Problem (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Hamiltonkreisproblem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.