1、最大流問題 1技術教學 給定一個有向圖G(V,E)，其中僅有一個點的入次 為零稱為發點（源），記為vs，僅有一個點的出次為 零稱為收點（匯），記為vt，其余點稱為中間點。 基本概念基本概念 3 5 1 1 4 2 3 5 2 vs v2 v1v3 v4 vt 對于G中的每一個弧(vi,vj)，相應地給一個數cij （cij0），稱為弧(vi,vj)的容量。我們把這樣的D稱 為網絡（或容量網絡），記為G(V,E,C)。 2技術教學 所謂網絡上的流，是指定義在弧集E 上的函數ff(vi,vj)，并稱f(vi,vj)為 弧(vi,vj)上的流量，簡記為fij。 3,1 5,2 1,0 1,0 4,1

2、 2,2 3,1 5,2 2,1 vs v2 v1v3 v4 vt 標示方式：每條邊上標示兩個數字，第一個是容量，第二 是流量 3技術教學 可行流、可行流的流量、最大流。 可行流是指滿足如下條件的流： （1）容量限制條件：對G中每條邊(vi,vj), 有 ijij cf 0 （2）平衡條件： 對中間點，有： k ki j ij ff （即中間點vi的物資輸入量等于輸出量） 對收點vt與發點vs，有：Wff j jt i si （即vs發出的物資總量等于vt接收的物資總量），W是 網絡的總流量。 4技術教學 可行流總是存在的，例如f=0就是一個流量為0的可 行流。 所謂最大流問題就是在容量網絡中

3、尋找流量最大的可 行流。 一個流f=fij，當fij=cij，則稱f對邊(vi, vj)是飽和的， 否則稱f對邊(vi, vj)不飽和。 最大流問題實際上是一個線性規劃問題。 但利用它與圖的密切關系，可以利用圖直觀簡便地求 解。 5技術教學 給定容量網絡G(V,A,E)，若點集V被剖分 為兩個非空集合V1和V2，使 vsV1 ，vtV2， 則把弧集(V1,V2)稱為（分離vs和vt的）割割集集。 顯然，若把某一割集的弧從網絡中去掉， 則從vs到vt便不存在路。所以，直觀上說，割 集是從vs到vt的必經之路。 3 5 1 1 4 2 3 5 2 vs v2 v1v3 v4 vt 注：有向邊也稱為

4、弧。 6技術教學 對教材P259定義21的解釋 vs v1 v4 v3 vt v2 邊集（vs,v1），（v1,v3），（v2,v3），（v3,vt）， （v4,vt）是G的割集。其頂點分別屬于兩個互補不相交 的點集。去掉這五條邊，則圖不連通，去掉這五條邊中 的任意1-4條，圖仍然連通。 7技術教學 割集的容量(簡稱割量) 最小 割集 割集(V1, V2)中所有起點在V1，終點在V2的邊的容量 的和稱為割集容量。例如下圖中所示割集的容量為5 3 5 1 1 4 2 3 5 2 vs v2 v1v3 v4 vt 在容量網絡的所有割集中，割集容量最小的割集稱為 最小割集（最小割）。 8技術教學 對

5、于可行流ffij，我們把網絡中使fijcij的 弧稱為飽和弧，使fij0的弧稱為非零 流弧。 設f是一個可行流，是從vs到vt的一條鏈，若 滿足前向弧都是非飽和弧,后向弧都是都是非零 流弧,則稱是（可行流f的）一條增廣鏈。 3,1 5,2 1,0 1,0 4,1 2,2 3,1 5,2 2,1 vs v2 v1v3 v4 vt 若是聯結發點 vs和收點vt的一條鏈， 我們規定鏈的方向是 從vs到vt，則鏈上的 弧被分成兩類：前向 弧、后向弧。 9技術教學 對最大流問題有下列定理： 定理定理1 1 容量網絡中任一可行流的流量容量網絡中任一可行流的流量 不超過其任一割集的容量。不超過其任一割集的容

6、量。 定理定理2 2（最大流（最大流- -最小最小割定理割定理）任一容任一容 量網絡中量網絡中，最大流的流量等于最小，最大流的流量等于最小割割集集 的的割割量。量。 推論推論1 可行流可行流f*fij*是最大流，是最大流，當且當且 僅當僅當G中不存在關于中不存在關于f*的增廣鏈。的增廣鏈。 10技術教學 求最大流的標號法求最大流的標號法 標號法思想是：標號法思想是：先找一個可行流。先找一個可行流。 對于一個可行流，經過對于一個可行流，經過標號過程標號過程得到得到 從發點從發點vs到收點到收點vt的增廣鏈；經過的增廣鏈；經過調整調整 過程過程沿增廣鏈增加可行流的流量，得沿增廣鏈增加可行流的流量，

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

