我正在閱讀由Robert Sedgewick編寫的書算法中的Ford-Fulkerson maxflow算法。這裏作者提到如下Ford-Fulkerson最大流算法分析
Ë邊緣在最短增強路徑 實施福特 - 富爾克森maxflow算法的所需的流動 網絡採用V頂點增廣路徑和的數量最多爲EV/2 。
證明草圖:每個增強路徑具有 從剩餘網絡,因爲它對應要麼 變得滿額或 被排空後向邊緣前邊緣刪除的臨界邊緣的邊緣。每當邊緣是臨界邊緣時,穿過它的增大路徑的長度必須增加2.由於增加路徑的長度最多爲V,所以每條邊可以至多增加V/2路徑,並且路徑增加路徑的總數最多爲EV/2。
我上面的文字問題是
- 我們是如何走到說如果augumenting路徑長度爲atmost V,每一個邊緣可以在atmost V/2 augumenting路徑?
要求用簡單的例子來解釋上面的例子,如果可能的話。
這對於計算機科學SE更適合嗎? –