《最大流問題》PPT課件.ppt

《《最大流問題》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《最大流問題》PPT課件.ppt（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1,第4節(jié) 網(wǎng)絡最大流問題,例 連接某產(chǎn)品產(chǎn)地vs和銷地vt的交通網(wǎng)如下：,,弧（vi，vj）：從vi到vj的運輸線， 弧旁數(shù)字：這條運輸線的最大通過能力,,制定一個運輸方案，使從vs到vt的產(chǎn)品數(shù)量最多。,2,弧旁數(shù)字： 運輸能力。,問題：這個運輸網(wǎng)絡中，從vs到vt的最大輸送量是多少？,3,7.4.1最大流的基本概念與定理,（1）. 網(wǎng)絡流,網(wǎng)絡流 對于網(wǎng)絡G=（V，A，C） ，定義在弧集合A上的 一個函數(shù)f = {f(vi ,vj)} 稱為網(wǎng)絡流， f(vi , vj) （簡稱fij）為弧aij ∈A上的流。,容量：在有向圖上，每條弧上給出的最大通過能力（最大可能負載）。cij 流量：網(wǎng)絡中加在弧上的負載量（實際負載量）。 fij,4,弧旁數(shù)字： 容量,弧旁數(shù)字： 流量,5,,6,（2）. 可行流,可行流 滿足下述條件的流 f 稱為可行流:,1)容量限制條件: 對每一弧(vi , vj )∈A 0≤fij ≤cij,2)平衡條件: 對中間點vi (i≠s,t ),有,V( f ) 稱為可行流 f 的流量,即發(fā)點的凈輸出量。,如所有fij=0， 零流。,可行流總是存在的,7,（3）. 最大流,若 V（f *） 為網(wǎng)絡可行流，且滿足： V（f *）=Max{V（f ）∣f }為網(wǎng)絡D中的任意 一個可行流，則稱f *為網(wǎng)絡的最大流。,（4）.前向弧與后向弧,設μ=（x,…,u，v,…A）是網(wǎng)絡G中的一條初等鏈并且定義鏈的方向是從x到A。若D中有弧（u，v），與μ方向一致，則稱（u，v）為鏈μ的前向弧，若D中有弧（u，v），與μ方向相反,則稱（v, u），為鏈μ的后向弧。,8,（5）. 增廣鏈,對可行流 f ={ fij }：,非飽和弧：fij cij,飽和?。篺ij =cij,非零流弧：fij 0,零流?。篺ij =0,鏈的方向：若是聯(lián)結(jié)vs和vt的一條鏈，定義鏈的方向是從vs到vt 。,,9,, = (v1,v2,v3,v4,v5,v6 ),+={(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6)}, - ={(v4,v5)},10,增廣 鏈 設 f 是一個可行流, 是從vs 到vt 的一條鏈,若滿 足下列條件,稱之為關于可行流 f 的一條增廣 鏈。,(vi , vj ) ∈ - 0 fij ≤ cij 后向弧 是非零流弧，,(vi , vj ) ∈ + 0≤ fij cij 前向弧是 非飽和弧，,11,（6）. 截集與截量,對于有向網(wǎng)絡G=(V,A,C） ，若S為V的子集， ，則稱弧集 為網(wǎng)絡G的一個截集，并將截集中所有弧容量之和稱為截容量，即 為截集 的截容量（簡稱為截量）。,（7）最小截與最小截量,若 是容量網(wǎng)絡中所有截集中截量最小的截集，即 則稱 為G上的最小截， 為上的最小截量。,12,性質(zhì) 任何一個可行流的流量V(f)都不會超過任一截集的容量。即,可行流f*，截集(V1*，V1*), 若V(f*)=C( V1*，V1*），,,,則f*必是最大流， (V1*，V1*) 必是D的最小截集。,,定理 若f*是網(wǎng)絡G=（V，A，C）上的可行流，則 可行流f*為最大的充要條件為μ中不存在關 于f*的增廣鏈。,最大流最小截量定理。任一個網(wǎng)絡D中，從vs 到 vt的最大流的流量等于分離vs，vt的最小截集的容量。,13,7.4.2尋求最大流的標號法（Ford—Fulkerson）,從任一個可行流 f 出發(fā)（若網(wǎng)絡中沒有給定 f ，則從零流開始），經(jīng)過標號過程與調(diào)整過程。,（一）標號過程,14,標號：,開始，vs 標上（0，∞），vs 是標號未檢查的點，其余點都是未標號點，一般地，取一個標號未檢查的點vi ，對一切未標號的點vj 。,（1）若弧（vi，vj）上，fijcij，則給vj 標號(i，l(vj))，,l(vj)=min[l (vi), cij-fij], vj 成為標號而未檢查的點。,（2）若弧（vj，vi）上，fji0，則給vj 標號(-i， l (vj))，,l (vj)=min[l (vi), fji], vj 成為標號而未檢查的點。,15,重復上述步驟，一旦vt被標號，則得到一條vs到vt的增廣鏈。若所有標號都已檢查過，而vt尚未標號，結(jié)束，這時可行流，即最大流。,（二）調(diào)整過程,從vt 開始，反向追蹤，找出增廣鏈 ，并在上進行流量調(diào)整。,（1）找增廣鏈,如vt 的第一個標號為k（或-k），則弧（vk，vt）∈（或弧（vt，vk) ∈)。檢查vk 的第一個標號，若為i（或-i），則(vi,vk) ∈ (或(vk,vi) ∈)。再檢查vi 的第一個標號,依此下去,直到vs 。被找出的弧構(gòu)成了增廣鏈 。,16,（2）流量調(diào)整,令調(diào)整量?是 l(vt)，構(gòu)造新的可行流 f ′，,令,去掉所有的標號,對新的可行流 f ′={ fij′},重新進入標號過程。,17,例 用標號法求下圖網(wǎng)絡的最大流。弧旁的數(shù)字是( cij , fij)。,解：（一）標號過程。,（1）給vs標上（0，∞）；,v2,v3,v1,,,,,vs,v4,vt,,,,,,,,,,,,,(3，3),,(4，3),(1，1),(5，3),(5，1),(2，2),(2，1),(1，1),(3,0),（0，∞）,在?。╲s，v2）上， fs2=cs2=3, 不滿足標號條件。,（vs，4）,18,（3）檢查v1，在?。╲2，v1）上，f210， 給v2標號 (-1, l(v2)),,,在?。╲1，v3）上，f13=2， c13=2，不滿足標號條件。,（-v1，1）,（4）檢查v2，在?。╲3，v2）上，f32=10， 給v3標號 (-2, l(v3)), 這里,（-v2，1）,19,在弧（v2，v4）上，f24=3，c24=4，f24c24, 給v4標號(2, l(v4)), 其中,（5）檢查v3，在弧（v3，vt）上，f3t=1， c3t=2， f3tc3t， 給vt標號 (3, l(vt)), 這里,vt得到標號，標號過程結(jié)束。,(v2，1),(v3，1),20,（二）調(diào)整過程,：從vt 開始逆向追蹤，找到增廣鏈。,（vs,v1,v2,v3,vt） ?=1，,在上進行流量 ?=1的調(diào)整，得 可行流 f ′ 如右 圖所示：,,21,去掉各點標號，從vs開始，重新標號。,點v1：標號過程 無法進行，所以 f ′即為最大流。,V（f ′）=3+2=5,（0，∞）,（vs，3）,22,例 用標號法求下圖網(wǎng)絡的最大流。弧旁的數(shù)字是( cij , fij)。,23,解： 第一輪 標號過程 （1）vs標（0，+∞），vs為已標號未檢查點。 （2）檢查vs，給v2標號（vs，l(v2)） ，vs成為已標號已檢查的點，v2成為已標號未檢查的點。 （3）檢查v2，給v1標號（-v2，l(v1)） 。同理給v4標號為（v2，1），v2成為已標號已檢查的 點，v1，v4成為已標號未檢查的點。 （4）檢查v1，給v3標號為（v1，2），v3成為已標號未檢 查的點。 （5）檢查v3，給vt標號為（ v3 ，2）。 因為vt已被標號，所以說明找到一條增廣鏈。 調(diào)整過程 按點的第一個標號，以vt點開始，回溯找到一條增廣 鏈， 如下圖紅線所示：,24,vt,(0， +∞),（vs，4）,（-v2，2）,（v2，1）,（v1，2）,（v3，2）,25,,vt,在增廣鏈上進行了流量調(diào)整。,前向弧,后向弧,于是調(diào)整后流量如下圖所示。,(0， +∞),（vs，4）,（-v2，2）,（v2，1）,（v1，2）,（v3，2）,26,vt,27,第二輪： 標號過程 （1）vs標（0，+∞），vs為已標號未檢查點。 （2）檢查vs，給v2標號（vs，2），v2成為已標號未檢查 的點。 （3）檢查v2 ，給v4標號（ v2 ，1）， v4成為已標號未檢 查的點。 （4）檢查v4 ，給vt標號為（ v4 ，1）， vt被標，轉(zhuǎn)入下 一階段。 調(diào)整過程 根據(jù)標號過程，以vt點開始，回溯找到一條增廣鏈，如 下圖紅線所示。,28,vt,（v2，1）,（v4，1）,29,增廣鏈上的三個弧都為前向弧，于是調(diào)整如下：,于是新調(diào)整的流量如下圖所示。,vt,(0， +∞),（vs，2）,（v2，1）,（v4，1）,30,第三輪 vs標（0,+∞）， v2標號（vs，1），檢查v2點，標號 過程無法繼續(xù)下去，于是說明了對于上圖所示的新 流，不存在增廣鏈，上圖所示的流就是最 大流，算法結(jié)束。 最大流量=3+3+2=8 最小截集為{（ vs, v1 ），（v2, v3），（v2,v4）}， 最小截量為8。,vt,(0， +∞),（vs，1）,