WikiDer > Hamilton-Pfad
EIN Hamilton-Pfad ist ein Weg entlang von Knoten in a Anzahl wobei jeder Knoten genau einmal auf dem Pfad liegt. Ein geschlossener Hamilton-Pfad wird als Hamilton-Zyklus oder Hamilton-Kreis bezeichnet. Der Name Hamiltonpad kommt von der irischMathematiker Herr William Rowan Hamilton (1805-1865).
Ein Graph, der einen Hamiltonkreis enthält, heißt a Hamiltonischer Graf oder Hamilton zählen. Jeder Anzahl der Durchgänge ist hamiltonisch, wie jeder volle Zählung mit 3 oder mehr Knoten.
Eine Zählung ist Hamilton-nahe oder Hamilton-verbunden wie für jedes Paar unterschiedlicher Knoten Sie und v Es gibt einen Hamilton-Pfad mit Endpunkten Sie und v. Der aus einem einzelnen Knoten bestehende Graph ist trivial Hamilton-verbunden.
Die Bestimmung, ob in einem gegebenen Graphen ein Hamilton-Weg oder ein Hamilton-Kreis existiert, der gerichtet oder ungerichtet sein kann, ist ein grundlegendes Problem in der Graphentheorie. Der Hamiltonpfad ist ein Sonderfall des case Probleme mit dem Handlungsreisenden; Dies wird erreicht, indem der Abstand zwischen zwei Städten gleich eins gesetzt wird, wenn sie benachbart sind, und gleich zwei, wenn sie nicht benachbart sind. Wenn die zurückgelegte Entfernung der Anzahl der Städte entspricht, ist die Route ein Hamilton-Pfad. Wenn kein Hamilton-Pfad vorhanden ist, ist die kürzeste Route länger.
Taits Vermutung
Peter Tait formulierte 1884 folgendes: Verdacht:
"Alle 3 verbunden, planar, kubischer Graph enthält einen Hamiltonkreis."
(Ein kubischer Graph ist ein Graph, bei dem jeder Knoten mit drei anderen Knoten verbunden ist; ein 3-zusammenhängender Graph ist ein Graph, aus dem mindestens 3 Knoten entfernt werden müssen, um einen nicht zusammenhängenden Graphen zu hinterlassen).
Diese Vermutung wurde 1946 von . widerlegt William Tutte,[1] der ein Gegenbeispiel mit 46 Knoten und 69 Seiten konstruierte. Er beobachtete, dass, wenn ein Graph das folgende Fragment enthält:
jeder Hamiltonkreis muss über den oberen Knoten und einen der unteren beiden in das Fragment ein- und austreten; es kann nicht durch einen der unteren Knoten eintreten und durch den anderen austreten und dennoch das ganze Fragment beeinflussen. Wenn nun drei dieser Fragmente wie folgt in einem Diagramm kombiniert werden:
dann müsste eine Hamilton-Schaltung den zentralen Knoten auf den drei Seiten umfahren, was unmöglich ist.
Holton und McKay[2] bewiesen 1988, dass die kleinsten 3-zusammenhängenden kubisch-planaren Graphen ohne Hamiltonkreis 38 Knoten haben. Solche kleinsten Gegenbeispiele der Tait-Vermutung wurden unabhängig voneinander um 1965 von Joshua Lederberg, David Barnette und Juray Bosák gefunden.
Satz von Tutte
William Tutte bewies 1946, dass jeder 4-zusammenhängende planare Graph (mit mindestens zwei Seiten) einen Hamiltonkreis hat.[3]
Satz von Orec
Das Satz von Orec gibt ein ausreichende Bedingung so dass ein Graph einen Hamilton-Pfad hat, was bedeutet, dass ein Graph mit "ausreichend vielen Seiten" einen Hamilton-Pfad hat.
Siehe auch
Quellen, Anmerkungen und/oder Verweise
|