《最大流問(wèn)題》PPT課件.ppt

《《最大流問(wèn)題》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《最大流問(wèn)題》PPT課件.ppt（30頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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