分析

2012-07-11 41 views
1

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

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

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

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

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

請您在此understading幫助。

感謝您的時間和幫助。

回答

0

自從我查看所有這些最大流量的東西后,我已經有一段時間了,但是如果我正確地思考這個問題,那麼這裏是引用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

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

+0

感謝您的解釋。以上解釋中的非簡單路徑是什麼意思? – venkysmarty 2012-07-12 06:36:42

+0

你也可以請你說說你的意思是什麼「1來抵消已經流過的邊緣0,另一邊流過邊緣1」。「在上面第 – venkysmarty 2012-07-12 06:44:01

+0

段中,非簡單路徑是一個帶有循環的路徑(因爲簡單路徑是非循環的,非簡單路徑是循環的)。當我說1來抵消1流動時,你必須知道流程圖上的函數是如何工作的。 f(a,b)被定義爲在該方向上從a到b的流動。根據定義,f(b,a)= -f(a,b)。剩餘容量(a,b)= c(a,b) - f(a,b)。使用這兩個事實我們可以看出,如果f(a,b)= 1,那麼f(b,a)= -1,並且c(a,b)= 1-1 = 0並且c(b,a)= 1- (-1)= 2。-1來自f(b,a),它是-f(a,b)= -1 – NKamrath 2012-07-12 12:12:02