„Diskussion:Hamiltonkreisproblem" – Versionsunterschied

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) Beantworten

Muss es nicht lauten:

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

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) Beantworten

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) Beantworten

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) Beantworten

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) Beantworten

"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)) Beantworten

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) Beantworten

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) Beantworten

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)) Beantworten

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) Beantworten

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) Beantworten

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)) Beantworten

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) Beantworten

Auf diesen Wikipedia-Artikel bin ich gestoßen, weil ich wissen will, ob ich feststellen kann, ob es einen Weg gibt, der bei einer gegebenen Anzahl und Anordnung von Punkten von einem festgelegten Ausgangspunkt sowie einenrm anderen (!) festgelegten Endpunkt führt und dabei alle Punkte genau einmal durchläuft (vgl. »The Bug Game«). Wenn ich nicht ganz falsch liege, dann ist das ein Hamiltonweg (bzw. Hamiltonpfad) und nicht ein Hamiltonkreis, bei dem Ausgangs- und Endpunkt identisch sind.

Gibt es einen Wikipedia-Artikel, der dieses leicht andere Problem behandelt?

Viele Grüße --Jake2042 (Diskussion) 02:49, 3. Feb. 2025 (CET) Beantworten

Hallo Jake2042, der englische Artikel behandelt das Hamiltonpfadproblem statt dem Hamiltonkreisproblem. Beide Probleme sind eng verwandt. Auch das Hamltonpfadproblem ist NP-vollständig, das heißt es ist kein Polynomialzeitalgorithmus bekannt und vermutlich existiert auch keiner. Dasselbe gilt auch für den Spezialfall, dass der Start- und Endpunkt vorgegeben sind. Nichtsdestotrotz gibt es für manche Graphklassen effiziente Lösungsverfahren. Beispielsweise können sowohl das Hamiltonkreisproblem als auch das Hamiltonpfadproblem auf Intervallgraphen in linearer Zeit gelöst werden. Interessanterweise ist bei diesen Graphen die Komplexität des Problems nach wie vor offen, wenn beide Endpunkte des Hamiltonpfads vorgegeben sind. Das Problem mit vorgegeben Endpunkten scheint also doch um einiges komplizierter zu sein als ohne Vorgaben. Wie sehen denn die Graphen aus, für die das Problem lösen möchtest? --Redrobsche (Diskussion) 19:55, 3. Feb. 2025 (CET) Beantworten