Diskussion:Hamiltonkreisproblem

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Hamiltonkreisproblem“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Alte Diskussionen

Zum Revert: Ein Kreis enthält sowieso jeden Knoten nur einmal! Also muss ein Kreis der alle Knoten enhält auch jeden Knoten genau einmal enthalten! Noch Fragen? :-) --Coma 13:38, 21. Apr 2004 (CEST)

Der erste Link geht nicht mehr, hat jemand das Applet noch anderswo gefunden? -- MrKlappstuhl 16:13, 24. Mai 2009 (CEST)

Chvatal 1972

Muss es nicht lauten:

"Ein Tupel $(a_{1},...,a_{n})\!$ natürlicher Zahlen mit $a_{1}\leq ...\leq a_{n}<n$ ist hamiltonisch, wenn für jedes $i<{\frac {n}{2}}$ gilt: $a_{i}\leq i\Rightarrow a_{n-i}\geq n-i$."

Ein Gegenbeispiel für die Richtung "=>" ist beispielsweise (2,2,2,2,2), der Graph wäre dann G = {(1,2),(2,3),(3,4),(4,5),(5,1)}. G ist Hamiltonsch, aber seine Gradfolge erfüllt nicht die Bedingung (a_2 <= 2 aber es folgt nicht a_3 >= 3). --Ich hab hunga 14:21, 2. Jul 2006 (CEST)

4-zusammenhängend

Folgt man dem Link in dem Resultat von William T. Tutte, so kommt man zu dem Ergebnis, dass 4-zusammenhängend über die höheren Homotopiegruppen, sprich Einbettungen der S^4 erklärt ist. Hier bzw. allgemein in der Graphentheorie sollte dies jedoch bedeuten, dass je zwei Ecken durch 4 (bis auf die Endpunkte) disjunkte Pfade verbunden sind, bzw. daß der Graph durch Trennen dreier beliebiger Kanten nicht zerfällt. Leider finde ich keinen geeigneteren Artikel zum Verlinken - müsste wohl entweder unter Graph mit erläutert werden oder neu geschrieben...--Hagman 14:37, 1. Feb. 2007 (CET)

Ergebnis von Ore

Ist das zweite Resultat nicht eine triviale Folgerung des ersten? Oder soll es beim ersten Resultat heissen "je zweier Knoten"?--Hagman 14:37, 1. Feb. 2007 (CET)

Ja, da ist was faul. Man kann sich leicht ein Gegenbeispiel überlegen, in dem es weder Hamiltonpfad noch -kreis gibt, das die Bedingung, dass es zwei nicht adjazente Knoten gibt, deren Summe der Grade größer als n ist, erfüllt. Wenn das für je zwei (nicht adjazente) Knotenpaare gälte, könnte ich dem glauben schenken ;) --130.149.13.61 16:48, 7. Jul. 2011 (CEST)

Dirac

Fehlt nicht noch eine Voraussetzung? Der vollständige Grapgmit zwei n=Knoten hat Minimalgrad1=n72, aber keinen Hamiltonkreis.--Hagman 17:28, 14. Jul. 2008 (CEST)

Handlungsreisender

"Ein bekannter Spezialfall des Hamiltonkreisproblems ist das Problem des Handlungsreisenden, bei welchem nach einem kürzesten Hamiltonkreis in einem gerichteten Graphen mit Kantengewichten gefragt wird." - WO wird beim Handlungsreisenden gefordert das ein Hammilton kreis rauskommt? reicht es nicht alle Orte mindestens(ggf aber auch 2 mal) einmal zu Besuchen???(nicht signierter Beitrag von 129.13.186.1 (Diskussion | Beiträge) 11:36, 27. Jul. 2009 (CEST))

Ich glaube, hier liegt ein Formulierungsfehler vor. Das TSP ist ein Spezialfall des Hamiltonpfadproblems, nicht Hamiltonkreis. Der TSP muss ja nicht wieder am Anfangspunkt rauskommen, was der einzige Unterschied zwischen Kreis und Pfad ist. -- Aike 22:03, 3. Feb. 2011 (CET)

