Entfernen Sie die Mindestanzahl von Scheitelpunkten, um das Diagramm zu trennen

(Diese Antwort wurde ursprünglich als Teil der Frage gegeben, mit dem Ziel, sie zu überprüfen.)

Meine Intuition sagt mir, dass wir Max-Flow- und Min-Cut-Algorithmen verwenden können, um dieses Problem zu lösen:

Ersetzen Sie jede der ungerichteten Kanten durch ein Paar gerichteter Kanten.
Ersetzen Sie jeden Scheitelpunkt durch zwei Scheitelpunkte und die durch eine Kante verbunden sind. Alle eingehenden Kanten von werden mit , alle ausgehenden Kanten von werden mit . $v$ $v_\text{in}$ $v_\text{out}$ $v$ $v_\text{in}$ $v$ $v_\text{out}$
Versuchen Sie, einen Mindestschnitt zu finden . Die Kanten von beziehen sich auf die Eckpunkte, die entfernt werden müssen. $M$ $M$

FrankW
quelle

Mir ist nicht klar, warum dies garantiert funktioniert. Was ist, wenn der minimale Schnitt des modifizierten Diagramms einige Kanten enthält, die nicht zwischen

und

, sondern eine gerichtete Kante aus Schritt 1 der Lösung sind? Warum wird Ihrer Meinung nach jeder Min-Vertex-Schnitt des Originaldiagramms eins zu eins mit einem Min-Edge-Schnitt des modifizierten Graphen übereinstimmen? Ich denke, ein Beweis ist erforderlich.

v_{in}

$v_\text{in}$

v_{out}

$v_\text{out}$

Um die Antwort von FrankW zu unterstützen, folgen Sie bitte den folgenden Links. Es gibt ein Papier von Abdol-Hossein Esfahanian, das das Ersetzen einer ungerichteten Kante durch zwei gerichtete Kanten unterstützt. - networkx.github.io/documentation/latest/reference/generated/… - cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

Pawan Puttaswamy

@pawanp, ich folge dir nicht. Natürlich können Sie eine ungerichtete Kante durch zwei gerichtete Kanten ersetzen. Die Frage ist nicht, ob Sie dies tun können, sondern ob nach Anwendung des von FrankW aufgelisteten Algorithmus die Ausgabe garantiert eine korrekte Lösung für das ursprüngliche Problem darstellt. Ich sehe nicht, wie relevant die Manpage der NetworkX-Bibliothek ist. In Bezug auf das Papier: Es ist 14 Seiten lang, mit 11 verschiedenen Algorithmen, die meisten ohne Korrektheitsnachweis. Können Sie genauer sagen, welchen Teil Sie hier als relevant ansehen?

Entfernen Sie die Mindestanzahl von Scheitelpunkten, um das Diagramm zu trennen

Antworten: