最大流標號法ppt課件

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

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

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

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

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

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

7、點，表明得到一條vs到vt的增廣鏈，轉入調(diào)整過程；若所有標號點都檢查過，表明這時的可行流就是最大流，算法結束。 調(diào)整過程：在增廣鏈上，前向弧流量增加l(vt)，后向弧流量減少l(vt)。 下面用實例說明具體的操作方法：例(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在圖中給出的可行在圖中給出的可行流的基礎上，求流的基礎上，求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)(-,+) 得增廣鏈，標號結束，得增廣鏈，標號結束，進入調(diào)整過程進入調(diào)整過程 無增廣鏈，標號結束，得無增廣鏈，標號結束，得最大流。同時得最小截。最大流。同時得最小截。下圖中已經(jīng)標示出了一個可行流，求最大流-, 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)得到增廣鏈，然后進行調(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)得到增廣鏈，然后進行調(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如圖所示最小割集的容量即當前可行流的流量），就是最大流的流量。注：用該方法可以同時得到最小割集，即圖中連結已標號的點與未標號的點的邊集。具有實際背景的例子 國

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

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

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

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

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

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