Hamiltonscher Weg

Hamiltonscher Weg (Umgeleitet vom Bondy-Hvátal-Theorem) Zur Navigation springen Zur Suche springen Dieser Artikel handelt von der Natur der Hamiltonschen Pfade. Für die Frage nach der Existenz eines Hamilton-Pfads oder -Zyklus in einem gegebenen Graphen, siehe Hamiltonsches Pfadproblem. A Hamiltonian cycle around a network of six vertices In the mathematical field of graph theory, ein Hamiltonscher Pfad (oder nachvollziehbarer Weg) ist ein Pfad in einem ungerichteten oder gerichteten Graphen, der jeden Knoten genau einmal besucht. Ein Hamiltonkreis (oder Hamiltonkreis) ist ein Zyklus, der jeden Knoten genau einmal besucht. Ein Hamilton-Pfad, der an benachbarten Scheitelpunkten beginnt und endet, kann vervollständigt werden, indem eine weitere Kante hinzugefügt wird, um einen Hamilton-Zyklus zu bilden, und das Entfernen einer beliebigen Kante aus einem Hamilton-Zyklus erzeugt einen Hamilton-Pfad. Bestimmen, ob solche Pfade und Zyklen in Graphen existieren (das Hamilton-Pfad-Problem und das Hamilton-Zyklus-Problem) sind NP-vollständig.

Hamiltonsche Pfade und Zyklen sind nach William Rowan Hamilton benannt, der das Ikosianische Spiel erfunden hat, jetzt auch bekannt als Hamiltons Puzzle, Dazu gehört das Auffinden eines Hamilton-Zyklus im Kantengraphen des Dodekaeders. Hamilton löste dieses Problem mit dem Ikosianischen Kalkül, eine algebraische Struktur basierend auf Einheitswurzeln mit vielen Ähnlichkeiten zu den Quaternionen (ebenfalls von Hamilton erfunden). Diese Lösung lässt sich nicht auf beliebige Graphen verallgemeinern.

Obwohl er nach Hamilton benannt ist, Hamiltonsche Zyklen in Polyedern waren ein Jahr zuvor auch von Thomas Kirkman untersucht worden, wer, im Speziellen, gab ein Beispiel eines Polyeders ohne Hamiltonkreise.[1] Noch früher, Hamiltonsche Zyklen und Pfade im Springerdiagramm des Schachbretts, die Rittertour, wurde im 9. Jahrhundert in indischer Mathematik von Rudrata studiert, und ungefähr zur gleichen Zeit in der islamischen Mathematik von al-Adli ar-Rumi. Im Europa des 18. Jahrhunderts, Rittertouren wurden von Abraham de Moivre und Leonhard Euler herausgegeben.[2] Inhalt 1 Definitionen 2 Beispiele 3 Eigenschaften 4 Bondy – Grabbed Theorem 5 Existenz von Hamiltonkreisen in planaren Graphen 6 Das Polynom des Hamilton-Zyklus 7 Siehe auch 8 Anmerkungen 9 Verweise 10 External links Definitions A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. Ein Graph, der einen Hamilton-Pfad enthält, wird als verfolgbarer Graph bezeichnet. Ein Graph ist hamilton-zusammenhängend, wenn es für jedes Knotenpaar einen hamiltonschen Weg zwischen den beiden Knoten gibt.

Ein Hamiltonkreis, Hamiltonkreis, Scheitelpunkttour oder Graphenzyklus ist ein Zyklus, der jeden Scheitelpunkt genau einmal besucht. Ein Graph, der einen Hamiltonschen Kreis enthält, heißt Hamiltonscher Graph.

Ähnliche Begriffe können für gerichtete Graphen definiert werden, wo jede Kante (Bogen) eines Weges oder Zyklus kann nur in einer einzigen Richtung verfolgt werden (d.h., die Scheitelpunkte sind mit Pfeilen verbunden und die Kanten nachgezeichnet "Schwanz an Kopf").

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