8、vt成為標號點或所有標號點 都檢查過。若vt成為標號點，表明得到一條vs到vt的 增廣鏈，轉入調整過程；若所有標號點都檢查過， 表明這時的可行流就是最大流，算法結束。 調整過程：在增廣鏈上，前向弧流量增加l(vt)，后 向弧流量減少l(vt)。 12技術教學 下面用實例說明具體的操作方法：例 (3,3) (5,1) (1,1) (1,1) (4,3) (2,2) (3,0) (5,3) (2,1) vs v2 v1v3 v4 vt (3,3) (5,1) (1,1) (1,1) (4,3) (2,2) (3,0) (5,3) (2,1) vs v2 v1v3 v4 vt 在圖中給出的可行在圖中

9、給出的可行 流的基礎上，求流的基礎上，求vs 到到vt的最大流。的最大流。 (-,+) (vs,4) (-v1,1) (-v2,1) (v2,1) (v3,1) (3,3) (5,2) (1,0) (1,0) (4,3) (2,2) (3,0) (5,3) (2,2) vs v2 v1v3 v4 vt (vs,3) (-,+) 得增廣鏈，標號結束，得增廣鏈，標號結束， 進入調整過程進入調整過程 無增廣鏈，標號結束，得無增廣鏈，標號結束，得 最大流。同時得最小截。最大流。同時得最小截。 13技術教學 下圖中已經標示出了一個可行流，求最大流 -, vs, 3 vs, 4 v2, 4 -v4, 2

10、vs v1 v2 v3 v4 v5 vs (4, 0) (5, 2) (1, 0) (4, 0) (1, 0) (2, 2) (3, 2) (4, 0) (2, 0) (5, 2) v4, 3 如圖已經得到增廣鏈，然后進行調整。 14技術教學 調整后的可行流如下圖： vs v1 v2 v3 v4 v5 vs (4, 3) (5, 2) (1, 0) (4, 3) (1, 0) (2, 2) (3, 2) (4, 0) (2, 0) (5, 5) -, vs, 3 vs, 1 v2, 1 -v4, 1 v3, 1 v5, 1 如圖已經得到增廣鏈，然后進行調整。 15技術教學 調整后的可行流如下圖

11、： vs v1 v2 v3 v4 v5 vs (4, 4) (5, 2) (1, 0) (4, 4) (1, 0) (2, 2) (3, 1) (4, 1) (2, 1) (5, 5) -, vs, 3 如圖所示最小割集的容量（即當前可行流的流量）， 就是最大流的流量。注：用該方法可以同時得到最小 割集，即圖中連結已標號的點與未標號的點的邊集。 16技術教學 具有實際背景的例子 國慶大假期間旅游非常火爆，機票早已訂購國慶大假期間旅游非常火爆，機票早已訂購 一空。成都一家旅行社由于信譽好、服務好，一空。成都一家旅行社由于信譽好、服務好， 所策劃的國慶首都游的行情看好，要求參加所策劃的國慶首都游的

12、行情看好，要求參加 的游客眾多，游客甚至不惜多花機票錢輾轉的游客眾多，游客甚至不惜多花機票錢輾轉 取道它地也愿參加此游。旅行社只好緊急電取道它地也愿參加此游。旅行社只好緊急電 傳他在全國各地的辦事處要求協助解決此問傳他在全國各地的辦事處要求協助解決此問 題。很快，各辦事處將其已訂購機票的情況題。很快，各辦事處將其已訂購機票的情況 傳到了總社。根據此資料，總社要作出計劃，傳到了總社。根據此資料，總社要作出計劃， 最多能將多少游客從成都送往北京以及如何最多能將多少游客從成都送往北京以及如何 取道轉機。下面是各辦事處已訂購機票的詳取道轉機。下面是各辦事處已訂購機票的詳 細情況表：細情況表： 17技術

