1、第5章 圖論與網絡分析,圖的基本概念,網絡分析,最小支撐樹問題 最短路徑問題 網絡最大流問題,圖論起源：哥尼斯堡七橋問題,問題：一個散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點？,結論：每個結點關聯的邊數均為偶數,1 圖的基本概念,由點和邊組成，記作G=(V，E)，其中V=(v1，v2，vn)為結點的集合，E=(e1，e2，em) 為邊的集合。,點表示研究對象,邊表示研究對象之間的特定關系,1. 圖,p114,圖,無向圖，記作G=(V，E),有向圖，記作D=(V，A),例1：哥尼斯堡橋問題的圖為一個無向圖。,有向圖的邊稱為弧。,2、圖的分類,例,圖1,圖2,3、鏈

2、與路、圈與回路,鏈,點邊交錯的序列,路,點弧交錯的序列,回路,起點=終點的路,無向圖：,有向圖：,鏈與路中的點均不相同，則稱為初等鏈 (路)類似可定義初等圈（回路）,4、連通圖,G1為不連通圖， G2為連通圖,例 ：,5、支撐子圖,圖G=(V，E)和G=(V ，E )，若V =V 且E E ，則稱G 為G的支撐子圖。,G2為G1的支撐子圖,例 ：,G2 是G1 的子圖；,例 ：,6、賦權圖（網絡）,圖的每條邊都有一個表示一定實際含義的權數，稱為賦權圖。記作D=(V，A，C)。,例 ：,2 最小支撐樹問題,本節(jié)主要內容：,樹,支撐樹,最小支撐樹,樹：無圈的連通圖，記為T。,一、樹的概念與性質,樹

3、的性質： （1）樹的任2點間有且僅有1鏈； （2）在樹中任去掉1邊，則不連通；故樹是使圖保持 連通且具有最少邊數的一種圖形 （3）在樹中不相鄰2點間添1邊，恰成1圈； （4）若樹T有m個頂點，則T有m-1條邊。,若一個圖 G =（V , E）的支撐子圖 T=（V , E） 構成樹，則稱 T 為G的支撐樹，又稱生成樹。,二、圖的支撐樹,例,例 某地新建5處居民點，擬修道路連接5處，經勘測其道路可鋪成如圖所示。為使5處居民點都有道路相連，問至少要鋪幾條路？,解：,該問題實為求圖的支撐樹問題，共需鋪4條路。,圖的支撐樹的應用舉例,用破圈法求出下圖的一個生成樹。,最小支撐樹：求網絡的支撐樹，使其權和最

4、小。,三、最小支撐樹問題,算法1（破圈法）： 在給定的賦權的連通圖上找一個圈； 在所找的圈中去掉一條權數最大的邊(若有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條)： 若所余下的圖已不含圈，則計算結束，所余下的圖即為最小支撐樹，否則，返問。,例 求上例中的最小支撐樹,解：,5,5.5,v1,v2,v3,v4,v5,3.5,7.5,4,2,3,4,算法2（避圈法）：從某一點開始，把邊按權從小到大依次添入圖中，若出現圈，則刪去其中最大邊，直至填滿n-1條邊為止（n為結點數） 。,最小生成樹舉例： 某六個城市之間的道路網如圖 所示，要求沿著已知長度的道路聯結六個城市的電話線網，使電話線的總

5、長度最短。,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,聯系今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。,練習今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個

6、最經濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費

7、用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數字所示。要求設計一個最經濟的煤氣管道路線，并求所需的總費用。,此即為最經濟的煤氣管道路線，所需的總費用為25萬元,3最短路徑問題,最短路問題是在一個網絡（賦權有向圖）中尋找從起點到某個節(jié)點之間一條最短的路線?，F欲求出1至6距離最短的路徑。,基本思想：從起點vs開始，逐步給每個結點vj標號dj ,vi，其中dj為起點vs到vj的最短距離， vi為該最短路線上的前一節(jié)點. 若給終點vt標上號dt ,vi, 表示已求出v1至vt的最短路其最短路長為 dt ，最短路徑可根