Ein Hamilton-Labyrinth ist eine Art Logikpuzzle, bei dem das Ziel darin besteht, den eindeutigen Hamilton-Zyklus in einem bestimmten Diagramm zu finden.[3][4] Beispiele Orthographische Projektionen und Schlegel-Diagramme mit Hamilton-Zyklen der Ecken der fünf platonischen Körper – nur das Oktaeder hat eine Eulersche Bahn oder einen Zyklus, durch Verlängerung seines Pfades mit dem gepunkteten vte Ein vollständiger Graph mit mehr als zwei Ecken ist hamiltonsch Jeder Zyklusgraph ist hamiltonsch Jedes Turnier hat eine ungerade Anzahl von hamiltonschen Wegen (Es ist deins 1934) Jeder platonische Körper, als Graph betrachtet, ist hamiltonsch[5] Der Cayley-Graph einer endlichen Coxeter-Gruppe ist hamiltonsch (Weitere Informationen zu Hamiltonschen Pfaden in Cayley-Graphen, siehe die Lovász-Vermutung.) Cayley-Graphen auf nilpotenten Gruppen mit zyklischer Kommutator-Untergruppe sind Hamiltonian.[6] Der Flipgraph eines konvexen Polygons oder gleichwertig, der Rotationsgraph von Binärbäumen, ist hamiltonsch.[7][8] Eigenschaften Der Herschel-Graph ist der kleinstmögliche polyedrische Graph, der keinen Hamiltonkreis hat. Ein möglicher Hamilton-Pfad ist gezeigt.

Jeder Hamilton-Kreis kann in einen Hamilton-Pfad umgewandelt werden, indem eine seiner Kanten entfernt wird, Ein Hamilton-Pfad kann jedoch nur dann zu einem Hamilton-Zyklus erweitert werden, wenn seine Endpunkte benachbart sind.

Alle Hamiltonschen Graphen sind zweifach zusammenhängend, aber ein zweifach zusammenhängender Graph muss nicht hamiltonsch sein (sehen, zum Beispiel, der Petersen-Graph).[9] Ein Eulerscher Graph G (ein zusammenhängender Graph, in dem jeder Knoten einen geraden Grad hat) hat unbedingt eine Euler-Tour, ein geschlossener Spaziergang, der durch jede Kante von G genau einmal geht. Diese Tour entspricht einem Hamiltonkreis im Liniendiagramm L(G), also ist der Liniengraph jedes Eulerschen Graphen hamiltonsch. Liniendiagramme können andere Hamilton-Zyklen haben, die nicht den Euler-Touren entsprechen, und insbesondere das Liniendiagramm L(G) jedes hamiltonschen Graphen G ist selbst hamiltonsch, unabhängig davon, ob der Graph G Eulersch ist.[10] Ein Turnier (mit mehr als zwei Ecken) ist genau dann hamiltonsch, wenn es stark zusammenhängend ist.

Die Anzahl verschiedener Hamilton-Zyklen in einem vollständigen ungerichteten Graphen auf n Ecken ist (n - 1)! / 2 und in einem vollständigen gerichteten Graphen auf n Ecken ist (n - 1)!. Diese Zählungen gehen davon aus, dass Zyklen, die bis auf ihren Startpunkt gleich sind, nicht separat gezählt werden.

Bondy–Chvátal theorem The best vertex degree characterization of Hamiltonian graphs was provided in 1972 nach dem Bondy–Greife das Theorem, was frühere Ergebnisse von G verallgemeinert. EIN. Dirac (1952) und Øysteinerz. Sowohl der Satz von Dirac als auch der Satz von Ore können auch aus dem Satz von Pósa abgeleitet werden (1962). Die Hamiltonizität wurde in Bezug auf verschiedene Parameter wie die Graphendichte umfassend untersucht, Zähigkeit, verbotene Subgraphen und Abstand neben anderen Parametern.[11] Die Sätze von Dirac und Ore besagen im Wesentlichen, dass ein Graph hamiltonsch ist, wenn er genügend Kanten hat.

Das Bondy-Chvátal-Theorem arbeitet mit dem Abschluss cl(G) eines Graphen G mit n Knoten, erhalten durch wiederholtes Hinzufügen einer neuen Kante uv, die ein nicht benachbartes Paar von Ecken u und v mit deg verbindet(v) + Grad(u) ≥ n bis keine Paare mehr mit dieser Eigenschaft gefunden werden können.

Bondy – Geschnappt durch Theorem (1976) — A graph is Hamiltonian if and only if its closure is Hamiltonian.

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

Satz von Dirac (1952) — A simple graph with n vertices ( {Anzeigestil ngeq 3} ) ist hamiltonsch, wenn jeder Knoten Grad hat {Anzeigestil {tfrac {n}{2}}} oder größer.

