分析

Question

我被Cormen等讀取推流算法在算法導論

我具有其中提到如下理解引理26.20 difficulaty：

設G =（ V，E）是具有源s和宿t的流網絡，並且假設在G中是預流。然後，對於任何溢出頂點u，在殘差網絡Gf中存在從u到s的簡單路徑。

要查看此leema的上下文可以在以下鏈接找到。

http://integrator-crimea.com/ddu0164.html

請您在此understading幫助。

感謝您的時間和幫助。

Answer 1

自從我查看所有這些最大流量的東西后，我已經有一段時間了，但是如果我正確地思考這個問題，那麼這裏是引用26.20的意思。

很明顯，有一條從s - > u的路徑，因爲在u中有多餘。引理要考慮的重要部分是它指出有一條從u - > s的簡單路徑，它與原始流的相反方向導致u的溢出（因爲流起源於s並且傳播到u）。由於在u中有溢出，所以從s→u有一條簡單的路徑，在整個路徑中至少有1個單位的流量。即使c（a，b）= 1且f（a，b）= 1使得c（a，b）= 0，其中a和b都是該簡單路徑中的所有頂點對，那麼c（b，a） （b，a）= f（b，a）= f（b，a）= 1 - （ - 1）= 2。因此，在達到該方向上的容量之前，您可以將2個單位推回該邊緣（1以抵消已經流動的1使得流動超過該邊緣0，另一個流動使該流動超過該邊緣1）。

你知道這是一條簡單路徑的原因是因爲如果沒有從s - > u的簡單路徑，那麼根本就沒有流量通過你。這是因爲即使沒有簡單的方法從s到達u，也必須至少有一個簡單的方法，否則所有的流將被捕獲在非簡單路徑中，這意味着沒有任何路徑會通過u。

照片這個。繪製一個流程圖，其中源完全通過一對節點循環。是否有可能擊中你（選擇一個節點），而不會將簡單的剩餘路徑返回給s？現在嘗試製作一個在幾個邊緣都流出來的流動都被導入到u中。現在嘗試找到返回到s的簡單路徑。這可能證明了26.20在說什麼。其中一些引理很難理解，但一旦你真的想到它，它通常是有道理的。他們只是通過相互矛盾的證明來證明這是正式證明他們所說的最好方法。另外，請查看wiki頁面，它總是有一些很好的見解！ http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm

希望有道理，我願意和你一起工作，如果它不只是讓我知道！