Gibt es einen Algorithmus, um einen minimalen Schnitt in einem ungerichteten Graphen zu finden, der Quelle und Senke trennt?

Question

Ich habe einen randgewichteten ungerichteten Graphen und 2 Knoten (oft Quelle und Senke genannt). Ich muss eine Menge von Kanten mit möglichst geringem Gewicht finden, die diese 2 Knoten in 2 schwache Komponenten trennt.

Ich weiß über Ford-Fulkerson's maximum flow algorithm und sein Theorem über maximum flow and minimum cut relation auf gerichtete Graphen.

Ich kenne auch eine Modifikation von Ford-Fulkersons Maximum-Flow-Algorithmus für ungerichtete Graphen, der jede ungerichtete Kante durch zwei entgegengesetzte gerichtete Kanten ersetzt und den Fluss zu beiden gleichzeitig aktualisiert. Aber mit dieser Modifikation wird der Max-Flow-min-cut-Satz scheint nicht mehr gültig zu sein, denn am folgende ungerichteten Graphen der minimalen Schnitt wird nicht korrekt ermittelt werden:

nodes: 0, 1, 2, 3 
edges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4 
source: 0 
sink: 3 

Max-Flow-min -Schnitt Theorem sagt, Minimum Schnitt sind diese Kanten, die Strömung ist gleich ihrer Kapazität, und durch die modifizierte Ford-Fulkerson, dass alle Kanten ist, die offensichtlich nicht der richtige Schnitt ist.

fand ich ein Stoer–Wagner algorithm for finding a global minimum cut in ungerichteten Graphen, aber das ist nicht ganz das, was ich will, da dieser Algorithmus keine Quelle nicht berücksichtigt und Waschbecken, und einen Schnitt finden, die die Knoten in der gleichen Komponente sein kann.

Gibt es einen Algorithmus, der effizient einen minimalen Schnitt in einem ungerichteten Graphen mit Quelle und Senke finden kann, der diese 2 spezifizierten Knoten trennt? Kann ich die oben erwähnten Algorithmen irgendwie ändern, damit sie für meinen Fall funktionieren?

Answer 1

Sie können einige Modifikationen des Ford-Fulkerson-Algorithmus verwenden.

1. Zuerst müssen Sie den maximalen Durchfluss zwischen Quelle und Senke finden und es wieder in Erinnerung bringen.
2. Entfernen Sie einige Kanten aus dem Diagramm.
3. Dann müssen Sie maximale Strömung in der neuen Grafik finden. Wenn der maximale Fluss nicht derselbe wie in Schritt eins ist, dann befindet sich diese Kante im minimalen Schnitt.
4. Return Rand der Grafik wählen, eine andere Kante und geht 2.

zu Schritt Wenn Sie maximalen Fluß zu finden, nur ungerichtete Kante als zwei gerichtete Kanten mit gleicher Kapazität berücksichtigen.