Satz von Ore (1960) — A simple graph with n vertices ( {Anzeigestil ngeq 3} ) ist hamiltonsch, wenn, für jedes Paar nicht benachbarter Ecken, die Summe ihrer Grade ist n oder größer.

Die folgenden Sätze können als gerichtete Versionen angesehen werden: Ghouila-Houiri (1960) — A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n.

Meiniel (1973) — A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to {Anzeigestil 2n-1} Die Anzahl der Knoten muss verdoppelt werden, da jede ungerichtete Kante zwei gerichteten Bögen entspricht und somit der Grad eines Knotens im gerichteten Graphen doppelt so groß ist wie der Grad im ungerichteten Graphen.

Rahman-Kaykobad (2005) — A simple graph with n vertices has a Hamiltonian path if, für jedes nicht benachbarte Knotenpaar ist die Summe ihrer Grade und ihrer kürzesten Weglänge größer als n.[12] Der obige Satz kann nur die Existenz eines Hamilton-Pfads in einem Graphen und nicht eines Hamilton-Zyklus erkennen.

Viele dieser Ergebnisse haben Analoga für balancierte bipartite Graphen, bei dem die Scheitelgrade mit der Anzahl der Scheitelpunkte auf einer einzelnen Seite der Bipartition und nicht mit der Anzahl der Scheitelpunkte im gesamten Diagramm verglichen werden.[13] Existence of Hamiltonian cycles in planar graphs Theorem — A 4-connected planar triangulation has a Hamiltonian cycle.[14] Theorem — A 4-connected planar graph has a Hamiltonian cycle.[15] The Hamiltonian cycle polynomial An algebraic representation of the Hamiltonian cycles of a given weighted digraph (deren Bögen Gewichte aus einem bestimmten Bodenfeld zugewiesen werden) ist das Polynom des Hamilton-Zyklus seiner gewichteten Adjazenzmatrix, definiert als die Summe der Produkte der Bogengewichte der Hamilton-Zyklen des Digraphen. Dieses Polynom ist als Funktion in den Bogengewichten genau dann nicht identisch Null, wenn der Digraph hamiltonsch ist. Die Beziehung zwischen der Rechenkomplexität der Berechnung von it und der Berechnung der Permanenten wurde von Grigoriy Kogan aufgezeigt.[16] Siehe auch Barnettes Vermutung, ein offenes Problem zur Hamiltonizität kubischer bipartiter polyedrischer Graphen Eulerscher Pfad, ein Weg durch alle Kanten in einem Graphen Satz von Fleischner, auf Hamilton-Quadraten von Graphen Gray-Code Grinbergs Satz, der eine notwendige Bedingung für planare Graphen angibt, um ein Hamilton-Zyklus-Hamilton-Pfad-Problem zu haben, das Berechnungsproblem zum Finden von Hamiltonschen Pfaden Hypohamiltonscher Graph, ein nicht-hamiltonischer Graph, in dem jeder vertex-deleted subgraph Hamiltonian Knight's tour ist, ein Hamilton-Zyklus in der LCF-Notation des Rittergraphen für kubische Hamilton-Graphen. Lovász-Vermutung, dass vertextransitive Graphen Hamiltonsche panzyklische Graphen sind, Graphen mit Zyklen aller Längen, einschließlich eines Hamilton-Zyklus Sieben Brücken von Königsberg Shortness Exponent, ein numerisches Maß dafür, wie weit die Graphen in einer Familie vom Hamilton-Operator entfernt sein können Snake-in-the-Box, der längste induzierte Pfad in einem Hyperwürfel-Steinhaus-Johnson-Trotter-Algorithmus zum Finden eines Hamilton-Pfads in einem Permutoeder-Subhamilton-Graphen, ein Untergraph eines planaren Hamiltonschen Graphen Taits Vermutung (jetzt als falsch bekannt) dass 3-reguläre polyedrische Graphen hamiltonisch sind Problem des Handlungsreisenden Anmerkungen ^ Biggs, N. L. (1981), "T. P. Kirkman, Mathematiker", Das Bulletin der London Mathematical Society, 13 (2): 97–120, doi:10.1112/blms/13.2.97, HERR 0608093. ^ Watkins, John J. (2004), "Kapitel 2: Rittertouren", Über die Grenze: Die Mathematik der Schachbrettprobleme, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5. ^ der Reiter, Johann (2017). Hamilton Mazes – Der Leitfaden für Anfänger. ^ Friedmann, Erich (2009). "Hamiltonsche Labyrinthe". Erichs Rätselpalast. Ab dem Original archiviert 16 April 2016. Abgerufen 27 Kann 2017. ^ Gärtner, M. "Mathematische Spiele: Über die bemerkenswerte Ähnlichkeit zwischen dem Ikosianischen Spiel und den Türmen von Hanoi." Wissenschaft. Amer. 196, 150–156, Kann 1957 ^ Ghaderpour, E.; Morris, D. W. (2014). "Cayley-Graphen auf nilpotenten Gruppen mit zyklischer Kommutator-Untergruppe sind Hamiltonian". Zeitgenössische Ars Mathematica. 7 (1): 55–72. arXiv:1111.6216. doi:10.26493/1855-3974.280.8d3. ^ Lukas, Joan M. (1987), "Der Rotationsgraph binärer Bäume ist hamiltonsch", Zeitschrift für Algorithmen, 8 (4): 503–535, doi:10.1016/0196-6774(87)90048-4 ^ Hurtado, Ferran; Nein, Markus (1999), "Triangulationsdiagramm eines konvexen Polygons und Triangulationsbaum", Computergeometrie, 13 (3): 179–188, doi:10.1016/S0925-7721(99)00016-4 ^ Eric Weinstein. "Biconnected Graph". Wolfram MathWorld. ^ Balakrishnan, R.; Ranganathan, K. (2012), "Logische Folge 6.5.5", Ein Lehrbuch der Graphentheorie, Springer, p. 134, ISBN 9781461445296. ^ Gold, Ronald J. (Juli 8, 2002). "Fortschritte beim Hamiltonschen Problem – Eine Übersicht" (Pdf). Emory-Universität. Abgerufen 2012-12-10. ^ Rahm, M. S.; Kaykobad, M. (April 2005). "Über Hamiltonkreise und Hamiltonwege". Briefe zur Informationsverarbeitung. 94: 37–41. doi:10.1016/j.ipl.2004.12.002. ^ Mond, J.; Moser, L. (1963), "Auf Hamiltonschen bipartiten Graphen", Israelisches Journal für Mathematik, 1 (3): 163–165, doi:10.1007/BF02759704, HERR 0161332 ^ 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, W. T. (1956), "Ein Satz über planare Graphen", Trans. Amer. Mathematik. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8 ^ Kogan, Gregor (1996), "Berechnen von Permanenten über Merkmalsfeldern 3: wo und warum wird es schwierig", 37th Annual Symposium on Foundations of Computer Science (FEUER '96): 108–114, doi:10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2 Referenzen Berge, Claude; Ghouila-Houiri, EIN. (1962), Programmierung, Spiele und Verkehrsnetze, New York: Söhne, Inc. Deleon, Melissa (2000), "Eine Studie über ausreichende Bedingungen für Hamilton-Zyklen" (Pdf), Rose-Hulman Undergraduate Math Journal, 1 (1), vom Original archiviert (Pdf) an 2012-12-22, abgerufen 2005-11-28. Dirac, G. EIN. (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 der Wurzeln der Einheit", Philosophisches Magazin, 12: 446. Hamilton, William Rowan (1858), "Konto des Ikosianischen Kalküls", Verfahren der Royal Irish Academy, 6: 415–416. Meiniel, M. (1973), "Eine hinreichende Bedingung für die Existenz eines Hamiltonkreises in einem gerichteten Graphen", Zeitschrift für kombinatorische Theorie, Serie B, 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9, HERR 0317997. Erz, Øystein (1960), "Hinweis zu Hamilton-Schaltungen", The American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928, HERR 0118683. Vornehm, L. (1962), "Ein Satz über Hamilton-Linien", Ungarischer Tud. Verzögerungen. Matte. Forschung Int. Komm., 7: 225–226, HERR 0184876. External links Weisstein, Erich W. "Hamiltonscher Zyklus". MathWorld. Kategorien Euler-Tour und Hamilton-Zyklen: Rechenprobleme in der GraphentheorieNP-vollständige ProblemeObjekte der GraphentheorieHamiltonsche Pfade und ZyklenWilliam Rowan Hamilton