Ford-Fulkerson方法中的修改

Question

我想在流網絡G中的所有最小切割中找到包含最小邊數的 積分容量。我們怎樣才能 修改G的能力，以創建一個新的流網絡G「中的任何最低 切G」是G. 來源與邊緣的最小數量的削減最低 - Cormen

Answer 1

可以說的圖G有頂點n。

我們定義容量，以用於G'電弧e'對應於弧e在G作爲c(e') = c(e) * n + 1。

因此，G'中的切割值正好是G中的切割值+切割中的邊緣數量的n倍。

可以說我們現在有一個最小值爲G'的值爲n * x + a。這意味着G中的剪切值是x。如果在G中存在具有較小值y < x的切割，則該切割將具有值n * y + b <= n * (y+1) <= n * x < n * x + a，這與在G'中值n * x + a的切割最小的事實相矛盾。我們剛剛證明，G'中的每個最小剪輯也是G中的最小剪輯。但是，接下來的結果是，G'中的最小剪輯是G中的最小剪輯，並且在G中具有所有最小剪輯的最小剪輯數。