13、教學 成都成都重慶重慶武漢武漢上海上海西安西安鄭州鄭州沈陽沈陽昆明昆明廣州廣州北京北京 成都成都105158121030 重慶重慶561525 武漢武漢10 上海上海158 西安西安86 鄭州鄭州148 沈陽沈陽18 昆明昆明810 廣州廣州82610 18技術教學 用圖來描述就是 成成 重重 武武 昆昆 上上 廣廣 西西 鄭鄭 沈沈 京京 8 5 10 15 8 12 10 30 5 6 15 25 10 15 8 8 6 14 18 8 10 8 2 6 10 發點發點vs =成都，收點成都，收點vt =北京。前面已訂購機票情況表中的數字即是北京。前面已訂購機票情況表中的數字即是 各邊上的

14、容量（允許通過的最大旅客量），當各邊上的實際客流量為各邊上的容量（允許通過的最大旅客量），當各邊上的實際客流量為 零時略去不寫，以零流作為初始可行流。零時略去不寫，以零流作為初始可行流。 19技術教學 利用標號法（經5次迭代）可以得到從成都發送旅 客到北京的最大流量如圖所示 重重 武武 昆昆 上上 廣廣 西西 鄭鄭 沈沈 京京 成成 30 10 0 6 12 2 8 0 12 5 10 6 10 10 6 0 0 0 10 8 0 18 10 10 0 W ( f* ) =10+6+12+30+12+10+5 = 85 20技術教學 多個發點多個收點的情形 對于多發點多收點的容量網絡的最大流問

15、題可 以通過添加兩個新點vs與vt擴充為新的單發點與 單收點的容量網絡的方式解決。 x1 x2 . xm y1 y2 . yn vs vt + + 其中vs到各已知點，以及各已知點到vt的弧的容量 取為+。 21技術教學 最大匹配問題 考慮工作分配問題。有n個工人，m件工作，每個工 人能力不同，各能勝任其中某幾項工作。假設每件 工作只需一人做，每人只做一件工作。怎樣分配才 能使盡量多的工作有人做，更多的人有工作做？ 該問題用圖論的語言可以描述為：在圖中，x1, x2, , xn表示工人，y1, y2, , ym表示工作，有向邊 (xi, yj)表示工人xi勝任工作yj，因此得到一個二部圖。 x

16、1 x2 x3 xn y1 y2 y3 ym 22技術教學 如果記X=x1, x2, , xn，Y=y1, y2, , ym，則該二 部圖可記為G=(X, Y, E)，而上述的工作匹配問題就 是：在圖G中找一個邊集E的子集，使得這個子集 中任意兩條邊沒有公共端點，最好的方案就是要使 得該子集中的邊數達到最大。 定義：對于二部圖G=(X, Y, E)，M是邊集E的一個 子集，如果M中的任意兩條邊沒有公共端點，則稱 M是圖G的一個匹配（也稱對集）。 M中任意一條邊的端點v稱為（關于M的）飽和點， G中的其他頂點稱為非飽和點。 若不存在另一匹配M1使得| M1 | | M |，則稱M為最 大匹配。

17、23技術教學 下面的二部圖表示了一個匹配問題 x1 x2 x3 x4 y1 y2 y3 y4 y5 x1 x2 x3 x4 y1 y2 y3 y4 y5 x1 x2 x3 x4 y1 y2 y3 y4 y5 它有如下兩個最大匹配： 24技術教學 最大匹配問題可以化為最大流問題求解。化的方式 類似于多發點多收點問題，具體做法是： 在原二部圖中添加兩個點vs和vt，其中vs有以它為 起點，以X中各點為終點的有向邊；連結vt有以它 為終點，Y中各點為起點的有向邊。并且在這樣的 圖中各邊上的容量取為1。若一條邊上的流量為1， 則表示一個相應的分配。如下圖 x1 x2 x3 xn y1 y2 y3 ym

18、 vs vt 這樣最大匹配問題就化為對上圖的網絡的最大流問題。 25技術教學 例 x1y1 有5位求職者和5項工作崗位，這5位求職者各自能勝 任的工作如圖所示，問如何安排才能實現最大就業? x2 x3 x4 y2 y3 y4 y5x5 vs vs 首先將原圖擴充成一個容量網絡，其中每邊的容量均 為1。然后用標號法來求最大流。 26技術教學 x1y1 x2 x3 x4 y2 y3 y4 y5x5 vs vs -,+ vs,1 vs,1 vs,1 vs,1 vs,1 x1,1 x1,1 x1,1 y1,1 x1y1 x2 x3 x4 y2 y3 y4 y5x5 vs vs 1 1 1 -,+ vs,1 vs,1 vs,1 x2,1 x2,1 y4,1 vs,1 27技術教學 x1y1 x2 x3 x4 y2 y3 y4 y5x5