8、據標號 vi 反向追蹤而得,最短路問題的Dijstra解法 （狄克拉斯）,0, v1,1, v1,(3) 考慮所有這樣的邊vi , vj，其中viVA， vjVB，挑選其中與起點v1距離最短（mindi+cij）的vj，對vj進行標號,(4) 重復(2)、(3)，直至終點vn標上號dn, vi，則dn即為v1 vn的最短距離，反向追蹤可求出最短路。,(1)給起點v1標號0, v1,0, v1,1, v1,(3) 考慮所有這樣的邊vi , vj，其中viVA， vjVB，挑選其中與起點v1距離最短（mindi+cij）的vj，對vj進行標號,(4) 重復(2)、(3)，直至終點vn標上號dn,

9、vi，則dn即為v1 vn的最短距離，反向追蹤可求出最短路。,(1)給起點v1標號0, v1,3, v1,0, v1,1, v1,3, v1,5, v3,0, v1,1, v1,3, v1,5, v3,6, v2,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,12, v5,此時終點v9已標號12, v5，則12即為v1 vn的最短距離，反向追蹤可求出最短路,0, v1,1, v1,3, v1,5,

10、v3,6, v2,9, v5,10, v5,12, v5,v1到v9的最短路為：v1 v3 v2 v5 v9，最短距離為12,p119,練習：用Dijkstra算法求下圖中V1至V8的最短路及最短路長。,關鍵線路： 1.V1-V2-V4-V6-V8 2.V1-V2-V4V7-V8 最短路長：12,課堂練習 無向圖情形,求網絡中v1至v7的最短路。,課堂練習 無向圖情形,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/ v4,7,v3,8,v5,13,v6,課堂練習 無向圖情形,答案（2）：,v1,v2,v3,v4

11、,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/ v4,7,v3,8,v5,13,v6,最短路模型的應用設備更新問題,例 某工廠使用一種設備，這種設備在一定的年限內隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設備是否更新。若購置設備，每年需支付購置費用；若繼續(xù)使用舊設備，需要支付維修與運行費用。計劃期（五年）內中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內的總費用最小。,最短路模型的應用設備更新問題,分析：,結點：V=v1，v6， vi表示第i年初；,弧

12、： A=(vi，vj) 表示第i年初購買，用至第j年初；i= 1,5; j= 2,6,權cij： i年初 j年初的費用，即cij= i年初購買費+（j-i）年里的維修費,通路：表示一個更新策略。例如v1-v2-v6表示第一年購買用到第二年更新，繼續(xù)用至第五年末的一個更新策略,最短路模型的應用設備更新問題,0,v1,16,v1,22,v1,30,v1,41,v1,53,v3/v4,16,30,22,41,59,16,22,30,41,17,23,31,17,23,18,建模：,求解：,求得兩個最優(yōu)更新策略： v1-v4-v6，即第一年購買設備，用到第四年更新，再用至第五年年末 V1-v3-v6，

13、即第一年購買設備，用到第三年更新，再用至第五年年末 最優(yōu)費用為53,計劃期（五年）內中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內的總費用最小。,練習：設備更新問題,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,算法的基本思路與步驟： 首先設任一點vi到任一點vj都有一條弧。無弧相連的點之間假設存在權為+的弧相連。 從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個點vi再沿弧(vi ,vj)到vj。則v1到vi的這條路必然也是v1到vi的

