So bestimmen Sie, ob das Entfernen eines bestimmten Zyklus ein Diagramm trennt

Question

So bestimmen Sie, ob das Entfernen eines bestimmten Zyklus ein Diagramm trennt

8

Ich habe Wege gesehen, einen Zyklus in einem Graphen zu erkennen, aber ich habe immer noch keinen Weg gefunden, einen "brückenartigen" Zyklus zu erkennen. Nehmen wir an, wir haben einen Zyklus in einem verbundenen (und ungerichteten) Graphen gefunden. Wie können wir feststellen, ob das Entfernen dieses Zyklus die Grafik trennt oder nicht? Wenn ich den Zyklus entferne, bedeute ich, die Kanten im Zyklus zu entfernen (so dass die Ecken nicht betroffen sind).

Eine Möglichkeit besteht darin, die Anzahl der Komponenten vor und nach dem Entfernen zu zählen. Ich bin nur neugierig zu wissen, ob es einen besseren Weg gibt.

Wenn es dafür einen etablierten Algorithmus gibt, könnte mich bitte jemand auf eine verwandte Arbeit / Papier / Publikation hinweisen?

algorithm graph

Wayne 09.10.2015, 11:05

quelle

2 Antworten

Tags und Links algorithm graph

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Verwenden Sie MacRuby Debugger in Xcode?

score 0 · Answer 1

Hier ist der naive Algorithmus, ich denke nicht, dass es einen effizienteren Weg gibt, die Überprüfung durchzuführen.

Beginnen Sie mit Ihrer Kantenliste ( cycleEdges )
Holen Sie sich die Scheitelpunkte innerhalb von cycleEdges ( cycleVertices )
- Wenn ein Eckpunkt in cycleVertices nur Kanten enthält, die Teil von cycleEdges sind, geben Sie FALSE
Für jeden Veteranen In cycleVertices
- Folgen Sie rekursiv Ecken von Ecken, die nicht in cycleEdges sind (vermeiden Sie bereits besuchte Ecken)
  - Wenn ein Eckpunkt erreicht wird, der nicht in cycleVertices enthalten ist, fügen Sie ihn zu te set outsideVertices hinzu (stoppen Sie die rekursive Suche in diesem Pfad)
- Wenn nur Eckpunkte erreicht wurden, die in cycleVertices enthalten sind, geben Sie FALSE
Wenn outsideVertices 1 Element enthält, geben Sie TRUE
Wählen Sie einen Eckpunkt in outsideVertices und entfernen Sie ihn aus outsideVertices
- Folgen Sie den Ecken des Eckpunkts rekursiv, die nicht in cycleEdges enthalten sind (vermeiden Sie bereits besuchte Eckpunkte) (bevorzugen Sie Kanten mit einem Eckpunkt in outsideVertices , um die Laufzeit für große Graphen zu verbessern) )
  - Wenn ein Vertex erreicht wird, der sich in outsideVertices befindet, entfernen Sie ihn aus outsideVertices
    - Wenn outsideVertices leer ist, geben Sie TRUE
Gib FALSCH zurück

score 0 · Answer 2

Sie können es für E + V tun. Sie können alle Brücken in Ihrem Diagramm für E + V durch dfs + dynamische Programmierung erhalten.

Ссылка

Speichere sie (mach einfach Boolesch [E], und mache "wahr". Dann können Sie für O (1) sagen, die Kante ist Brücke oder nicht. Sie können einfach alle Kanten aus Ihrem Zyklus nehmen und sicherstellen, dass es sich um eine Brücke handelt.