Hamilton-Pfad – Wikipedia

before-content-x4

Ein Hamilton-Zyklus um ein Netzwerk von sechs Eckpunkten

Im mathematischen Bereich der Graphentheorie a Hamilton-Pfad (oder rückverfolgbarer Pfad) ist ein Pfad in einem ungerichteten oder gerichteten Diagramm, der jeden Scheitelpunkt genau einmal besucht. EIN Hamilton-Zyklus (oder Hamiltonsche Schaltung) ist ein Hamilton-Pfad, der ein Zyklus ist. Das Bestimmen, ob solche Pfade und Zyklen in Graphen existieren, ist das Hamilton-Pfadproblem, das NP-vollständig ist.

Hamiltonsche Pfade und Zyklen sind nach William Rowan Hamilton benannt, der das ikosianische Spiel erfand, das heute auch als bekannt ist Hamiltons RätselDies beinhaltet das Auffinden eines Hamilton-Zyklus im Randgraphen des Dodekaeders. Hamilton löste dieses Problem mit dem Ikosianischen Kalkül, einer algebraischen Struktur, die auf Wurzeln der Einheit basiert und viele Ähnlichkeiten mit den Quaternionen aufweist (ebenfalls von Hamilton erfunden). Diese Lösung lässt sich nicht auf beliebige Graphen verallgemeinern.

Obwohl sie nach Hamilton benannt wurden, waren Hamilton-Zyklen in Polyedern auch ein Jahr zuvor von Thomas Kirkman untersucht worden, der insbesondere ein Beispiel für ein Polyeder ohne Hamilton-Zyklen gab.[1] Noch früher waren Hamiltonsche Zyklen und Pfade in der Rittergrafik des Schachbretts, der Rittertour, im 9. Jahrhundert von Rudrata in der indischen Mathematik und etwa zur gleichen Zeit in der islamischen Mathematik von al-Adli ar-Rumi studiert worden. Im Europa des 18. Jahrhunderts wurden Rittertouren von Abraham de Moivre und Leonhard Euler veröffentlicht.[2]

Definitionen[edit]

EIN Hamilton-Pfad oder rückverfolgbarer Pfad ist ein Pfad, der jeden Scheitelpunkt des Diagramms genau einmal besucht. Ein Graph, der einen Hamilton-Pfad enthält, heißt a rückverfolgbares Diagramm. Ein Graph ist Hamiltonian verbunden Wenn für jedes Scheitelpunktpaar ein Hamilton-Pfad zwischen den beiden Scheitelpunkten besteht.

EIN Hamilton-Zyklus, Hamiltonsche Schaltung, Vertex-Tour oder Grafikzyklus ist ein Zyklus, der jeden Scheitelpunkt genau einmal besucht. Ein Graph, der einen Hamilton-Zyklus enthält, heißt a Hamilton-Graph.

Ähnliche Begriffe können für definiert werden gerichtete Graphenwobei jede Kante (Bogen) eines Pfades oder Zyklus nur in einer einzigen Richtung verfolgt werden kann (dh die Eckpunkte sind mit Pfeilen verbunden und die Kanten sind “Schwanz-zu-Kopf” verfolgt).

Eine Hamilton-Zerlegung ist eine Kantenzerlegung eines Graphen in Hamilton-Schaltungen.

EIN Hamilton Labyrinth ist eine Art logisches Puzzle, bei dem das Ziel darin besteht, den eindeutigen Hamilton-Zyklus in einem bestimmten Diagramm zu finden.[3][4]

Beispiele[edit]

Das obige als zweidimensionales planares Diagramm

Eigenschaften[edit]

Jeder Hamilton-Zyklus kann durch Entfernen einer seiner Kanten in einen Hamilton-Pfad konvertiert werden. Ein Hamilton-Pfad kann jedoch nur dann auf den Hamilton-Zyklus erweitert werden, wenn seine Endpunkte benachbart sind.

Alle Hamilton-Diagramme sind zweifach verbunden, aber ein zweifach verbundenes Diagramm muss kein Hamilton-Diagramm sein (siehe z. B. das Petersen-Diagramm).[6]

