Ford-Fulkerson最大流算法分析

我正在閱讀由Robert Sedgewick編寫的書算法中的Ford-Fulkerson maxflow算法。這裏作者提到如下Ford-Fulkerson最大流算法分析

Ë邊緣在最短增強路徑實施福特 - 富爾克森maxflow算法的所需的流動網絡採用V頂點增廣路徑和的數量最多爲EV/2 。

證明草圖：每個增強路徑具有從剩餘網絡，因爲它對應要麼變得滿額或被排空後向邊緣前邊緣刪除的臨界邊緣的邊緣。每當邊緣是臨界邊緣時，穿過它的增大路徑的長度必須增加2.由於增加路徑的長度最多爲V，所以每條邊可以至多增加V/2路徑，並且路徑增加路徑的總數最多爲EV/2。

我上面的文字問題是

我們是如何走到說如果augumenting路徑長度爲atmost V，每一個邊緣可以在atmost V/2 augumenting路徑？

要求用簡單的例子來解釋上面的例子，如果可能的話。

來源

2016-04-29 venkysmarty

這對於計算機科學SE更適合嗎？ –

首先需要證明前面的語句

每一次的邊緣是一個重要的優勢，增廣路徑的長度，通過它必須由2

增加的路徑長度最多爲V，因爲穿過頂點兩次是沒有意義的（在這樣的路徑上移除頂點x的兩個出現點之間的所有邊，並且您仍然有一條良好的路徑，其容量至少是原始的路徑）。因此，如果路徑長度至多爲V，並且每當邊緣爲臨界時，路徑的長度增加2，則邊緣可以是至多V/2次的關鍵。

來源

2016-04-29 10:11:52 Sorin

感謝您的解釋。對不起，我沒有安靜下來。你的意思是「刪除這樣一條路徑上兩個頂點x之間的所有邊」。？ – venkysmarty

如果你有一個路徑'source，a，B，c，d，e，f，g，B，sink'，那麼你可以通過消除'B'到'得到'源，a，B，匯'。新路徑總是到達相同的目的地，並且其容量至少與原始較長路徑一樣大。基本上說它是兩次通過一個頂點沒有意義。 – Sorin

OP應該標記爲正確的，這是一個很好的答案！ – darkhipo

Ford-Fulkerson最大流算法分析

回答

相關問題