Nochmal zur ersten Frage: beim Handlungsreisenden wird gefordert, dass jede Stadt genau einmal besucht wird. Weiterhin muss in der üblichen Definition der Handlungsreisende auch wieder an seinen Ausgangspunkt zurückkehren, also ist TSP ein Spezialfall des Hamiltonkreisproblems. Man spricht auch von einer Tour bzw. Rundtour. Siehe zum Beispiel auch einfach den Artikel zum Problem des Handlungsreisenden auf Wikipedia. --130.149.13.61 16:42, 7. Jul. 2011 (CEST)

Ich stimme 130.149.13.61 zu, sowohl im TSP als auch im Hamiltonkreisproblem muß man wieder zum Ausgangsort zurückkehren. Allerdings ist das Hamiltonkreisproblem dennoch ein Spezialfall des TSP und nicht andersherum. Im Artikel ist es also FALSCH beschrieben. Der Unterschied zwischen den Problemen ist, dass man im TSP die KÜRZESTE Tour finden muss, während im Hamiltonkreisproblem einfach nur die Existenz irgendeiner Tour nachgewiesen werden muss. "Spezialfall" bedeutet in der Mathematik immer, dass man, wenn man das allgemeinere Problem lösen kann, man mit diesem Lösungsverfahren auch direkt den Spezialfall lösen kann (zB wenn ich allgemeine Polynomgleichungen lösen kann, kann ich auch den Spezialfall der quadratischen Gleichungen lösen). Wie man mithilfe eines TSP-Solvers den Spezialfall Hamiltonkreisproblem lösen kann, ist in der englischen Wikipedia auf der Seite http://en.wikipedia.org/wiki/Hamiltonian_path_problem unter dem Punkt "Relation between problems" erklärt. (nicht signierter Beitrag von 132.230.167.12 (Diskussion) 11:38, 9. Okt. 2012 (CEST))

NP vollständig?

Ist das Hamiltonkreisproblem nur die Entscheidung, ob ein Graph hamiltonsch ist oder nicht (so steht es im Artikel), oder muss auch der entsprechende Kreis geliefert werden? Ähnlich kann man ja bei zusammengesetzten Zahlen u.U. schnell nachweisen, dass sie keine Primzahlen sind, kennt aber deshalb noch lange nicht seine Faktoren. --Rat 00:01, 6. Apr. 2010 (CEST)

Steht doch im Wort: Kreis/Zyklus muss vorhanden sein im Hamiltonweg damit es ein Hamiltonkreis ist. Hamiltonsch ist nur eine Abfolge von durchlaufenden Knoten ohne Wiederholung die über Graphkanten erreicht werden können.--95.91.62.194 12:51, 24. Jun. 2012 (CEST)

Ich habe einen Lösungsalgorithmus gefunden

Hallo, ich aheb das Problem des längsten Pfads am Freitag in einer Vorlesung erörtert bekommen und habe einen Algorithmus entwickelt, der für einen Graf mit n Knoten maximal n hoch 3 Schritte braucht, um einen Pfad zu berechnen. Dabei kann ich auch mit Pfaden arbeiten, die eine Länge haben, sodass entweder der kürzeste Hamiltonkreis (das wäre dann die Lösung des Travelling Salesman Problem) oder der längste Hamiltonkreis erstellt wird. Jetzt habe ich auch noch gehört, dass ein Preisgeld über 1 Mio USD für eine Lösung des HKP aussteht. Ich suche jemanden, der Ahnung von diesen Preisausschreibungen der Millenium Prize Problems hat und mir hilft meinen ALgo zu Geld zu machen. Wer Spß hat, schreibt an IhreWunschadesse@web.de

Jetzt stellt sich fürmich immer noch die Frage, was das HKP mit P-NP-Vollständigkeit zu tun hat. Ich fände es schön, wenn das für einen normalen Menschen mit normalem Verstand und einem normalen Grundwissen verständlich erörtert werden könnte. (nicht signierter Beitrag von 88.77.2.192 (Diskussion) 14:03, 13. Jun. 2011 (CEST))

Definitionen

Dieser Abschnitt fängt an mit: Sei G = (V,E) ein Graph mit |V| = n Knoten (oder Ecken) und |E| = m Kanten.

Im weiteren wird aber nirgendwo referiert an n oder m, aber wird erneut von n gesprochen, anders als die n vom Anzahl Knoten. Madyno (Diskussion) 11:35, 20. Apr. 2018 (CEST)