Ein Eulerscher Graph G (ein zusammenhängender Graph, in dem jeder Scheitelpunkt einen geraden Grad hat) hat notwendigerweise eine Euler-Tour, einen geschlossenen Weg, der durch jede Kante von verläuft G genau einmal. Diese Tour entspricht einem Hamilton-Zyklus im Liniendiagramm L.((G), also ist der Liniendiagramm jedes Eulerschen Graphen Hamiltonian. Liniendiagramme können andere Hamilton-Zyklen aufweisen, die nicht den Euler-Touren entsprechen, insbesondere das Liniendiagramm L.((G) jedes Hamiltonschen Graphen G ist selbst Hamiltonian, unabhängig davon, ob der Graph G ist Eulerianer.[7]

Ein Turnier (mit mehr als zwei Eckpunkten) ist genau dann Hamiltonian, wenn es stark verbunden ist.

Die Anzahl der verschiedenen Hamilton-Zyklen in einem vollständigen ungerichteten Diagramm auf n Eckpunkte ist ((n – 1)! / 2 und in einem vollständigen gerichteten Diagramm auf n Eckpunkte ist ((n – 1)!. Diese Zählungen setzen voraus, dass Zyklen, die bis auf ihren Startpunkt gleich sind, nicht separat gezählt werden.

Bondy-Chvátal-Theorem[edit]

Die beste Vertex-Grad-Charakterisierung von Hamilton-Graphen wurde 1972 durch das Bondy-Chvátal-Theorem geliefert, das frühere Ergebnisse von GA Dirac (1952) und Øystein Ore verallgemeinert. Sowohl Diracs als auch Ore-Theoreme können auch aus Pósas Theorem (1962) abgeleitet werden. Die Hamiltonizität wurde in Bezug auf verschiedene Parameter wie Graphendichte, Zähigkeit, verbotene Teilgraphen und Abstand unter anderen Parametern umfassend untersucht.[8] Die Sätze von Dirac und Ore besagen grundsätzlich, dass ein Graph Hamilton ist, wenn dies der Fall ist genug Kanten.

Das Bondy-Chvátal-Theorem arbeitet auf der Schließung cl (G) eines Graphen G mit n Scheitelpunkte, die durch wiederholtes Hinzufügen einer neuen Kante erhalten werden uv Verbinden eines nicht benachbarten Scheitelpunktpaares u und v mit Grad (v) + deg (u) ≥ n bis keine Paare mehr mit dieser Eigenschaft gefunden werden können.

Bondy-Chvátal-Theorem (1976). Ein Graph ist genau dann Hamiltonian, wenn sein Abschluss Hamiltonian ist.

Da vollständige Graphen Hamilton-Graphen sind, sind alle Graphen, deren Abschluss vollständig ist, Hamilton-Graphen. Dies ist der Inhalt der folgenden früheren Sätze von Dirac und Ore.

Diracs Theorem (1952). Ein einfaches Diagramm mit n Eckpunkte (n ≥ 3) ist Hamilton, wenn jeder Scheitelpunkt einen Grad hat
Erzsatz (1960). Ein einfaches Diagramm mit n Eckpunkte (n ≥ 3) ist Hamilton, wenn für jedes Paar nicht benachbarter Eckpunkte die Summe ihrer Grade ist n oder größer.

Die folgenden Sätze können als gerichtete Versionen angesehen werden:

Ghouila-Houiri (1960). Ein stark verbundener einfacher gerichteter Graph mit n Scheitelpunkte sind Hamilton-Werte, wenn jeder Scheitelpunkt einen vollen Grad größer oder gleich hat n.
Meyniel (1973). Ein stark verbundener einfacher gerichteter Graph mit n Scheitelpunkte sind Hamilton-Werte, wenn die Summe der vollen Grade jedes Paares unterschiedlicher nicht benachbarter Scheitelpunkte größer oder gleich ist 2n – 1.

Die Anzahl der Scheitelpunkte muss verdoppelt werden, da jede ungerichtete Kante zwei gerichteten Bögen entspricht und somit der Grad eines Scheitelpunkts im gerichteten Graphen doppelt so hoch ist wie der Grad im ungerichteten Graphen.

Rahman-Kaykobad (2005). Ein einfaches Diagramm mit n Scheitelpunkte haben einen Hamilton-Pfad, wenn für jedes nicht benachbarte Scheitelpunktpaar die Summe ihrer Grade und ihrer kürzesten Pfadlänge größer als ist n.[9]

Der obige Satz kann nur die Existenz eines Hamilton-Pfades in einem Graphen und nicht eines Hamilton-Zyklus erkennen.

Viele dieser Ergebnisse enthalten Analoga für ausgeglichene zweigeteilte Graphen, bei denen die Scheitelpunktgrade eher mit der Anzahl der Scheitelpunkte auf einer einzelnen Seite der Bipartition als mit der Anzahl der Scheitelpunkte im gesamten Graphen verglichen werden.[10]

Existenz von Hamilton-Zyklen in planaren Graphen[edit]

Satz (Whitney, 1931)
Eine 4-verbundene planare Triangulation hat einen Hamilton-Zyklus.
Satz (Tutte, 1956)
Ein 4-verbundener planarer Graph hat einen Hamilton-Zyklus.

Das Hamiltonsche Zykluspolynom[edit]

Eine algebraische Darstellung der Hamilton-Zyklen eines gegebenen gewichteten Digraphen (dessen Bögen Gewichte aus einem bestimmten Grundfeld zugewiesen werden) ist das Hamilton-Zykluspolynom seiner gewichteten Adjazenzmatrix, definiert als die Summe der Produkte der Bogengewichte der Hamilton-Zyklen des Digraphen . Dieses Polynom ist als Funktion in den Bogengewichten nicht genau dann gleich Null, wenn der Digraph Hamilton ist. Die Beziehung zwischen der rechnerischen Komplexität der Berechnung und der Berechnung der permanenten Daten wurde in Kogan (1996) gezeigt.

Siehe auch[edit]

  • Barnets Vermutung, ein offenes Problem der Hamiltonizität kubischer zweigliedriger polyedrischer Graphen
  • Eulerscher Pfad, ein Pfad durch alle Kanten in einem Diagramm
  • Fleischners Theorem über Hamiltonsche Quadrate von Graphen
  • Grauer Code
  • Grinbergs Theorem, das eine notwendige Bedingung für planare Graphen liefert, um einen Hamilton-Zyklus zu haben
  • Hamilton-Pfadproblem, das Rechenproblem beim Finden von Hamilton-Pfaden
  • Hypohamiltonianischer Graph, ein nicht-Hamiltonianischer Graph, in dem jeder durch Scheitelpunkte gelöschte Untergraph Hamiltonian ist
  • Knight’s Tour, ein Hamilton-Zyklus in der Rittergrafik
  • LCF-Notation für kubische Hamilton-Graphen.
  • Lovász vermutet, dass vertextransitive Graphen Hamilton-Graphen sind
  • Pancyclic Graph, Graphen mit Zyklen aller Längen einschließlich eines Hamiltonschen Zyklus
  • Sieben Brücken von Königsberg
  • Kurzheitsexponent, ein numerisches Maß dafür, wie weit die Graphen in einer Familie von Hamilton entfernt sein können
  • Snake-in-the-Box, der längste induzierte Pfad in einem Hypercube
  • Steinhaus-Johnson-Trotter-Algorithmus zum Auffinden eines Hamilton-Pfades in einem Permutoeder
  • Subhamiltonian Graph, ein Subgraph eines planaren Hamiltonian Graph
  • Taits Vermutung (jetzt als falsch bekannt), dass 3-reguläre polyedrische Graphen Hamilton-Graphen sind
  • Problem mit reisenden Verkäufern
  1. ^ Biggs, NL (1981), “TP Kirkman, Mathematiker”, Das Bulletin der London Mathematical Society, 13 (2): 97–120, doi:10.1112 / blms / 13.2.97, HERR 0608093.
  2. ^ Watkins, John J. (2004), “Kapitel 2: Knight’s Tours”, Auf ganzer Linie: Die Mathematik der Schachbrettprobleme, Princeton University Press, S. 25–38, ISBN 978-0-691-15498-5.
  3. ^ de Ruiter, Johan (2017). Hamilton Mazes – Der Leitfaden für Anfänger.
  4. ^ Friedman, Erich (2009). “Hamiltonian Mazes”. Erichs Puzzle Palace. Archiviert vom Original am 16. April 2016. Abgerufen 27. Mai 2017.
  5. ^ Gardner, M. “Mathematische Spiele: Über die bemerkenswerte Ähnlichkeit zwischen dem Icosianischen Spiel und den Türmen von Hanoi.” Sci. Amer. 196, 150–156, Mai 1957
  6. ^ Eric Weinstein. “Biconnected Graph”. Wolfram MathWorld.
  7. ^ Balakrishnan, R.; Ranganathan, K. (2012), “Corollary 6.5.5”, Ein Lehrbuch der Graphentheorie, Springer, p. 134, ISBN 9781461445296.
  8. ^ Gould, Ronald J. (8. Juli 2002). “Fortschritte beim Hamilton-Problem – Eine Umfrage” (PDF). Emory University. Abgerufen 2012-12-10.
  9. ^ Rahman, MS; Kaykobad, M. (April 2005). “Auf Hamilton-Zyklen und Hamilton-Pfaden”. Informationsverarbeitungsbriefe. 94: 37–41. doi:10.1016 / j.ipl.2004.12.002.
  10. ^ Moon, J.; Moser, L. (1963), “On Hamiltonian bipartite graphs”, Israel Journal of Mathematics, 1 (3): 163–165, doi:10.1007 / BF02759704, HERR 0161332

Verweise[edit]

  • Berge, Claude; Ghouila-Houiri, A. (1962), Programmier-, Spiele- und Transportnetze, New York: Sons, Inc.
  • DeLeon, Melissa (2000), “Eine Studie über ausreichende Bedingungen für Hamilton-Zyklen” (PDF), Rose-Hulman Undergraduate Math Journal, 1 (1), archiviert von das Original (PDF) am 22.12.2012abgerufen 2005-11-28.
  • Dirac, GA (1952), “Einige Sätze über abstrakte Graphen”, Verfahren der London Mathematical Society, 3rd Ser., 2: 69–81, doi:10.1112 / plms / s3-2.1.69, HERR 0047308.
  • Hamilton, William Rowan (1856), “Memorandum über ein neues System von Wurzeln der Einheit”, Philosophisches Magazin, 12: 446.
  • Hamilton, William Rowan (1858), “Bericht über den Icosian Calculus”, Verfahren der Royal Irish Academy, 6: 415–416.
  • Meyniel, M. (1973), “Une Bedingung genügt Existenz ‘d’un Schaltung hamiltonien dans un graphe orienté”, Zeitschrift für kombinatorische Theorie, Serie B, 14 (2): 137–147, doi:10.1016 / 0095-8956 (73) 90057-9, HERR 0317997.
  • Ore, Øystein (1960), “Note on Hamilton Circuits”, The American Mathematical Monthly, 67 (1): 55, doi:10.2307 / 2308928, JSTOR 2308928, HERR 0118683.
  • Pósa, L. (1962), “Ein Satz über Hamilton-Linien”, Magyar Tud. Akad. Matte. Kutató Int. Közl., 7: 225–226, MR 0184876.
  • Whitney, Hassler (1931), “Ein Satz über Graphen”, Annalen der Mathematik, Zweite Serie, 32 (2): 378–390, doi:10.2307 / 1968197, JSTOR 1968197, HERR 1503003.
  • Tutte, WT (1956), “Ein Satz über planare Graphen”, Trans. Amer. Mathematik. Soc., 82: 99–116, doi:10.1090 / s0002-9947-1956-0081471-8.
  • Kogan, Grigoriy (1996), “Berechnen von Permanenten über Felder der Eigenschaft 3: Wo und warum wird es schwierig”, 37. jährliches Symposium über Grundlagen der Informatik (FOCS ’96): 108–114, doi:10.1109 / SFCS.1996.548469, ISBN 0-8186-7594-2

Externe Links[edit]

after-content-x4