【正文】 ????????CvvfCvvffjiijjiijij ),( ),( ??增廣鏈以外各弧流量不變 標號算法 vs v2 v1 v3 vt 3 2 2 2 3 (0,+∞) ?重復標號過程 。 ? 給網(wǎng)絡中的各個點標號： ● 先給發(fā)點 vs標上 (0,+∞) 。 ● 檢查 vs給 v2標上 (vs,1)，檢查 v2,在弧 (v2,vt)上 ,f2t=C2t=2,不滿足標號條件，在弧 (v1,v2)上， f12=0,也不滿足標號條件，標號無法繼續(xù)。算法結(jié)束。 4 (vs,1) 2 2 2 0 2 2 如下圖所示，弧上數(shù)字表示該弧的容量，求該網(wǎng)絡的最大流。 最大流量為從發(fā)點流出的量 422)(21 ????? ss fffv這時的可行流就是所求的最大流 練習： 用標號法求圖 87所示網(wǎng)絡的最大流。 弧旁的數(shù)是 (cij， fij)。 圖 87 解： (1) 標號過程 ① 首先給 vs標上 (0， +∞) ② 檢查 vs，在弧 (vs， v2)上， fs2=cs2=3，不滿足標號條件。弧 (vs， v1)上， fs1=1， cs1=5， fs1＜ cs1，則 v1的標號為 (vs， l (v1))，其中 l (v1)=min［ l (vs)， (cs1fs1)］ =min［ +∞， 51］ =4 ③ 檢查 v1，在弧 (v1， v3)上， f13=2， c13=2，不滿足標號條件。 在弧 (v2， v1)上， f21=1＞ 0，則給 v2記下標號為 (v1， l (v2))，這里 l (v2)=min［ l (v1)， f21］ =min［ 4， 1］ =1 ④ 檢查 v2，在弧 (v2， v4)上， f21=3， c24=4， f24＜ c24，則給 v4標號 (v2， l (v4))，這里 l (v4)=min［ l (v2)， (c24f24)］ =min［ 1， 1］=1 在弧 (v3， v2)上， f32=1＞ 0，給 v3標號： (v2， l (v3))，這里 l (v3） =min［ l (v2)， f32］ =min［ 1， 1］ =1 ⑤ 在 v3， v4中任選一個進行檢查。例如 在弧 (v3， vt)上， f3t=1， c3t=2， f3t＜ c3t，給 vt標號為 (v3， l (vt))，這里 l (vt)=min［ l (v3)， (c3tf3t)］ =min［ 1， 1］ =1 因 vt有了標號，故轉(zhuǎn)入調(diào)整過程。 圖 88 (2) 調(diào)整過程按點的第一個標號找到一條增廣鏈，如圖 88中雙箭頭線表示。 易見 μ+=｛ (vs， v1)， (v3， vt)｝ μ=｛ (v2， v1)， (v3， v2)｝ 按 θ=1在 μ上調(diào)整 f。 μ+上： fs1+θ=1+1=2 f3t+θ=1+1=2 μ上： f21?θ=1?1=0 f32?θ=1?1=0 其余的 fij不變。 1V 11(V ,V ) 調(diào)整后得如下圖所示的可行流，對這個可行流進入標號過程，尋找增廣鏈。 開始給 vs標以 (0， +∞)，于是檢查 vs，給 v1標以 (vs,3)，檢查 v1，弧 (v1,v3)上， f13＝ c13，弧 (v2,v1)上， f21=0，均不符號條件，標號過程無法繼續(xù)下去，算法結(jié)束。 這時的可行流即為所求最大流。最大流量為 v(f)=fs1+fs2=f4t+f3t=5 與此同時可找到最小截集 ， 其中 V1為標號點集合， 為未標號點集合?；〖? 即為最小截集。 11(V , V ) 從一個費用最小的可行流 出發(fā)（這樣的可行流一定存在，因為費用 ，所以 就是一個流量為 0的最小費用流），找出這個可行流 的費用最小的一條增廣鏈 L，沿 L調(diào)整 ，直到找不到費用最小的增廣鏈，就得到了最小費用最大流。 第五節(jié) 最小費用流問題 對于網(wǎng)絡圖 G中的弧，除標明弧的容量 外，還要標明流過該弧單位流量的費用 ， G的一個可行流 ，使得流的總運輸費用： 達到最小。 特別，如果可行流是最大流時，此問題就是最小費用最大流問題。 ijcijb}{ ijff ???? Lji ijij fbfb ),()(}{ ijff ?0?ijb 0?fff最小費用流問題 最小費用最大流的基本思路 ? 例：以圖 86為例，求最小費用最大流?；∨詳?shù)字為(bij,cij)。 圖 86 (1) 取 f(0)=0 為初始可行流。 (2) 構(gòu)造賦權(quán)有向圖 W(f(0)) ，并求出從 v s 到 v t 的 最短路 (v s ,v 2 ,v 1 ,v t ) ，如圖 5 3 ( b )( 雙箭頭即為最短路 ) 。 (3) 在原網(wǎng)絡 D 中，與這條最短路相應的增廣鏈為 μ ＝ (v s ,v 2 ,v 1 ,v t ) 。 (4) 在 μ 上進行調(diào)整， θ ＝ 5 ，得 f(1)( 圖 5 3 ( c )) 。按照上述 算法依次得 f(1),f(2),f(3),f(4)，流量依次為 5 ， 7 ， 10 ， 11 ； 構(gòu)造相應的賦權(quán)有向圖為 W(f(1)),W(f(2)),W(f(3)),W(f(4)) ， 注意到 W(f(4)) 中已不存在從 v s 到 v t 的最短路， 所以 f(4)為最小費用最大流。 圖 53