第5章圖論與網(wǎng)絡分析,圖的基本概念,網(wǎng)絡分析,最小支撐樹問題最短路徑問題網(wǎng)絡最大流問題,圖論起源：哥尼斯堡七橋問題,問題：一個散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點？,結論：每個結點關聯(lián)的邊數(shù)均為偶數(shù),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、鏈與路、圈與回路,鏈,點邊交錯的序列,路,點弧交錯的序列,回路,起點=終點的路,無向圖：,有向圖：,鏈與路中的點均不相同，則稱為初等鏈(路)類似可定義初等圈（回路）,4、連通圖,G1為不連通圖，G2為連通圖,例：,5、支撐子圖,圖G=(V，E)和G=(V，E)，若V=V且EE，則稱G為G的支撐子圖。,G2為G1的支撐子圖,例：,G2是G1的子圖；,例：,6、賦權圖（網(wǎng)絡）,圖的每條邊都有一個表示一定實際含義的權數(shù)，稱為賦權圖。記作D=(V，A，C)。,例：,2最小支撐樹問題,本節(jié)主要內(nèi)容：,樹,支撐樹,最小支撐樹,樹：無圈的連通圖，記為T。,一、樹的概念與性質(zhì),樹的性質(zhì)：（1）樹的任2點間有且僅有1鏈；（2）在樹中任去掉1邊，則不連通；故樹是使圖保持連通且具有最少邊數(shù)的一種圖形（3）在樹中不相鄰2點間添1邊，恰成1圈；（4）若樹T有m個頂點，則T有m-1條邊。,若一個圖G=（V,E）的支撐子圖T=（V,E）構成樹，則稱T為G的支撐樹，又稱生成樹。,二、圖的支撐樹,例,例某地新建5處居民點，擬修道路連接5處，經(jīng)勘測其道路可鋪成如圖所示。為使5處居民點都有道路相連，問至少要鋪幾條路？,解：,該問題實為求圖的支撐樹問題，共需鋪4條路。,圖的支撐樹的應用舉例,用破圈法求出下圖的一個生成樹。,最小支撐樹：求網(wǎng)絡的支撐樹，使其權和最小。,三、最小支撐樹問題,算法1（破圈法）：在給定的賦權的連通圖上找一個圈；在所找的圈中去掉一條權數(shù)最大的邊(若有兩條或兩條以上的邊都是權數(shù)最大的邊，則任意去掉其中一條)：若所余下的圖已不含圈，則計算結束，所余下的圖即為最小支撐樹，否則，返問。,例求上例中的最小支撐樹,解：,5,5.5,v1,v2,v3,v4,v5,3.5,7.5,4,2,3,4,算法2（避圈法）：從某一點開始，把邊按權從小到大依次添入圖中，若出現(xiàn)圈，則刪去其中最大邊，直至填滿n-1條邊為止（n為結點數(shù)）。,最小生成樹舉例：某六個城市之間的道路網(wǎng)如圖所示，要求沿著已知長度的道路聯(lián)結六個城市的電話線網(wǎng)，使電話線的總長度最短。,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,聯(lián)系今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,練習今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,例今有煤氣站A，將給一居民區(qū)供應煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設各用戶點的煤氣管道所需的費用（單位：萬元）如圖邊上的數(shù)字所示。要求設計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。,此即為最經(jīng)濟的煤氣管道路線，所需的總費用為25萬元,3最短路徑問題,最短路問題是在一個網(wǎng)絡（賦權有向圖）中尋找從起點到某個節(jié)點之間一條最短的路線?，F(xiàn)欲求出1至6距離最短的路徑。,基本思想：從起點vs開始，逐步給每個結點vj標號dj,vi，其中dj為起點vs到vj的最短距離，vi為該最短路線上的前一節(jié)點.若給終點vt標上號dt,vi,表示已求出v1至vt的最短路其最短路長為dt，最短路徑可根據(jù)標號vi反向追蹤而得,最短路問題的Dijstra解法（狄克拉斯）,0,v1,1,v1,(3)考慮所有這樣的邊vi,vj，其中viVA，vjVB，挑選其中與起點v1距離最短（mindi+cij）的vj，對vj進行標號,(4)重復(2)、(3)，直至終點vn標上號dn,vi，則dn即為v1vn的最短距離，反向追蹤可求出最短路。,(1)給起點v1標號0,v1,0,v1,1,v1,(3)考慮所有這樣的邊vi,vj，其中viVA，vjVB，挑選其中與起點v1距離最短（mindi+cij）的vj，對vj進行標號,(4)重復(2)、(3)，直至終點vn標上號dn,vi，則dn即為v1vn的最短距離，反向追蹤可求出最短路。,(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即為v1vn的最短距離，反向追蹤可求出最短路,0,v1,1,v1,3,v1,5,v3,6,v2,9,v5,10,v5,12,v5,v1到v9的最短路為：v1v3v2v5v9，最短距離為12,p119,練習：用Dijkstra算法求下圖中V1至V8的最短路及最短路長。,關鍵線路：1.V1-V2-V4-V6-V82.V1-V2-V4V7-V8最短路長：12,課堂練習無向圖情形,求網(wǎng)絡中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,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,最短路模型的應用設備更新問題,例某工廠使用一種設備，這種設備在一定的年限內(nèi)隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設備是否更新。若購置設備，每年需支付購置費用；若繼續(xù)使用舊設備，需要支付維修與運行費用。計劃期（五年）內(nèi)中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內(nèi)的總費用最小。,最短路模型的應用設備更新問題,分析：,結點：V=v1，v6，vi表示第i年初；,?。篈=(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，即第一年購買設備，用到第三年更新，再用至第五年年末最優(yōu)費用為53,計劃期（五年）內(nèi)中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內(nèi)的總費用最小。,練習：設備更新問題,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的所有路中的最短路。設P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程：,(二)Ford法(逐次逼近法)（權有負數(shù)）,開始時，令即用v1到vj的直接距離做初始解。,從第二步起，使用遞推公式：,求，當進行到第t步，若出現(xiàn),即為v1到各點的最短路長。,則停止計算，,例:,從第二步起，使用遞推公式,從第二步起，使用遞推公式,為了求出從v1到各個點的最短路，一般采用反向追蹤的方法：如果已知d(vs,vj),那么尋求一個點vk,使得d(vs,vk)+wkj=d(vs,vj),然后記錄下(vk,vj)；在看d(vs,vk),尋求一個點vi,使得d(vs,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網(wǎng)絡最大流問題,引例：下圖為V1到V6的一交通網(wǎng)，權表示相應運輸線的最大通過能力，制定一方案，使從V1到V6的運輸產(chǎn)品數(shù)量最多。,已知網(wǎng)絡D=（V，A，C），其中V為頂點集，A為弧集，C=cij為容量集，cij為弧（vi，vj）上的容量?，F(xiàn)D上要通過一個流f=fij，其中fij為?。╲i，vj）上的流量。問題：應如何安排流量fij可使D上通過的總流量v最大？,一、一般提法,二、最大流問題的數(shù)學模型,maxv=v（f）,容量約束,平衡約束,P125,滿足上述所有約束條件的流成為可行流。,（1）容量條件：對于每一個弧（vi,vj）A，有0fijcij。（2）平衡條件：對于發(fā)點vs，有對于收點vt，有對于中間點，有為可行流f的流量(發(fā)點的凈輸出量或收點的凈輸入量),1、稱滿足下列條件的流f為可行流：,三、基本概念和定理,可行流特征：（1）容量條件：每一個弧上的流量不能超過該弧的容量。（2）每一個中間點的流入量與流出量的代數(shù)和為零。（轉運的作用）（3）出發(fā)點的總流出量與收點的總流入量必相等。,任意一個網(wǎng)絡上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。網(wǎng)絡系統(tǒng)中最大流問題就是在給定的網(wǎng)絡上尋求一個可行流f,其流量v(f)達到最大值。,可行流中fijcij的弧叫做飽和??；fijcij的弧叫做非飽和??；fij0的弧叫做非零流??；fij0的弧叫做零流弧。,2、飽和弧與零流弧,f為一可行流，u為vs至vt的鏈，令u+=正向弧，u-=反向弧。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關于f的一條增廣鏈。,3、增廣鏈,增廣鏈,顯然圖中增廣鏈不止一條,增廣鏈,容量網(wǎng)絡D=（V，A，C），vs為始點，vt為終點。如果把V分成兩個非空集合使則所有始點屬于V1，而終點屬于的弧的集合，稱為分離vs和vt的截集。,4、截集和截集的截量,截集是連接起點和終點的必經(jīng)之路。,截集中所有弧的容量之和，稱為這個截集的截量，記為,則截集為,設,容量為24,設,則截集為,容量為20,流量與截量的關系：,任一可行流的流量都不會超過任一截集的截量,v1,vs,v2,v3,vt,（2，2）,（4，3）,（3，1）,（1，0）,（3，3）,（5，2）,（2，2）,最大流最小截定理：任一網(wǎng)絡D中，從vs至vt的最大流的流量等于分離vs、vt的最小截集的容量。,例.如圖所示的網(wǎng)絡中，弧旁數(shù)字為(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）,（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)，截量為：6V1=vs,v1，截集為(vs,v2),(v1,vt)，截量為：7V1=vs,v2，截集為，截量為：7,V1=vs，截集為(vs,v1),(vs,v2)，截量為：6V1=vs,v1，截集為(vs,v2),(v1,vt)，截量為：7V1=vs,v2，截集為，截量為：7V1=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)，截量為：6V1=vs,v1，截集為(vs,v2),(v1,vt)，截量為：7V1=vs,v2，截集為，截量為：7V1=vs,v3，截集為，截量為：12V1=vs,v1,v2，截集為，截量為：5,（2）最小截量minC(V1,V2)=5；（3）v(f*)=5=minC(V1,V2)f*是最大流。,最大流判定定理：可行流f*是最大流的充分必要條件是當且僅當不存在從vs到vt的關于f*的增廣鏈。,p124,尋求網(wǎng)絡最大流問題的主要步驟：（1）確定初始可行流（觀察法和零流法）（2）檢驗當前可行流是否是網(wǎng)絡中的最大流(對已知可行流用標號法尋找可擴充鏈，若存在，則當前可行流不是最大流，轉(3)；若不存在，則是最大流）（3）將當前的可行流調(diào)整成一個流量更大的新可行流再由(2)檢驗,四、求最大流方法標號法,思路：從始點開始標號，尋找是否存在增廣鏈。給vj標號為j,vi，其中j為調(diào)整量，vi為前一節(jié)點。,標號具體步驟：,（b）標號終止，說明不存在可擴充鏈，當前即為流為最大流，并得最小截集,（a）說明存在可擴充鏈,反向追蹤找出,轉(4),例5用標號法求下面網(wǎng)絡的最大流。,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,步驟：(1)給vs標號為,vs，選與vs關聯(lián)的流出未飽和弧(vs,vj),給vj標號j,vs,其中j=csj-fsj,例5用標號法求下面網(wǎng)絡的最大流。,（2,2）,（1,1）,（3,3）,（1,1）,（4,3）,（5,1）,（3,0）,（2,1）,（5,3）,例5用標號法求下面網(wǎng)絡的最大流。,（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用標號法求下面網(wǎng)絡的最大流。,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用標號法求下面網(wǎng)絡的最大流。,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用標號法求下面網(wǎng)絡的最大流。,vt已標號，得到一條增廣鏈u(反向追蹤)，轉（5）；vt未標號，且無法再標號,此時的流為最大流,此時的截集為最小截。,（4）重復（2）,（3），依次進行的結局可能為：,例5用標號法求下面網(wǎng)絡的最大流。,(5)調(diào)整。取=t，令,，得新流fij轉(1)。,（2,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兆瓦，經(jīng)輸電網(wǎng)可把電力送到8號地區(qū)，電網(wǎng)能力如圖所示。求三個發(fā)電站輸?shù)皆摰貐^(qū)的最大電力。,v0,（1）由于網(wǎng)絡圖中只有一個發(fā)點和一個收點，所以有必要添加一個虛設的起點和弧弧上各容量為，分別為三點的發(fā)電能力，如圖所示：,v0,10,10,15,15,15,0,10,10,10,10,15,25,(2)由觀察法得一初始可行流即圖上所標。為弧上容量，為弧上流量。,(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),(15,15),(10,0),(20,10),v0,(10,10),(15,15),(40,10),v0,|,|,v6,|,v5,v4,|,v2,v1,v7,v8,(4)調(diào)整流量。由可擴充鏈確定一新可行流，可擴充鏈上前向弧上流量均增加,(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,|,|,v6,|,v5,v4,v2,v1,v7,v8,|,標號完畢，且終點未標號。這說明網(wǎng)絡中已找不到可擴充鏈，當前即為最大流，最大流流量為：20+15+1045即三個發(fā)電站輸送到8號地區(qū)的最大電力為45兆瓦。,練習：圖中A、B、C、D、E、F分別表示陸地和島嶼，表示橋梁及其編號。河兩岸分別互為敵對的雙方部隊占領，問至少應切斷幾座橋梁（具體指出編號）才能達到阻止對方部隊過河的目的。試用圖論方法進行分析。,分析：轉化為一個網(wǎng)絡圖，弧的容量為兩點間的橋梁數(shù)。,則問題為求最小截。,步驟（1）確定初始可行流,1(1),1(0),分析：轉化為一個網(wǎng)絡圖，弧的容量為兩點間的橋梁數(shù)。,則問題為求最小截。,答案：最小截為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城，可能的旅行路線如圖：,邊防隊擬建立足夠數(shù)量檢查站以便使每輛汽車至少必經(jīng)過一個檢查站，建立檢查站的費用根據(jù)各路段條件有所不同（如圖數(shù)字所示），求最小費用解。,（分析：最小截問題）,分析：轉化為一個網(wǎng)絡圖，弧的容量為各路段得費用。則問題為求最小截。步驟,a,B,A,b,c,d,e,f,g,4,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)每天產(chǎn)生的垃圾要運往該地區(qū)的4個垃圾處理場處理，現(xiàn)考慮各城鎮(zhèn)到各處理場的道路對各城鎮(zhèn)垃圾外運的影響。假設各城鎮(zhèn)每日產(chǎn)生的垃圾量、各處理場的日處理能力及各條道路（可供運垃圾部分）的容量（其中容量為0表示無此直接道路）如右表所示，試用網(wǎng)絡流方法分析目前的道路狀況能否使所有垃圾都運到處理場得到處理，如果不能，應首先拓寬哪條道路。,分析：轉化為一個網(wǎng)絡圖，弧的容量為各路段能處理垃圾的數(shù)量。,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,30,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，調(diào)整量,b,90(40),50(10),40(20),70(40),80(80),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,調(diào)整量為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,調(diào)整量為10,90(50),50(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ā)現(xiàn)，理論上應當拓寬割集所在的道路。但由于sa,sc和4t都是添加的虛擬道路，所以只有拓寬割集中的b3道路的路寬，或者增大4號處理場處理垃圾的能力，才能解決問題。,練習：過紐約ALBANY的北-南高速公路，路況通過能力如下圖所示，圖中弧上數(shù)字單位：千輛/小時。求（1）該路網(wǎng)能承受的北-南向最大流量；（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，調(diào)整成新流，繼續(xù)標號,用標號法得可擴充鏈,1,2,3,5,4,6,（,進入Albany(北),離開Albany(南),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，其公路網(wǎng)如圖所示。弧旁數(shù)字是該段公路的長度，有一批物資要從v1運到v9，問走哪條路最近？,習題課練習（最小支撐樹）,已知有A、B、C、D、E、F六個城鎮(zhèn)間的道路網(wǎng)絡如圖，現(xiàn)要在六個城鎮(zhèn)間架設通訊網(wǎng)絡（均沿道路架設），每段道路上的架設費用如圖。求能保證各城鎮(zhèn)均能通話且總架設費用最少的架設方案。,練習2,第四節(jié)最小費用最大流問題,在實際的網(wǎng)絡系統(tǒng)中，當涉及到有關流的問題的時候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費用的問題。比如一個鐵路系統(tǒng)的運輸網(wǎng)絡流，即要考慮網(wǎng)絡流的貨運量最大，又要考慮總費用最小。最小費用最大流問題就是要解決這一類問題。,設一個網(wǎng)絡D=（V，A，C），對于每一個弧(vi,vj)A,給定一個單位流量的費用bij0，網(wǎng)絡系統(tǒng)的最小費用最大流問題，是指要尋求一個最大流f，并且流的總費用達到最小。,而此時總費用b(f)比b(f)增加了,我們將叫做這條增廣鏈的費用。,我們首先考察，在一個網(wǎng)絡D中，當沿可行流f的一條增廣鏈，以調(diào)整量=1改進f，得到的新可行流f的流量，有v(f)=v(f)+1,顯然，零流f=0是流量為0的最小費用流。一般地，尋求最小費用流，總可以從零流f=0開始。問題是：如果已知f是流量為v(f)的最小費用流，如何尋找關于f的最小費用增廣鏈？,結論：若f是流量為v(f)的所有可行流中的費用最小，而是關于f的所有增廣鏈中的費用最小的增廣鏈，則f沿增廣鏈調(diào)整量為1得到的新可行流f，一定是流量為v(f)+1的所有可行流中的最小費用流。依次類推，當f是最大流時，就是所要求的最小費用最大流。,若u是從vs到vt關于f的增廣鏈，它的費用,若果把u-中的邊(vi,vj)反向，并且令它的權是-bij，而u+中的方向不變，并且的它的權是bij，這樣就把求從vs到vt關于f的最小費用增廣鏈就轉換成尋求從vs到vt的最短路。,構造一個賦權有向圖M(f)，其頂點是原網(wǎng)絡D的頂點，他的邊根據(jù)f的情況確定：,若原圖中（vi，vj）邊中fij=0，則M(f)中連接（vi，vj）,并令其權L(vi,vj)=bij；若原圖中（vi，vj）邊中fij=cij，則M(f)中連接（vi，vj）,并令其權L(vi,vj)=-bij；若原圖中（vi，vj）邊中fij=0，則M(f)中連接（vi，vj）和(vj,vi),并令其權L(vi,vj)=bij,L(vi,vj)=-bij；,步驟：（1）取零流為初始可行流，f(0)=0。（2）一般地，如果在第k-1步得到最小費用流f(k-1)，則構造圖L(f(k-1)。（3）在L(f(k-1)中，尋求從vs到vt的最短路。若不存在最短路，則f(k-1)就是最小費用最大流；否則轉(4)。（4）如果存在最短路，則在可行流f(k1)的圖中得到與此最短路相對應的增廣鏈，在增廣鏈上，對f(k1)進行調(diào)整，調(diào)整量為：,得到新可行流f(k)。對f(k)重復上面步驟，返回（2）。,例求圖8-24所示網(wǎng)絡中的最小費用最大流，弧旁的權是（bij,cij）.,圖8-24,4,由于在M(f(4)中已經(jīng)不存在從vs到vt的最短路，因此，可行流f(4)，v(f(4)=11是最小費用最大流。,例8.11求網(wǎng)絡的最小費用最大流，弧旁權是（bij,cij）,