最大流標(biāo)號(hào)法ppt課件

1、最大流問題 給定一個(gè)有向圖G(V,E)，其中僅有一個(gè)點(diǎn)的入次為零稱為發(fā)點(diǎn)源），記為vs，僅有一個(gè)點(diǎn)的出次為零稱為收點(diǎn)匯），記為vt，其余點(diǎn)稱為中間點(diǎn)?；靖拍罨靖拍?511 42352vsv2v1v3v4vt 對(duì)于G中的每一個(gè)弧(vi,vj)，相應(yīng)地給一個(gè)數(shù)cijcij0），稱為弧(vi,vj)的容量。我們把這樣的D稱為網(wǎng)絡(luò)或容量網(wǎng)絡(luò)），記為G(V,E,C)。 所謂網(wǎng)絡(luò)上的流，是指定義在弧集E上的函數(shù)ff(vi,vj)，并稱f(vi,vj)為弧(vi,vj)上的流量，簡(jiǎn)記為fij。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt標(biāo)示方式：每條邊上標(biāo)示兩個(gè)數(shù)字，

2、第一個(gè)是容量，第二是流量可行流、可行流的流量、最大流?？尚辛魇侵笣M足如下條件的流：（1容量限制條件：對(duì)G中每條邊(vi,vj), 有ijijcf 0（2平衡條件：對(duì)中間點(diǎn)，有：kkijijff（即中間點(diǎn)vi的物資輸入量等于輸出量）對(duì)收點(diǎn)vt與發(fā)點(diǎn)vs，有：Wffjjtisi（即vs發(fā)出的物資總量等于vt接收的物資總量），W是網(wǎng)絡(luò)的總流量?？尚辛骺偸谴嬖诘?，例如f=0就是一個(gè)流量為0的可行流。所謂最大流問題就是在容量網(wǎng)絡(luò)中尋找流量最大的可行流。一個(gè)流f=fij，當(dāng)fij=cij，則稱f對(duì)邊(vi, vj)是飽和的，否則稱f對(duì)邊(vi, vj)不飽和。最大流問題實(shí)際上是一個(gè)線性規(guī)劃問題。但利用它與

3、圖的密切關(guān)系，可以利用圖直觀簡(jiǎn)便地求解。 給定容量網(wǎng)絡(luò)G(V,A,E)，若點(diǎn)集V被剖分為兩個(gè)非空集合V1和V2，使 vsV1 ，vtV2，則把弧集(V1,V2)稱為分離vs和vt的割集。 顯然，若把某一割集的弧從網(wǎng)絡(luò)中去掉，則從vs到vt便不存在路。所以，直觀上說，割集是從vs到vt的必經(jīng)之路。3511 42352vsv2v1v3v4vt注：有向邊也稱為弧。對(duì)教材P259定義21的解釋vsv1v4v3vtv2邊集vs,v1），（v1,v3），（v2,v3），（v3,vt），（v4,vt是G的割集。其頂點(diǎn)分別屬于兩個(gè)互補(bǔ)不相交的點(diǎn)集。去掉這五條邊，則圖不連通，去掉這五條邊中的任意1-4條，圖仍然

4、連通。 割集的容量(簡(jiǎn)稱割量) 最小割集割集(V1, V2)中所有起點(diǎn)在V1，終點(diǎn)在V2的邊的容量的和稱為割集容量。例如下圖中所示割集的容量為53511 42352vsv2v1v3v4vt在容量網(wǎng)絡(luò)的所有割集中，割集容量最小的割集稱為最小割集最小割）。 對(duì)于可行流ffij，我們把網(wǎng)絡(luò)中使fijcij的弧稱為飽和弧，使fij0的弧稱為非零流弧。 設(shè)f是一個(gè)可行流，是從vs到vt的一條鏈，若滿足前向弧都是非飽和弧,后向弧都是都是非零流弧,則稱是可行流f的一條增廣鏈。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt 若是聯(lián)結(jié)發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈，我們規(guī)定鏈的方向

