Ich habe einen verbundenen, nicht gerichteten Graphen mit N Knoten und 2N-3 Kanten. Sie können den Graphen so betrachten, wie er auf einem vorhandenen Ausgangsgraphen aufgebaut ist, der 3 Knoten und 3 Kanten hat. Jeder Knoten wird dem Diagramm hinzugefügt und hat zwei Verbindungen mit den vorhandenen Knoten im Diagramm. Wenn alle Knoten dem Diagramm hinzugefügt sind (N-3 Knoten insgesamt hinzugefügt), wird das endgültige Diagramm erstellt.
Ursprünglich wurde ich gefragt, welche maximale Anzahl von Knoten in diesem Graphen genau einmal besucht werden kann (mit Ausnahme des Anfangsknotens), dh wie viele Knoten maximal im Hamilton-Pfad enthalten sind gegebenes Diagramm? (Okay, der größte Hamilton-Pfad ist keine gültige Phrase, aber in Anbetracht der Natur der Frage muss ich eine maximale Anzahl von Knoten finden, die einmal besucht werden und die Reise endet am Anfangsknoten. Ich dachte, es könnte sein betrachtet als ein Sub-Graph, der Hamiltonian ist, und besteht aus der maximalen Anzahl von Knoten, also dem größtmöglichen Hamilton-Pfad).
Da ich nicht aufgefordert werde, einen Pfad zu finden, sollte ich zuerst prüfen, ob ein Hamilton-Pfad für die angegebene Anzahl von Knoten existiert. Ich weiß, dass planare Graphen und Zyklusgraphen (C n ) Hamilton-Graphen sind (ich auch kenne Ore's Theorem für Hamilton-Graphen, aber der Graph, an dem ich arbeiten werde, ist kein dichter Graph mit einem großen Wahrscheinlichkeit, so dass Ores Satz in meinem Fall ziemlich nutzlos ist). Daher muss ich einen Algorithmus finden, um zu überprüfen, ob der Graph ein Zyklusgraph ist, d.h. ob ein Zyklus existiert, der alle Knoten des gegebenen Graphen enthält.
Da DFS zur Erkennung von Zyklen verwendet wird, dachte ich, dass eine kleine Manipulation des DFS mir helfen könnte, zu erkennen, wonach ich suche, indem ich die erkundeten Knoten im Auge behalte und schließlich überprüfe, ob der zuletzt besuchte Knoten eine Verbindung zum Anfangsknoten. Unglücklicherweise Ich könnte mit diesem Ansatz nicht erfolgreich sein.
Ein anderer Ansatz, den ich versuchte, bestand darin, einen Knoten auszuschließen und dann zu versuchen, ausgehend von seinem anderen benachbarten Knoten zu seinem benachbarten Knoten zu gelangen. Dieser Algorithmus liefert möglicherweise keine korrekten Ergebnisse entsprechend den ausgewählten benachbarten Knoten.
Ich bin hier ziemlich festgefahren. Können Sie mir helfen, an einen anderen Algorithmus zu denken, um mir zu sagen, ob der Graph ein Zyklusdiagramm ist?
Bearbeiten
Ich erkannte mit Hilfe des Kommentars (danke dafür n.m.):
Ein Zyklusdiagramm besteht aus einem einzigen Zyklus und hat N Kanten und N Ecken. Wenn es einen Zyklus gibt, der alle Knoten des gegebenen Graphen enthält, ist das ein Hamilton-Zyklus. - n.m.
dass ich eigentlich suche nach einem Hamilton-Pfad, was ich nicht vorhatte :) Bei einem zweiten Gedanken denke ich, dass die Überprüfung der Hamilton-Eigenschaft des Graphen während des Aufbaus effizienter ist, was ich auch suche: Zeiteffizienz.
Nach einigem Nachdenken dachte ich, was auch immer die Anzahl der Knoten sein mag, der Graph scheint wegen der Knotenzusatzkriterien ein Hamilton-Operator zu sein. Das Problem ist, ich kann nicht sicher sein und ich kann es nicht beweisen. Fügt das Hinzufügen von Knoten auf diese Weise, d. H. Das Hinzufügen neuer Knoten mit 2 Kanten, die den hinzugefügten Knoten mit den vorhandenen Knoten verbinden, die Hamilton-Eigenschaft des Graphen? Wenn es die Hamilton-Eigenschaft nicht ändert, wie? Wenn es sich wieder ändert, wie? Danke.
BEARBEITEN # 2
Ich habe wiederum festgestellt, dass das Konstruieren des Graphen, wie ich es beschrieben habe, die Hamilton-Eigenschaft verändern könnte. Betrachten Sie eine Eingabe wie folgt:
%Vor%Diese Eingabe besagt, dass der vierte Knoten mit Knoten 1 und Knoten 3, 5. mit Knoten 2 und Knoten 3 verbunden ist. . .
Der vierte und der siebte Knoten sind mit denselben Knoten verbunden, wodurch die maximale Anzahl von Knoten, die genau einmal besucht werden können, um 1 verringert wird. Wenn ich diese Kollisionen feststelle ( NOT einschließlich einer Eingabe wie z 3 3, das ist ein Beispiel, das Sie vorgeschlagen haben, da das Problem angibt, dass die neu hinzugefügten Kanten mit 2 anderen Knoten verbunden sind und senken die maximale Anzahl der Knoten, beginnend mit N, ich glaube, dass ich bekommen kann das richtige Ergebnis.
Seht, ich wähle nicht die Verbindungen, sie sind mir gegeben und ich muss die max finden. Anzahl der Knoten.
Ich denke, das Zählen der gleichen Verbindungen beim Erstellen des Graphen und Subtrahieren der Anzahl der gleichen Verbindungen von N wird das richtige Ergebnis geben? Können Sie das bestätigen oder gibt es einen Fehler bei diesem Algorithmus?
Um diesem Thread eine Klarstellung zu geben: Das Finden eines Hamilton-Zyklus ist NP-vollständig, was bedeutet, dass das Finden eines längsten Zyklus auch NP-vollständig ist, denn wenn wir einen längsten Zyklus in einem Graphen finden können, können wir den Hamilton-Zyklus finden des Untergraphen, der durch die Eckpunkte induziert wird, die auf diesem Zyklus liegen. (Siehe auch zum Beispiel dieses Papier bezüglich des längsten Zyklusproblems <) / p>
Wir können Diracs Kriterium hier nicht benutzen: Dirac sagt uns nur minimum degree >= n/2 -> Hamiltonian Cycle , das ist die Implikation in die entgegengesetzte Richtung dessen, was wir brauchen würden. Andersherum ist definitiv falsch: nimm einen Zyklus über n Vertices, jeder Scheitelpunkt in ihm hat genau Grad 2, egal wie groß der Kreis ist, aber es hat (ist) ein HC. Was Sie an Dirac erkennen können, ist no Hamiltonian Cycle -> minimum degree < n/2 , was hier keinen Sinn macht, da wir nicht wissen, ob unser Graph eine HC hat oder nicht, also können wir die Implikation nicht verwenden (trotzdem erstellt jeder Graph, nach dem was wir konstruieren) Das beschriebene OP wird einen Scheitelpunkt von Grad 2 haben, nämlich den letzten Scheitelpunkt, der dem Graphen hinzugefügt wurde, also haben wir für beliebige n einen minimalen Grad 2 ).
Das Problem besteht darin, dass Sie sowohl Graphen beliebiger Größe mit einem HC als auch Graphen beliebiger Größe, die keinen HC haben, konstruieren können. Für den ersten Teil: Wenn das ursprüngliche Dreieck A, B, C ist und die hinzugefügten Scheitelpunkte mit 1 bis k nummeriert sind, dann verbinde den ersten hinzugefügten Scheitelpunkt mit A und C und den k + 1-ten Scheitelpunkt mit A und dem k-ten Scheitelpunkt Vertex für alle k & gt; = 1. Der Zyklus ist A,B,C,1,2,...,k,A . Für den zweiten Teil verbinde beide Scheitelpunkte 1 und 2 mit A und B; Dieses Diagramm hat keinen HC.
Es ist auch wichtig zu beachten, dass die Eigenschaft, einen HC zu haben, während der Konstruktion von einem Scheitelpunkt zum anderen wechseln kann. Sie können die HC-Eigenschaft sowohl erstellen als auch löschen, wenn Sie einen Scheitelpunkt hinzufügen, so dass Sie bei jedem Hinzufügen eines Scheitelpunkts darauf achten müssen. Ein einfaches Beispiel: Nehmen Sie den Graphen nach dem Hinzufügen des ersten Scheitelpunkts und fügen Sie einen zweiten Scheitelpunkt mit Kanten zu den gleichen zwei Scheitelpunkten des Dreiecks hinzu, mit dem der erste Scheitelpunkt verbunden war. Dies konstruiert aus einem Graphen mit einem HC ein Graph ohne HC. Anders herum: füge jetzt einen dritten Eckpunkt hinzu und verbinde ihn mit 1 und 2; dies ergibt sich aus einem Graphen ohne HC, einem Graphen mit einem HC Das Speichern des letzten bekannten HC während des Aufbaus hilft dir nicht wirklich, weil er sich komplett ändern kann. Du könntest einen HC haben, nachdem der 20. Eckpunkt hinzugefügt wurde, dann keinen für k in [21.2000] und noch einen für den 2001. Eckpunkt. Höchstwahrscheinlich hat die HC, die Sie auf 23 Eckpunkten hatten, Ihnen nicht viel weiter.
Wenn Sie herausfinden möchten, wie Sie dieses Problem effizient lösen , müssen Sie Kriterien finden, die für alle Ihre Graphen funktionieren, die effizient überprüft werden können. Sonst scheint mir Ihr Problem nicht einfacher zu sein als das Hamilton-Cycle-Problem im allgemeinen Fall, so dass Sie möglicherweise einen der Algorithmen anpassen können. verwendet für dieses Problem zu deiner Variante davon.
Ich habe einen verbundenen, nicht gerichteten Graphen mit N Knoten und 2N-3 Kanten. Sie können den Graphen so betrachten, wie er auf einem vorhandenen Ausgangsgraphen aufgebaut ist, der 3 Knoten und 3 Kanten hat. Jeder Knoten wird dem Diagramm hinzugefügt und hat zwei Verbindungen mit den vorhandenen Knoten im Diagramm. Wenn alle Knoten dem Diagramm hinzugefügt sind (N-3 Knoten insgesamt hinzugefügt), wird das endgültige Diagramm erstellt.
Ursprünglich wurde ich gefragt, welche maximale Anzahl von Knoten in diesem Graphen genau einmal besucht werden kann (mit Ausnahme des Anfangsknotens), dh wie viele Knoten maximal im Hamilton-Pfad enthalten sind gegebenes Diagramm? (Okay, der größte Hamilton-Pfad ist keine gültige Phrase, aber in Anbetracht der Natur der Frage muss ich eine maximale Anzahl von Knoten finden, die einmal besucht werden und die Reise endet am Anfangsknoten. Ich dachte, es könnte sein betrachtet als ein Sub-Graph, der Hamiltonian ist, und besteht aus der maximalen Anzahl von Knoten, also dem größtmöglichen Hamilton-Pfad).
Da ich nicht aufgefordert werde, einen Pfad zu finden, sollte ich zuerst prüfen, ob ein Hamilton-Pfad für die angegebene Anzahl von Knoten existiert. Ich weiß, dass planare Graphen und Zyklusgraphen (C n ) Hamilton-Graphen sind (ich auch kenne Ore's Theorem für Hamilton-Graphen, aber der Graph, an dem ich arbeiten werde, ist kein dichter Graph mit einem großen Wahrscheinlichkeit, so dass Ores Satz in meinem Fall ziemlich nutzlos ist). Daher muss ich einen Algorithmus finden, um zu überprüfen, ob der Graph ein Zyklusgraph ist, d.h. ob ein Zyklus existiert, der alle Knoten des gegebenen Graphen enthält.
Da DFS zur Erkennung von Zyklen verwendet wird, dachte ich, dass eine kleine Manipulation des DFS mir helfen könnte, zu erkennen, wonach ich suche, indem ich die erkundeten Knoten im Auge behalte und schließlich überprüfe, ob der zuletzt besuchte Knoten eine Verbindung zum Anfangsknoten. Unglücklicherweise Ich könnte mit diesem Ansatz nicht erfolgreich sein.
Ein anderer Ansatz, den ich versuchte, bestand darin, einen Knoten auszuschließen und dann zu versuchen, ausgehend von seinem anderen benachbarten Knoten zu seinem benachbarten Knoten zu gelangen. Dieser Algorithmus liefert möglicherweise keine korrekten Ergebnisse entsprechend den ausgewählten benachbarten Knoten.
Ich bin hier ziemlich festgefahren. Können Sie mir helfen, an einen anderen Algorithmus zu denken, um mir zu sagen, ob der Graph ein Zyklusdiagramm ist?
Bearbeiten
Ich erkannte mit Hilfe des Kommentars (danke dafür n.m.):
Ein Zyklusdiagramm besteht aus einem einzigen Zyklus und hat N Kanten und N Ecken. Wenn es einen Zyklus gibt, der alle Knoten des gegebenen Graphen enthält, ist das ein Hamilton-Zyklus. - n.m.
dass ich eigentlich suche nach einem Hamilton-Pfad, was ich nicht vorhatte :) Bei einem zweiten Gedanken denke ich, dass die Überprüfung der Hamilton-Eigenschaft des Graphen während des Aufbaus effizienter ist, was ich auch suche: Zeiteffizienz.
Nach einigem Nachdenken dachte ich, was auch immer die Anzahl der Knoten sein mag, der Graph scheint wegen der Knotenzusatzkriterien ein Hamilton-Operator zu sein. Das Problem ist, ich kann nicht sicher sein und ich kann es nicht beweisen. Fügt das Hinzufügen von Knoten auf diese Weise, d. H. Das Hinzufügen neuer Knoten mit 2 Kanten, die den hinzugefügten Knoten mit den vorhandenen Knoten verbinden, die Hamilton-Eigenschaft des Graphen? Wenn es die Hamilton-Eigenschaft nicht ändert, wie? Wenn es sich wieder ändert, wie? Danke.
BEARBEITEN # 2
Ich habe wiederum festgestellt, dass das Konstruieren des Graphen, wie ich es beschrieben habe, die Hamilton-Eigenschaft verändern könnte. Betrachten Sie eine Eingabe wie folgt:
%Vor%Diese Eingabe besagt, dass der vierte Knoten mit Knoten 1 und Knoten 3, 5. mit Knoten 2 und Knoten 3 verbunden ist. . .
Der vierte und der siebte Knoten sind mit denselben Knoten verbunden, wodurch die maximale Anzahl von Knoten, die genau einmal besucht werden können, um 1 verringert wird. Wenn ich diese Kollisionen feststelle ( NOT einschließlich einer Eingabe wie z 3 3, das ist ein Beispiel, das Sie vorgeschlagen haben, da das Problem angibt, dass die neu hinzugefügten Kanten mit 2 anderen Knoten verbunden sind und senken die maximale Anzahl der Knoten, beginnend mit N, ich glaube, dass ich bekommen kann das richtige Ergebnis.
Seht, ich wähle nicht die Verbindungen, sie sind mir gegeben und ich muss die max finden. Anzahl der Knoten.
Ich denke, das Zählen der gleichen Verbindungen beim Erstellen des Graphen und Subtrahieren der Anzahl der gleichen Verbindungen von N wird das richtige Ergebnis geben? Können Sie das bestätigen oder gibt es einen Fehler bei diesem Algorithmus?
Unten habe ich drei zusätzliche Knoten (3,4,5) im ursprünglichen Graphen hinzugefügt und es sieht so aus, als könnte ich ständig neue Knoten hinzufügen, während ich die Eigenschaft des Hamilton-Zyklus behalte. Für den folgenden Graph wäre der Zyklus connected, non-directed
Da es keine zusätzlichen Einschränkungen gab, wie Sie einen neuen Knoten mit zwei Kanten hinzufügen können, denke ich, dass Sie nach Konstruktion ein Diagramm haben können, das die Eigenschaft von hamiltonian cycle enthält.
Um diesem Thread eine Klarstellung zu geben: Das Finden eines Hamilton-Zyklus ist NP-vollständig, was bedeutet, dass das Finden eines längsten Zyklus auch NP-vollständig ist, denn wenn wir einen längsten Zyklus in einem Graphen finden können, können wir den Hamilton-Zyklus finden des Untergraphen, der durch die Eckpunkte induziert wird, die auf diesem Zyklus liegen. (Siehe auch zum Beispiel dieses Papier bezüglich des längsten Zyklusproblems <) / p>
Wir können Diracs Kriterium hier nicht benutzen: Dirac sagt uns nur Floyd's Cycle Finding algorithm , das ist die Implikation in die entgegengesetzte Richtung dessen, was wir brauchen würden. Andersherum ist definitiv falsch: nimm einen Zyklus über Tortoise and Hare Vertices, jeder Scheitelpunkt in ihm hat genau Grad 2, egal wie groß der Kreis ist, aber es hat (ist) ein HC. Was Sie an Dirac erkennen können, ist closed paths , was hier keinen Sinn macht, da wir nicht wissen, ob unser Graph eine HC hat oder nicht, also können wir die Implikation nicht verwenden (trotzdem erstellt jeder Graph, nach dem was wir konstruieren) Das beschriebene OP wird einen Scheitelpunkt von Grad %code% haben, nämlich den letzten Scheitelpunkt, der dem Graphen hinzugefügt wurde, also haben wir für beliebige %code% einen minimalen Grad %code% ).
Das Problem besteht darin, dass Sie sowohl Graphen beliebiger Größe mit einem HC als auch Graphen beliebiger Größe, die keinen HC haben, konstruieren können. Für den ersten Teil: Wenn das ursprüngliche Dreieck A, B, C ist und die hinzugefügten Scheitelpunkte mit 1 bis k nummeriert sind, dann verbinde den ersten hinzugefügten Scheitelpunkt mit A und C und den k + 1-ten Scheitelpunkt mit A und dem k-ten Scheitelpunkt Vertex für alle k & gt; = 1. Der Zyklus ist %code% . Für den zweiten Teil verbinde beide Scheitelpunkte 1 und 2 mit A und B; Dieses Diagramm hat keinen HC.
Es ist auch wichtig zu beachten, dass die Eigenschaft, einen HC zu haben, während der Konstruktion von einem Scheitelpunkt zum anderen wechseln kann. Sie können die HC-Eigenschaft sowohl erstellen als auch löschen, wenn Sie einen Scheitelpunkt hinzufügen, so dass Sie bei jedem Hinzufügen eines Scheitelpunkts darauf achten müssen. Ein einfaches Beispiel: Nehmen Sie den Graphen nach dem Hinzufügen des ersten Scheitelpunkts und fügen Sie einen zweiten Scheitelpunkt mit Kanten zu den gleichen zwei Scheitelpunkten des Dreiecks hinzu, mit dem der erste Scheitelpunkt verbunden war. Dies konstruiert aus einem Graphen mit einem HC ein Graph ohne HC. Anders herum: füge jetzt einen dritten Eckpunkt hinzu und verbinde ihn mit 1 und 2; dies ergibt sich aus einem Graphen ohne HC, einem Graphen mit einem HC Das Speichern des letzten bekannten HC während des Aufbaus hilft dir nicht wirklich, weil er sich komplett ändern kann. Du könntest einen HC haben, nachdem der 20. Eckpunkt hinzugefügt wurde, dann keinen für k in [21.2000] und noch einen für den 2001. Eckpunkt. Höchstwahrscheinlich hat die HC, die Sie auf 23 Eckpunkten hatten, Ihnen nicht viel weiter.
Wenn Sie herausfinden möchten, wie Sie dieses Problem effizient lösen , müssen Sie Kriterien finden, die für alle Ihre Graphen funktionieren, die effizient überprüft werden können. Sonst scheint mir Ihr Problem nicht einfacher zu sein als das Hamilton-Cycle-Problem im allgemeinen Fall, so dass Sie möglicherweise einen der Algorithmen anpassen können. verwendet für dieses Problem zu deiner Variante davon.
Was wir in diesem Problem haben, ist ein %code% Graph mit N Knoten und 2N-3 Kanten. Betrachten Sie die unten angegebene Grafik,
%Vor% Der Graph hat keinen Hamilton-Zyklus. Aber das Diagramm wird gemäß den Regeln zum Hinzufügen von Knoten erstellt. Wenn Sie also nach einem Hamilton-Zyklus suchen, erhalten Sie möglicherweise keine Lösung. Darüber hinaus, selbst wenn es möglich ist, ist die Hamilton-Zyklus-Detektion ein NP-vollständiges Problem mit O (2
Ich schlage vor, eine modifizierte Version von %code% (auch% code_% Algorithmus genannt) zu verwenden.
Der modifizierte Algorithmus ist
%Vor%Der Algorithmus ruft Floyds Cycle Finding Algorithm maximal 2N mal auf. Floyds Cycle Finding-Algorithmus benötigt eine lineare Zeit (O (N)). Daher ist die Komplexität des modifizierten Algorithmus O (N 2 ) , was viel besser ist als die exponentielle Zeit, die der Hamilton-Zyklus-basierte Ansatz einnimmt.
Ein mögliches Problem bei diesem Ansatz besteht darin, dass %code% zusammen mit Zyklen erkannt wird, sofern keine strengeren Prüfkriterien implementiert werden.
Antworten Sie auf Bearbeiten # 2
Betrachten Sie die Grafik unten,
%Vor%Gemäß Ihrem Algorithmus hat dieser Graph keinen Zyklus, der alle Knoten enthält. Aber es gibt einen Zyklus in diesem Graph, der alle Knoten enthält.
%Vor%Also ich denke, es gibt einen Fehler in Ihrem Ansatz. Aber wenn Ihr Algorithmus korrekt ist, ist er viel besser als mein Ansatz. Da meins O (n 2 ) Zeit einnimmt, wo Ihrs nur O (n) braucht.
Unten habe ich drei zusätzliche Knoten (3,4,5) im ursprünglichen Graphen hinzugefügt und es sieht so aus, als könnte ich ständig neue Knoten hinzufügen, während ich die Eigenschaft des Hamilton-Zyklus behalte. Für den folgenden Graph wäre der Zyklus 0-1-3-5-4-2-0
Da es keine zusätzlichen Einschränkungen gab, wie Sie einen neuen Knoten mit zwei Kanten hinzufügen können, denke ich, dass Sie nach Konstruktion ein Diagramm haben können, das die Eigenschaft von hamiltonian cycle enthält.
Tags und Links algorithm language-agnostic graph hamiltonian-cycle cyclic-graph