Minimale Anzahl von Kanten entfernen, um zwei Scheitelpunkte in einem Graphen zu trennen

Question

Hier versuche ich zwei Scheitelpunkte in einem Graphen mit minimaler Kantenentfernung zu trennen.

In diesem Diagramm zwischen zwei Ecken A und Z Sie die Antwort auf viele Arten finden. Auf optimale Weise können Sie nur eine Kante von A bis B entfernen.

Wenn es einen bestimmten Algorithmus dafür gibt?

Ich habe einige Vorschläge gefunden, um dies zu lösen, indem ich das Maximum-Flow-Min-Cut-Problem verwende, aber ich bekomme keine allgemeine Idee, dieses Problem in Max-Flow-Min-Cut-Theorem umzuwandeln. Auch in dem Prozess könnte ich am Ende eine Kante zwischen F und G entfernen, die nutzlos ist.

Answer 1

Dies kann mit Max Flow - Min Cut Problem gelöst werden.

Sie können Ihr Diagramm in Netzwerk-Flow-Modell wie folgt:
1. Betrachten A die Quelle Scheitel sein, Z der Spüle Scheitel sein.
2. Stellen Sie die Kapazität jeder Kante auf 1 Einheit ein.

Jetzt, lösen Sie das Max Flow - Min Cut Problem im obigen Netzwerk. Damit können Sie die Anzahl der kantenverknüpften Pfade von A bis Z finden. Entfernen Sie für jeden dieser Pfade die erste Kante (Kante, die von der Quelle A stammt).

Proof:
dass Beachten Sie nach oben Kanten zu entfernen, werden Sie nicht in der Lage sein A zu Z zu erreichen. Wenn Sie einen Pfad hätten, würde der Max-Flow-Algorithmus diesen Pfad in einen Satz von Edge-Disjoint-Pfaden eingefügt haben.
auch durch den Bau von Netzwerk können Sie nicht geringere Anzahl von Kanten entfernen trennen A von Z