5、是從vs到vt，則鏈上的弧被分成兩類：前向弧、后向弧。 對(duì)最大流問題有下列定理： 定理1 容量網(wǎng)絡(luò)中任一可行流的流量不超過其任一割集的容量。 定理2最大流-最小割定理任一容量網(wǎng)絡(luò)中，最大流的流量等于最小割集的割量。 推論1 可行流f*fij*是最大流，當(dāng)且僅當(dāng)G中不存在關(guān)于f*的增廣鏈。 求最大流的標(biāo)號(hào)法求最大流的標(biāo)號(hào)法 標(biāo)號(hào)法思想是：先找一個(gè)可行流。標(biāo)號(hào)法思想是：先找一個(gè)可行流。對(duì)于一個(gè)可行流，經(jīng)過標(biāo)號(hào)過程得到對(duì)于一個(gè)可行流，經(jīng)過標(biāo)號(hào)過程得到從發(fā)點(diǎn)從發(fā)點(diǎn)vs到收點(diǎn)到收點(diǎn)vt的增廣鏈；經(jīng)過調(diào)的增廣鏈；經(jīng)過調(diào)整過程沿增廣鏈增加可行流的流量，整過程沿增廣鏈增加可行流的流量，得新的可行流。重復(fù)這一過

6、程，直到得新的可行流。重復(fù)這一過程，直到可行流無增廣鏈，得到最大流?？尚辛鳠o增廣鏈，得到最大流。 標(biāo)號(hào)過程: (1)給vs標(biāo)號(hào)(-,+)，vs成為已標(biāo)號(hào)未檢查的點(diǎn)，其余都是未標(biāo)號(hào)點(diǎn)。 (2)取一個(gè)已標(biāo)號(hào)未檢查的點(diǎn)vi，對(duì)一切未標(biāo)號(hào)點(diǎn)vj：若有非飽和弧(vi,vj)，則vj標(biāo)號(hào)(vi,l(vj)，其中l(wèi)(vj)minl(vi),cij fij，vj成為已標(biāo)號(hào)未檢查的點(diǎn)；若有非零弧(vj,vi)，則vj標(biāo)號(hào)(-vi,l(vj)，其中l(wèi)(vj)minl(vi), fji，vj成為已標(biāo)號(hào)未檢查的點(diǎn)。vi成為已標(biāo)號(hào)已檢查的點(diǎn)。 (3)重復(fù)步驟(2)，直到vt成為標(biāo)號(hào)點(diǎn)或所有標(biāo)號(hào)點(diǎn)都檢查過。若vt成為標(biāo)號(hào)

7、點(diǎn)，表明得到一條vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整過程；若所有標(biāo)號(hào)點(diǎn)都檢查過，表明這時(shí)的可行流就是最大流，算法結(jié)束。 調(diào)整過程：在增廣鏈上，前向弧流量增加l(vt)，后向弧流量減少l(vt)。 下面用實(shí)例說明具體的操作方法：例(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt在圖中給出的可行在圖中給出的可行流的基礎(chǔ)上，求流的基礎(chǔ)上，求vs到到vt的最大流。的最大流。(-,+)(vs,4)(-v1,1)(-v2,1)(v2,1

8、)(v3,1)(3,3)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)vsv2v1v3v4vt(vs,3)(-,+) 得增廣鏈，標(biāo)號(hào)結(jié)束，得增廣鏈，標(biāo)號(hào)結(jié)束，進(jìn)入調(diào)整過程進(jìn)入調(diào)整過程 無增廣鏈，標(biāo)號(hào)結(jié)束，得無增廣鏈，標(biāo)號(hào)結(jié)束，得最大流。同時(shí)得最小截。最大流。同時(shí)得最小截。下圖中已經(jīng)標(biāo)示出了一個(gè)可行流，求最大流-, vs, 3vs, 4v2, 4-v4, 2vsv1v2v3v4v5vs(4, 0)(5, 2)(1, 0)(4, 0)(1, 0)(2, 2)(3, 2)(4, 0)(2, 0)(5, 2)v4, 3如圖已經(jīng)得到增廣鏈，然后進(jìn)行調(diào)整。調(diào)整后的可行流如

9、下圖：vsv1v2v3v4v5vs(4, 3)(5, 2)(1, 0)(4, 3)(1, 0)(2, 2)(3, 2)(4, 0)(2, 0)(5, 5)-, vs, 3vs, 1v2, 1-v4, 1v3, 1v5, 1如圖已經(jīng)得到增廣鏈，然后進(jìn)行調(diào)整。調(diào)整后的可行流如下圖：vsv1v2v3v4v5vs(4, 4)(5, 2)(1, 0)(4, 4)(1, 0)(2, 2)(3, 1)(4, 1)(2, 1)(5, 5)-, vs, 3如圖所示最小割集的容量即當(dāng)前可行流的流量），就是最大流的流量。注：用該方法可以同時(shí)得到最小割集，即圖中連結(jié)已標(biāo)號(hào)的點(diǎn)與未標(biāo)號(hào)的點(diǎn)的邊集。具有實(shí)際背景的例子 國(guó)

10、慶大假期間旅游非?；鸨?，機(jī)票早已訂購(gòu)國(guó)慶大假期間旅游非?；鸨?，機(jī)票早已訂購(gòu)一空。成都一家旅行社由于信譽(yù)好、服務(wù)好一空。成都一家旅行社由于信譽(yù)好、服務(wù)好，所策劃的國(guó)慶首都游的行情看好，要求參，所策劃的國(guó)慶首都游的行情看好，要求參加的游客眾多，游客甚至不惜多花機(jī)票錢輾加的游客眾多，游客甚至不惜多花機(jī)票錢輾轉(zhuǎn)取道它地也愿參加此游。旅行社只好緊急轉(zhuǎn)取道它地也愿參加此游。旅行社只好緊急電傳他在全國(guó)各地的辦事處要求協(xié)助解決此電傳他在全國(guó)各地的辦事處要求協(xié)助解決此問題。很快，各辦事處將其已訂購(gòu)機(jī)票的情問題。很快，各辦事處將其已訂購(gòu)機(jī)票的情況傳到了總社。根據(jù)此資料，總社要作出計(jì)況傳到了總社。根據(jù)此資料，總社要

11、作出計(jì)劃，最多能將多少游客從成都送往北京以及劃，最多能將多少游客從成都送往北京以及如何取道轉(zhuǎn)機(jī)。下面是各辦事處已訂購(gòu)機(jī)票如何取道轉(zhuǎn)機(jī)。下面是各辦事處已訂購(gòu)機(jī)票的詳細(xì)情況表：的詳細(xì)情況表：成都成都重慶重慶武漢武漢上海上海西安西安鄭州鄭州沈陽沈陽昆明昆明廣州廣州北京北京成都成都105158121030重慶重慶561525武漢武漢10上海上海158西安西安86鄭州鄭州148沈陽沈陽18昆明昆明810廣州廣州82610用圖來描述就是成成重重武武昆昆上上廣廣西西鄭鄭沈沈京京85101581210305615251015886141881082610發(fā)點(diǎn)發(fā)點(diǎn)vs =成都，收點(diǎn)成都，收點(diǎn)vt =北京。前面已

12、訂購(gòu)機(jī)票情況表中的數(shù)字即是北京。前面已訂購(gòu)機(jī)票情況表中的數(shù)字即是各邊上的容量允許通過的最大旅客量），當(dāng)各邊上的實(shí)際客流量為各邊上的容量允許通過的最大旅客量），當(dāng)各邊上的實(shí)際客流量為零時(shí)略去不寫，以零流作為初始可行流。零時(shí)略去不寫，以零流作為初始可行流。利用標(biāo)號(hào)法經(jīng)5次迭代可以得到從成都發(fā)送旅客到北京的最大流量如圖所示重重武武昆昆上上廣廣西西鄭鄭沈沈京京成成301006122801251061010600010801810100W ( f* ) =10+6+12+30+12+10+5 = 85多個(gè)發(fā)點(diǎn)多個(gè)收點(diǎn)的情形對(duì)于多發(fā)點(diǎn)多收點(diǎn)的容量網(wǎng)絡(luò)的最大流問題可以通過添加兩個(gè)新點(diǎn)vs與vt擴(kuò)充為新的單發(fā)

13、點(diǎn)與單收點(diǎn)的容量網(wǎng)絡(luò)的方式解決。x1x2.xmy1y2.ynvsvt+其中vs到各已知點(diǎn)，以及各已知點(diǎn)到vt的弧的容量取為+。最大匹配問題考慮工作分配問題。有n個(gè)工人，m件工作，每個(gè)工人能力不同，各能勝任其中某幾項(xiàng)工作。假設(shè)每件工作只需一人做，每人只做一件工作。怎樣分配才能使盡量多的工作有人做，更多的人有工作做？該問題用圖論的語言可以描述為：在圖中，x1, x2, , xn表示工人，y1, y2, , ym表示工作，有向邊(xi, yj)表示工人xi勝任工作yj，因此得到一個(gè)二部圖。x1x2x3xny1y2y3ym如果記X=x1, x2, , xn，Y=y1, y2, , ym，則該二部圖可記

14、為G=(X, Y, E)，而上述的工作匹配問題就是：在圖G中找一個(gè)邊集E的子集，使得這個(gè)子集中任意兩條邊沒有公共端點(diǎn)，最好的方案就是要使得該子集中的邊數(shù)達(dá)到最大。定義：對(duì)于二部圖G=(X, Y, E)，M是邊集E的一個(gè)子集，如果M中的任意兩條邊沒有公共端點(diǎn)，則稱M是圖G的一個(gè)匹配也稱對(duì)集）。M中任意一條邊的端點(diǎn)v稱為關(guān)于M的飽和點(diǎn)，G中的其他頂點(diǎn)稱為非飽和點(diǎn)。若不存在另一匹配M1使得| M1 | | M |，則稱M為最大匹配。下面的二部圖表示了一個(gè)匹配問題x1x2x3x4y1y2y3y4y5x1x2x3x4y1y2y3y4y5x1x2x3x4y1y2y3y4y5它有如下兩個(gè)最大匹配：最大匹配問

15、題可以化為最大流問題求解?；姆绞筋愃朴诙喟l(fā)點(diǎn)多收點(diǎn)問題，具體做法是：在原二部圖中添加兩個(gè)點(diǎn)vs和vt，其中vs有以它為起點(diǎn)，以X中各點(diǎn)為終點(diǎn)的有向邊；連結(jié)vt有以它為終點(diǎn)，Y中各點(diǎn)為起點(diǎn)的有向邊。并且在這樣的圖中各邊上的容量取為1。若一條邊上的流量為1，則表示一個(gè)相應(yīng)的分配。如下圖x1x2x3xny1y2y3ymvsvt這樣最大匹配問題就化為對(duì)上圖的網(wǎng)絡(luò)的最大流問題。例x1y1有5位求職者和5項(xiàng)工作崗位，這5位求職者各自能勝任的工作如圖所示，問如何安排才能實(shí)現(xiàn)最大就業(yè)?x2x3x4y2y3y4y5x5vsvs首先將原圖擴(kuò)充成一個(gè)容量網(wǎng)絡(luò)，其中每邊的容量均為1。然后用標(biāo)號(hào)法來求最大流。x1y1x2x3x4y2y3y4y5x5vsvs-,+vs,1vs,1vs,1vs,1vs,1x1,1x1,1x1,1y1,1x1y1x2x3x4y2y3y4y5x5vsvs111-,+vs