最小切割頂點/節點 - 不是邊線

Question

我們都知道並喜歡s-t最小切割算法，但它們都切割了圖中的邊緣。是否有任何變種切入節點？

Answer 1

因此，要使用s-t最小割算法，您需要將圖轉換爲流網絡。這給出了一個隱式有向圖（邊的正向流動方向）。你可以使用這個有向表示將圖轉換成應該解決這個問題的東西。本質上，你將每個頂點V（不包括源和匯）轉換成兩個頂點，稱它們爲A和B.A獲取V的所有邊內，B獲得所有V的外邊。然後創建最大容量爲無窮大的邊A - > B.

我想如果你運行通常的s-t最小切割算法，它只會選擇你創建的邊緣。我認爲唯一必要的修改是在A的入度是1的情況下，它可以選擇該邊切割，然後只選擇A作爲頂點。 （這取決於s-t算法的實現）

我希望這是有道理的。我不確定這是否行得通（即我不想考慮一個合適的證明），但是直覺上它會這樣。我所擁有的直觀觀點是，如果你切割一個「非頂點」邊緣，那麼你可能會削減一個「頂點」邊緣，因爲它具有與w.r.t相同的效果來斷開圖形。