Minimaler Schnitt durch Scheitelpunkte/Knoten - keine Kanten

Question

Wir alle kennen und lieben s-t Algorithmen für minimalen Schnitt, aber sie schneiden alle durch die Kanten in der Grafik. Gibt es Varianten, die Knoten durchschneiden?

Answer 1

Um den s-t Minimalschnitt-Algorithmus zu verwenden, müssen Sie Ihren Graphen in ein Flussnetzwerk umwandeln. Dies ergibt einen impliziten gerichteten Graphen (die Richtung des Vorwärtsflusses einer Kante). Sie können diese gerichtete Darstellung verwenden, um den Graphen in etwas zu verwandeln, das dies lösen soll. Im Wesentlichen transformiert man jede Ecke V (mit Ausnahme der Quelle und der Senke) in zwei Vertices, die man A und B nennt. A erhält alle V-In-Kanten, B erhält alle V-Out-Kanten. Sie erstellen dann die Kante A -> B mit einer maximalen Kapazität von unendlich.

Ich denke, wenn Sie den üblichen s-t Minimalschnitt-Algorithmus auf diesem ausführen, wird es nur die Kanten, die Sie erstellen, auswählen. Die einzige Modifikation, die ich für notwendig halte, ist in Fällen, in denen der In-Grad von A eins ist, kann es die zu schneidende Kante auswählen, aber dann einfach A als den Scheitelpunkt auswählen. (Dies hängt von der Implementierung des s-t-Algorithmus ab)

Ich hoffe, das macht Sinn. Ich bin mir nicht sicher, ob das funktioniert (d. H. Ich habe keine Lust, mir einen richtigen Beweis zu überlegen), aber es macht intuitiv Sinn, dass es so wäre. Die intuitive Idee, die ich habe, ist, dass, wenn Sie eine "nicht-vertex" Kante schneiden, Sie auch eine "Scheitelpunkt" Kante schneiden können, da es den gleichen Effekt hat, den Graph zu trennen.