運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析.ppt

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