14、所有路中的最短路。 設P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程：,(二) Ford法(逐次逼近法) （權有負數）,開始時，令 即用v1到vj的直接距離做初始解。,從第二步起，使用遞推公式：,求 ，當進行到第t步，若出現,即為v1到各點的最短路長。,則停止計算，,例:,從第二步起，使用遞推公式,從第二步起，使用遞推公式,為了求出從v1到各個點的最短路，一般采用反向追蹤的方法：如果已知d(vs ,vj),那么尋求一個點vk ,使得d(vs,vk)+wkj=d(vs ,vj) ,然后記錄下(vk ,vj)；在看d(vs ,vk) ,尋求一個點vi ,使得d(v

15、s ,vi)+wik=d(vs ,vk)依次類推，一直到達為止。這樣，從vs到vj的最短路是（vs ,vi ,vk ,vj）,d(v1 ,v8)=6, 由于d(v1 ,v6)+w68=(-1)+7記錄下v6 由于d(v1 ,v3)+w36=d(v1 ,v6) , 記錄下v3 由于d(v1 ,v1)+w13=d(v1 ,v3), 于是，從v1到v8的最短路是(v1 ,v3 ,v6 ,v8)。,4 網絡最大流問題,引例：下圖為V1到V6的一交通網，權表示相應運輸線的最大通過能力，制定一方案，使從V1到V6的運輸產品數量最多。,已知網絡D=（V，A，C），其中V為頂點集，A為弧集，C=cij為容量集

16、， cij 為?。╲i，vj ）上的容量。現D上要通過一個流f=fij，其中fij 為?。╲i，vj ）上的流量。 問題：應如何安排流量fij可使D上通過的總流量v最大？,一、一般提法,二、最大流問題的數學模型,max v=v（f）,容量約束,平衡約束,P125,滿足上述所有約束條件的流成為可行流。,（1）容量條件：對于每一個?。╲i ,vj）A，有0 fij cij 。 （2）平衡條件： 對于發(fā)點vs，有 對于收點vt ，有 對于中間點，有 為可行流f 的流量(發(fā)點的凈輸出量或收點的凈輸入量),1、稱滿足下列條件的流f為可行流：,三、 基本概念和定理,可行流特征： （1）容量條件：每一個弧上

17、的流量不能超過該弧的容量。 （2）每一個中間點的流入量與流出量的代數和為零。（轉運的作用） （3）出發(fā)點的總流出量與收點的總流入量必相等。,任意一個網絡上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。 網絡系統(tǒng)中最大流問題就是在給定的網絡上尋求一個可行流f,其流量v(f)達到最大值。,可行流中 fijcij 的弧叫做飽和??； fijcij的弧叫做非飽和??； fij0 的弧叫做非零流弧； fij0 的弧叫做零流弧。,2、飽和弧與零流弧,f為一可行流，u為vs至vt的鏈，令u+=正向弧， u-=反向弧。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關于f的一條增廣鏈。,3、增廣

18、鏈,增廣鏈,顯然圖中增廣鏈不止一條,增廣鏈,容量網絡D =（V，A，C），vs為始點，vt為終點。如果把V分成兩個非空集合 使 則所有始點屬于V1，而終點屬于 的弧的集合 ，稱為分離vs和vt的截集。,4、截集和截集的截量,截集是連接起點和終點的必經之路。,截集 中所有弧的容量之和，稱為這個截集的截量，記為,則截集為,設,容量為24,設,則截集為,容量為20,流量與截量的關系：,任一可行流的流量都不會超過任一截集的截量,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,最大流最小截定理：任一網絡D中，從v s至v t 的最大流的流

19、量等于分離v s、v t 的最小截集的容量。,例. 如圖所示的網絡中，弧旁數字為(cij ,fij ),v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）確定所有的截集； （2）求最小截集的容量； （3）證明圖中的流為最大流；,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，,截集為(vs,v1), (vs,v2)，截量為：6,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）

