Suche nach allen unabhängigen Verbindungen in Grafik

Question

Ich habe eine ungerichtete Grafik. Gibt es einen effizienten Algorithmus, um alle unabhängigen Verbindungen zwischen zwei Knoten zu finden? Mit unabhängig meine ich, dass diese Verbindungen gemeinsame Knoten haben können, aber keine gemeinsamen Kanten haben können.

In diesem Beispiel gibt es 2 unabhängige Verbindungen von 0 bis 8 (0-2-3-4-8 oder 0-5-6-7-8). Ich habe versucht, den Breadth-First-Suchalgorithmus kontinuierlich zu verwenden, während ich Kanten, die ich schon gesehen habe, "pseudo-radierst". Das Problem ist, dass ich auf diese Weise Graphen durchgehen kann: 0-5-4-8, was nicht richtig ist, weil ich keinen anderen Weg gehen kann.

Danke für jede Hilfe!

Answer 1

Was Sie interessieren, ist Min-Cut-Problem zwischen einer Quelle und Senke zu lösen (der erste der Knoten von Interesse für Sie ist eine Quelle und der zweite ist eine Senke).

Here können Sie über den Ansatz für diese Aufgabe lesen. Grundsätzlich verbinde ich mich mit einem Theorem, das beweist, dass der maximale Fluss zwischen der Quelle und der Senke gleich dem minimalen Schnitt ist. Sie interessieren sich für den minimalen Schnitt, da dies genau die minimale Anzahl von Kanten ist, die entfernt werden müssen, um die Verbindung zwischen Quelle und Senke zu trennen.

Wenn Sie eine Ford Fulkerson max flow algorithm ausführen, können Sie die verschiedenen Pfade von der Quelle zur Senke rekonstruieren, wobei Sie berücksichtigen, welche Rückkanten Kapazität haben, nachdem der Algorithmus beendet ist. Eine letzte Anmerkung - Ford Fulkerson wird klassisch in gerichteten Graphen beschrieben. Um es für Ihren ungerichteten Fall arbeiten zu lassen, stellen Sie jede Kante als zwei separate gerichtete Kanten dar, die in entgegengesetzte Richtungen weisen. Alle Ihre anfänglichen Kapazitäten sollten gleich 1 sein.