20、,（2，2）,（1）所有的截集：, V1=vs，截集為(vs,v1), (vs,v2)，截量為：6,V1=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集為(vs,v1), (vs,v2)，截量為：6 V1=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7 V1=vs ,v2，截集為，截量為：7, V1=vs，截集為(vs,v1), (vs,v2)，截量為：6 V1=vs ,v1，截集為(vs,v2), (v1

21、,vt)，截量為：7 V1=vs ,v2，截集為，截量為：7 V1=vs ,v3，截集為，截量為：12,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,（1）所有的截集：, V1=vs，截集為(vs,v1), (vs,v2)，截量為：6 V1=vs ,v1，截集為(vs,v2), (v1,vt)，截量為：7 V1=vs ,v2，截集為，截量為：7 V1=vs ,v3，截集為，截量為：12 V1=v

22、s ,v1,v2，截集為，截量為：5,（2）最小截量min C (V1,V2)= 5； （3）v(f*)=5= min C (V1,V2) f*是最大流。,最大流判定定理： 可行流f* 是最大流的充分必要條件是當且僅當不存在從vs到vt 的關于f *的增廣鏈。,p124,尋求網絡最大流問題的主要步驟：（1）確定初始可行流（觀察法和零流法）（2）檢驗當前可行流是否是網絡中的最大流(對已知可行流用標號法尋找可擴充鏈，若存在，則當前可行流不是最大流，轉(3)；若不存在，則是最大流）（3）將當前的可行流調整成一個流量更大的新可行流再由(2)檢驗,四、求最大流方法標號法,思路：從始點開始標號，尋找是否存

23、在增廣鏈。給vj標號為j,vi，其中j為調整量， vi為前一節(jié)點。,標號具體步驟：,（b） 標號終止，說明不存在可擴充鏈，當前即為流為最大流，并得最小截集,（a） 說明存在可擴充鏈,反向追蹤找出 ,轉(4),例5 用標號法求下面網絡的最大流。,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,步驟：(1)給vs標號為,vs， 選與vs關聯的流出未飽和弧(vs, vj) ,給vj標號j,vs,其中j=csj-fsj,例5 用標號法求下面網絡的最大流。,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2

24、,1）,（5,3）,例5 用標號法求下面網絡的最大流。,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,例5 用標號法求下面網絡的最大流。,vt已標號，得到一條增廣鏈u(反向追蹤)，轉（5）； vt未標號，且無法再標號,此時的流為最大流,此時的截集為最小截。,（4）重復（2）,（3），依次進行的結局可能為：,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,例5 用標號法

25、求下面網絡的最大流。,vt已標號，得到一條增廣鏈u(反向追蹤)，轉（5）； vt未標號，且無法再標號,此時的流為最大流,此時的截集為最小截。,（4）重復（2）,（3），依次進行的結局可能為：,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,例5 用標號法求下面網絡的最大流。,vt已標號，得到一條增廣鏈u(反向追蹤)，轉（5）； vt未標號，且無法再標號,此時的流為最大流,此時的截集為最小截。,（4）重復（2）,（3），依次進行的結局可能為：,例5 用標號法求下面網絡的最大流。,(5)調整。取 =t，令,，得新流 fij轉(1)。,（2

26、,2）,（1,0）,（3,3）,（1,1）,（4,4）,（5,2）,（3,0）,（2,1）,（5,4）,此時標號無法進行，當前流為最大流，最大流量為5；最小截為(vs,v2), (v1,v3)，截量為：5,練習： 有三個發(fā)電站v1,v2,v3，發(fā)電能力分別為15、10和40兆瓦，經輸電網可把電力送到8號地區(qū)，電網能力如圖所示。求三個發(fā)電站輸到該地區(qū)的最大電力。,v0,（1）由于網絡圖中只有一個發(fā)點和一個收點，所以有必要添加一個虛設的起點 和弧 弧上各容量為 ，分別為三點 的發(fā)電能力，如圖所示：,v0,10,10,15,15,15,0,10,10,10,10,15,25,(2)由觀察法得一初始可

27、行流 即圖上所標 。 為弧 上容量， 為弧上流量。,(2)由觀察法得一初始可行流 即圖上所標 。 為弧 上容量， 為弧上流量。,v3,(40,10),(15,15),(30,10),(15,15),(45,25),(10,10),(15,15),(10,0),(20,10),v0,(10,10),(15,15),(40,10),(3)用標號法尋找可擴充鏈,v0,|,|,v6,|,v5,v4,|,v2,v1,v7,v8,反向追蹤，得一v0-v8的可擴充鏈: v0-v3-v6-v5-v2-v7-v8,v3,(40,10),(15,15),(30,10),(15,15),(45,25),(10,10

28、),(15,15),(10,0),(20,10),v0,(10,10),(15,15),(40,10),v0,|,|,v6,|,v5,v4,|,v2,v1,v7,v8,(4)調整流量。由可擴充鏈確定一新可行流 ，可擴充鏈上前向弧上流量均增加,(45,35),(40,20),(10,10),(20,20),(30,20),(40,20),(5)繼續(xù)用標號法檢驗當前可行流是否為最大流,v3,(40,20),(15,15),(30,20),(15,15),(45,35),(10,10),(15,15),(10,10),(20,20),v0,(10,10),(15,15),(40,20),v0,|,|

29、,v6,|,v5,v4,v2,v1,v7,v8,|,標號完畢，且終點未標號。這說明網絡中已找不到可擴充鏈，當前即為最大流，最大流流量為： 20+15+1045 即三個發(fā)電站輸送到8號地區(qū)的最大電力為45兆瓦。,練習：圖中A、B、C、D、E、F分別表示陸地和島嶼，表示橋梁及其編號。河兩岸分別互為敵對的雙方部隊占領，問至少應切斷幾座橋梁（具體指出編號）才能達到阻止對方部隊過河的目的。試用圖論方法進行分析。,分析：轉化為一個網絡圖，弧的容量為兩點間的橋梁數。,則問題為求最小截。,步驟（1）確定初始可行流,1(1),1(0),分析：轉化為一個網絡圖，弧的容量為兩點間的橋梁數。,則問題為求最小截。,答案

30、：最小截為AE、CD、CF,A,B,C,D,E,F,2(1),1(1),1(1),1(1),1(0),2(2),2(1),2(1),2(1),2(2),2(2),步驟（1）確定初始可行流,（2）標號法求最大 流得最小截,1(0),1(0),2(0),2(0),2(0),案例：有一批人從我國A城赴俄羅斯B城，可能的旅行路線如圖：,邊防隊擬建立足夠數量檢查站以便使每輛汽車至少必經過一個檢查站，建立檢查站的費用根據各路段條件有所不同（如圖數字所示），求最小費用解。,（分析：最小截問題）,分析：轉化為一個網絡圖，弧的容量為各路段得費用。則問題為求最小截。 步驟,a,B,A,b,c,d,e,f,g,4,

31、6,8,2,3,2,5,7,3,8,4,3,7,6,4,4(4),6(6),8(3),2(2),3(3),2(2),5(5),7(6),3(0),8(4),4(3),3(3),7(3),6(6),4(4),（1）確定初始可行流,（2）標號法求最大流得最小截,答案：最小截為Aa、Ab、cb，即在這三個路段修建檢查站，最小費用為13,案例：垃圾處理問題 某地區(qū)有3個城鎮(zhèn)，各城鎮(zhèn)每天產生的垃圾要運往該地區(qū)的4個垃圾處理場處理，現考慮各城鎮(zhèn)到各處理場的道路對各城鎮(zhèn)垃圾外運的影響。假設各城鎮(zhèn)每日產生的垃圾量、各處理場的日處理能力及各條道路（可供運垃圾部分）的容量（其中容量為0表示無此直接道路）如右表所示

32、，試用網絡流方法分析目前的道路狀況能否使所有垃圾都運到處理場得到處理，如果不能，應首先拓寬哪條道路。,分析：轉化為一個網絡圖，弧的容量為各路段能處 理垃圾的數量。,a,b,c,1,2,3,4,s,t,80,50,40,20,50,60,40,90,30,20,70,30,50,10,20,40,則問題為求最小截。,b,80(80),50(30),40(20),20(0),50(30),60(60),40(40),90(20),30(30),20(20),70(20),30(30),50(50),10(0),20(20),40(0),80,50,40,20,50,60,40,90,20,70,3

33、0,50,10,20,40,s,（1）確定初始可行流,30,（2）標號法求最大流得最小截,4,c,3,2,1,a,t,b,80(80),50(30),40(20),20(0),50(30),60(60),40(40),90(20),30(30),20(20),70(20),30(30),50(50),10(0),20(20),40(0),s,（3）反向追蹤，找可擴充鏈,4,c,3,2,1,a,t,90(40),20(20),50(10),40(20),70(40),得一s-t的可擴充鏈:,s-b-4-c-3-t，調整量,b,90(40),50(10),40(20),70(40),80(80),

34、50(30),40(20),20(20),60(60),40(40),30(30),20(20),30(30),50(50),10(0),20(20),（4）重復標號,3,2,1,a,t,s,4,c,a,2,1,a,3,（5）反向追蹤，找可擴充鏈,（6）找到可擴充流S-b-4-c-3-t,調整量為10,b,80(80),50(40),40(20),20(20),60(60),40(40),30(30),20(20),30(20),50(50),10(10),20(20),3,2,1,a,t,s,4,c,a,2,1,a,3,（6）找到可擴充流S-b-4-c-3-t,調整量為10,90(50),5

35、0(0),40(30),70(50),90(50),20(20),50(0),40(30),70(50),80(80),50(40),40(20),60(60),40(40),30(30),20(20),30(20),50(50),10(10),20(20),（4）重復標號，直至終止,3,2,1,a,t,c,3,2,1,a,t,s,b,4,答案：最小截為sa、sc、b3 、4t ,垃圾最大處理量為180 50+70+80,答案,綜上，目前的道路狀況不能使所有垃圾都運到處理場得到處理。 從圖上不難發(fā)現，理論上應當拓寬割集所在的道路。但由于sa,sc和4t都是添加的虛擬道路，所以只有拓寬割集中的b

36、3道路的路寬，或者增大4號處理場處理垃圾的能力，才能解決問題。,練習：過紐約ALBANY的北-南高速公路，路況通過能力如下圖所示，圖中弧上數字單位：千輛/小時。求（1）該路網能承受的北-南向最大流量；（2）若要擴充通過能力，應在那一組路段上擴充，說明原因。,(1)選取一個可行流,1,2,3,5,4,6,（,進入Albany(北),離開Albany(南),2(2),4(1),3(0),1(1),6(5),3(3),2(2),3(3),6(2),1(1),V1V4V2V5V6，可擴充量為1，調整成新流，繼續(xù)標號,用標號法得可擴充鏈,1,2,3,5,4,6,（,進入Albany(北),離開Alban

37、y(南),2(2),4(2),3(1),1(1),6(5),3(3),2(2),3(3),6(3),1(0),標號終止，當前流為最大流，最大流量為8 割集為：12, 45， 46，36 應該在割集弧上擴大流量,練習1,0, v1,4, v1,3, v1,5, v2,6, v2,9, v7,7, v4/ v6,8.5, v6,6, v2,有9個城市v1、 v2、v9，其公路網如圖所示。弧旁數字是該段公路的長度，有一批物資要從v1 運到v9 ，問走哪條路最近？,習題課練習（最小支撐樹）,已知有A、B、C、D、E、F六個城鎮(zhèn)間的道路網絡 如圖，現要在六個城鎮(zhèn)間架設通訊網絡（均沿道路架設），每段道路上的架設費用如圖。求能保證各城鎮(zhèn)均能通話且總架設費用最少的架設方案。,練習2,第四節(jié) 最小費用最大流問題,在實際的網絡系統(tǒng)中，當涉及到有關流的問題的時候，我們往往不僅僅考慮的是流量，