運籌學(xué) 圖與網(wǎng)絡(luò)分析

圖與網(wǎng)絡(luò)模型Graph Theory引言 十八世紀(jì)的哥尼斯堡城中流過一條河（普雷.格爾河），河上有 7 座橋連接著河的兩岸和河中的兩個小島。當(dāng)時那里的人們熱衷于這樣一個游戲：一個游者怎樣才能一次連續(xù)走過這 7 座橋，回到原出發(fā)點，而每座橋只允許走一次。沒有人想出走法，又無法說明走法不存在，這就是著名的“哥尼斯堡 7 橋”難題。ABCD第1頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory引言 “哥尼斯堡 7 橋”難題最終在 1736 年由數(shù)學(xué)家 Euler 的一篇論文給予了完滿的解決，這是圖論的第一篇論文。在后來的兩百年間圖論的發(fā)展是緩慢的，直到 1936 年匈牙利數(shù)學(xué)家 O.Knig寫出了圖論的第一本專著有限圖與無限圖的理論。在圖論的發(fā)展過程中還有兩位著名科學(xué)家值得一提，他們是克?；舴蚝蛣P萊?？讼；舴蛟谘芯侩娋W(wǎng)絡(luò)時對圖的獨立回路理論作出了重要的貢獻，而化學(xué)家凱萊在對碳?xì)浠衔锏耐之悩?gòu)體的數(shù)量進行計數(shù)時推動了圖論中樹的計數(shù)問題的研究。圖論的歷史上最具有傳奇色彩的問題也許要數(shù)著名的“四色猜想”了歷史上許許多多數(shù)學(xué)猜想之一。它描述對一張地圖著色的問題，曾經(jīng)有一位數(shù)學(xué)家這樣說：“對于這個問題，一位數(shù)學(xué)家可以用不到五分鐘的時間向馬路上任何一位行人講述清楚它，然后，兩人都明白這一問題，但是，兩人都無能為力。”幸運的是在 1970s 終于由美國的兩位數(shù)學(xué)家借助大型計算機將其證明了。第2頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 圖論與網(wǎng)絡(luò)分析理論所研究的問題十分廣泛，內(nèi)容極其豐富。正如一位數(shù)學(xué)家所說：“可以說，圖論為任何一個包含了某種二元關(guān)系的系統(tǒng)提供了一種分析和描述的模型?！毕旅嫖覀儊砜匆粋€案例 國慶大假期間旅游非?；鸨?，機票早已訂購一空。成都一家旅行社由于信譽好、服務(wù)好，所策劃的國慶首都游的行情看好，要求參加的游客眾多，游客甚至不惜多花機票錢暫轉(zhuǎn)取道它地也愿參加此游。旅行社只好緊急電傳他在全國各地的辦事處要求協(xié)助解決此問題。很快，各辦事處將其已訂購機票的情況傳到了總社。根據(jù)此資料，總社要作出計劃，最多能將多少游客從成都送往北京以及如何取道轉(zhuǎn)機。下面是各辦事處已訂購機票的詳細(xì)情況表：第3頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 各辦事處已訂購機票情況表成都成都重慶重慶武漢武漢上海上海西安西安鄭州鄭州沈陽沈陽昆明昆明廣州廣州北京北京成都成都 重慶重慶 武漢武漢 上海上海 西安西安 鄭州鄭州 沈陽沈陽 昆明昆明 廣州廣州 北京北京10 5 15 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10 8 2 6 10 第4頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 將此問題通過圖的模型描述：下圖中，點各城市，帶箭頭連線從箭尾城市到箭頭城市已訂購有機票，帶箭頭連線旁的數(shù)字機票數(shù)量。成重武昆上廣西鄭沈京8鄭州辦事處已訂有的到北京的機票數(shù)量。第5頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 一、圖及其分類和術(shù)語 1、圖論中所研究的圖并非幾何學(xué)中的圖，也不是繪畫中的圖。在這里我們所關(guān)心的僅僅是圖中有多少個點，點與點之間有無線來連接，也就是說我們研究的是某個系統(tǒng)中的元素點，以及這些元素之間的某種關(guān)系連線。定義：圖一個圖G是一個有序二元組（V，E），記為G=（V，E）其中（1）V是一個有限非空的集合，其元素稱為G的點或頂點，而稱V為G的點集 V=v1，v2，vn；（2）E是V中元素的無序?qū)?vi，vj)所構(gòu)成的一個集合，其元素稱為G的邊，一般表示為 e=(vi，vj)，而稱E是G的邊集。邊（無向邊）沒有方向的連線 ?。ㄓ邢蜻叄в蟹较虻倪B線 無向圖 有向圖 簡單圖 多重圖 完全圖 二部圖（偶圖，雙圖）第6頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 子圖 真子圖 生成子圖 點生成子圖 邊生成子圖 點的次 奇次點 偶次點 鏈 圈 路 回路 賦權(quán)圖 2、連通圖 在眾多各類圖中有一類在實際應(yīng)用中占有重要地位的圖 連通圖在圖中，任意兩點間至少存在著一條鏈連通圖連通圖不連通圖不連通圖第7頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 3、圖與矩陣 在圖與網(wǎng)絡(luò)分析的應(yīng)用中，將面臨一個問題如何分析、計算一個較大型的網(wǎng)絡(luò)，這當(dāng)然需借助快速的計算工具計算機。那么，如何將一個圖表示在計算機中，或者，如何在計算機中存儲一個圖呢？現(xiàn)在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。鄰接矩陣對于圖G=（V，E），|V|=n，|E|=m，有n n階方矩陣A=（aij）n n，其中 aij=k 當(dāng)且僅當(dāng)vi與vj之間有條邊時 0 其它第8頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 鄰接矩陣A=（aij）n n=0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 2 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 10 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 2 0 1 0 0 0 v1v2v3v4v5v6v7v8v1 v2 v3 v4 v5 v6 v7 v8 v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8第9頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory圖與網(wǎng)絡(luò)的基本概念 關(guān)聯(lián)矩陣對于圖G=（V，E），|V|=n，|E|=m，有m n階矩陣M=（mij）m n，其中 mij =2 當(dāng)且僅當(dāng) vi是邊ej 的兩個端點 1 當(dāng)且僅當(dāng) vi是邊ej 的一個端點 例 0 其它v1v2v3v5v4v8v6v7e1e2e3e4e6e5e7e9e12e10e11e8M=（mij）=1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 第10頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最小樹問題 二、樹（Tree）和最小樹 樹是圖論中一類重要的圖，實際中有很多系統(tǒng)的結(jié)構(gòu)都是樹。樹連通且不含圈的圖，簡記為 T。下面的說法是等價的：T是一個樹。T無圈，且 m=n-1。T連通，且 m=n-1。T無圈，但每加一條新的邊即出現(xiàn)唯一一個圈。T連通，但每舍去一條邊就不連通。T中任意兩點，有唯一的一條鏈相連。T是邊數(shù)最少的連通圖。圖的生成樹若G圖的一個點生成子圖是一個樹，則稱此樹是G圖的一個生成樹。樹的權(quán)若Tk是加權(quán)圖G的一棵樹，則樹T的全部邊的權(quán)之和稱為樹Tk的權(quán)，記為 （Tk）=（e）；e Tk 最小樹T*是加權(quán)圖G的一棵最小樹，即（T*）=min (Tk)k第11頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最小樹問題 破圈法，避圈法求生成樹：圖圖G生成樹生成樹T生成樹生成樹T第12頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最小樹問題 破圈法，避圈法求最小生成樹：圖圖G生成樹生成樹T生成樹生成樹T15424531344215121231211212312112第13頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最短路問題 三、路（Path）和最短路 最短路問題是網(wǎng)絡(luò)分析中應(yīng)用最廣泛的問題之一。盡管前面介紹了用動態(tài)規(guī)劃方法求解，但有時卻較困難，此時圖論的方法卻十分有效。最短路問題的一般描述：G=（V，E）是連通圖，圖中各邊（vi，vj）有權(quán)l(xiāng)ij（=表示vi，vj間無邊），vs、vt為圖中任意兩指定點，求一條路，使其是從 vs到 vt的所有路中最短（路中各邊的權(quán)之和最?。┑囊粭l路。即L（）=min lij（vi，vj）第14頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最短路問題 E.W.Dijkstra 算法（標(biāo)號算法）算法基本思路分析：（逐步向外搜索）52165828997221210X（P標(biāo)號）Y（T標(biāo)號）起點到該點的最短距離起點到該點的最短距離的上界2527 5111212105756 679 910106 3 3第15頁/共59頁人、狼、羊、草渡河游戲 一個人帶著一條狼、一只羊、一筐白菜過河蛤由于船太小，人一次只能帶一樣?xùn)|西乘船過河。狼和羊、羊和白菜不能單獨留在同岸，否則羊或白菜會被吃掉。人 M（Man），狼 W（Wolf），羊 G（Goat），草 H（Hay）。點 vi 表示河岸的狀態(tài)，邊 ek 表示由狀態(tài) vi 經(jīng)一次渡河到狀態(tài) vj，權(quán)邊 ek 上的權(quán)定為 1。我們可以得到下面的加權(quán)有向圖：第16頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最短路問題 v1，u1 =（M，W，G，H）；v2，u2=（M，W，G）；v3，u3 =（M，W，H）；v4，u4 =（M，G，H）；v5，u5 =（M，G）。此游戲轉(zhuǎn)化為在下面的二部圖中求從 v1 到 u1 的最短路問題。v1v2v3v4v5u5u4u3u2u1第17頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最短路問題 在 E.W.Dijkstra 算法中必須滿足一個條件 在圖 G 中所有邊的權(quán) lij 0。若在圖 G 中存在有負(fù)權(quán)邊（當(dāng)然，這種情形只針對有向圖而言）時必須對E.W.Dijkstra 算法加以修改 稱為修改的 E.W.Dijkstra 算法。第18頁/共59頁2、情況二：wij0設(shè)從V1到Vj(j=1,2,t)的最短路長為P1jV1到Vj無任何中間點 P1j（1）=wijV1到Vj中間最多經(jīng)過一個點 P1j（2）=min P1j（1）+wijV1到Vj中間最多經(jīng)過兩個點 P1j（3）=min P1j（2）+wij.V1到Vj中間最多經(jīng)過t-2個點 P1j（t-1）=min P1j（t-2）+wij終止原則：1）當(dāng)P1j（k）=P1j（k+1）可停止，最短路P1j*=P1j（k）2）當(dāng)P1j（t-1）=P1j（t-2）時，再多迭代一次P1j（t），若P1j（t）=P1j（t-1），則原問題無解，存在負(fù)回路。第19頁/共59頁 例：求下圖所示有向圖中從v1到各點的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第20頁/共59頁 wij d(t)(v1,vj)v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v80 25-30-2406400-3 0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-336910020-336910說明：表中空格處為說明：表中空格處為+。4第21頁/共59頁例例 設(shè)備更新問題設(shè)備更新問題制訂一設(shè)備更新問題，使得總費用最小制訂一設(shè)備更新問題，使得總費用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 購買費購買費 13 14 16 19 24 使用年數(shù)使用年數(shù) 0-1 1-2 2-3 3-4 4-5 維修費維修費 8 10 13 18 27 解解設(shè)以設(shè)以vi(i=1,2,3,4,5)表示表示“第第i年初購進一臺年初購進一臺新設(shè)備新設(shè)備”這種狀態(tài)，以這種狀態(tài)，以v6表示表示“第第5年末年末”這種狀態(tài)；這種狀態(tài)；以弧以弧(vi,vj)表示表示“第第i年初購置的一臺設(shè)備一直使用到年初購置的一臺設(shè)備一直使用到第第j年初年初”這一方案，以這一方案，以wij表示這一方案所需購置費表示這一方案所需購置費和維護費之和。和維護費之和。第22頁/共59頁v1v2v3v5v6v4214432228962316345244734273732(0，Vs)(0，V1)(31,V1)(44,V1)(62,V1)(78,V3)第23頁/共59頁這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就可歸結(jié)為從圖中找出一條從可歸結(jié)為從圖中找出一條從v1到到v6的最短路問題。的最短路問題。用用Dijkstra標(biāo)號法，求得最短路為標(biāo)號法，求得最短路為 v1v3v6 即第一年初購置的設(shè)備使用到第三年初予以更新，即第一年初購置的設(shè)備使用到第三年初予以更新，然后一直使用到第五年末。這樣五年的總費用最然后一直使用到第五年末。這樣五年的總費用最少，為少，為78。第24頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法Dijkstra算法比較簡單，但是，對于含有負(fù)權(quán)弧的網(wǎng)絡(luò)可能失效。這時，應(yīng)對算法加以修改，即所謂“修改的 Dijkstra 算法”。下面，介紹一種算法距離矩陣摹乘法，它適用于任何網(wǎng)絡(luò)的最短路問題。例如v1v3v4v2v6v534233-24411-16333第25頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法1、網(wǎng)絡(luò)的距離矩陣設(shè)一網(wǎng)絡(luò)N中有n個點，其中任意兩點 vi 與 vj 之間都有一條邊(vi,vj)，其權(quán)數(shù)為 wij -。若 vi 與 vj 不相鄰，則虛設(shè)一條邊(vi,vj)，并令其權(quán)數(shù)wij=。距離矩陣 W=（wij）前例中的距離矩陣為W=v1 v2 v3 v4 v5 v6v1 0 3 2 4v2 0 4 4 1v3 0 -1 6 v4 3 -2 0 1 v5 5 0 3v6 3 3 0第26頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法2、求各點至某點的最短路求 vi（i=1,2,n）至某點 vr 的最短路。令：dir(k)=vi 走k步達到 vr 的最短距離，i=1,2,n則有 dir(1)=wir,i=1,2,ndir(k)=min wij+djr(k-1),i=1,2,n1jn令：令：dk =（d1r(k),d2r(k),dnr(k),）T ,k=1,2,第27頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory距離矩陣摹乘法矩陣摹乘運算法：dk=W dk-1 ,(k=2,3,)當(dāng) dk=dk-1,(k=2,3,)則計算停止，dk 中的元素即為各點到 vr 的最短距離。第28頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題一、基本概念 網(wǎng)絡(luò)最短距離矩陣 D=(dij)nn dij表示vi到vj的最短距離（1）網(wǎng)絡(luò)的中心令：令：d(vi)=max dij ,i=1,2,n若若 max d(vi)=d(vk)1in1jn則稱點則稱點 vk 為網(wǎng)絡(luò)的中心。為網(wǎng)絡(luò)的中心。第29頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題（2）網(wǎng)絡(luò)的重心 設(shè) gi 為點 vi 的權(quán)重（i=1,2,n），令：令：h(vj)=gidij ,j=1,2,ni=1n若若 max h(vj)=h(vr)1jn則稱點則稱點 vr 為網(wǎng)絡(luò)的重心。為網(wǎng)絡(luò)的重心。第30頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題二、應(yīng)用例 某地 7 個村鎮(zhèn)之間的現(xiàn)有交通道路如下圖，邊旁數(shù)值為各村鎮(zhèn)之間道路的長度，點旁數(shù)值為各村鎮(zhèn)的小學(xué)生人數(shù)?，F(xiàn)擬在某一村鎮(zhèn)建一商店和小學(xué)，試問：（1）商店應(yīng)該建在何村，能使各村都離它較近？（2）小學(xué)應(yīng)該建在何村，能使各村小學(xué)生總的行走路程最短？第31頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題v1v3v4v5v6v7v2746435712324230404535252050距離人數(shù)第32頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題（1）中心問題 網(wǎng)絡(luò)最短距離矩陣如下：vj viD=(dij)d(vi)=max dij 123456710345781010230324577343055688452502355(min)57452013768563102871078532010j結(jié)論：結(jié)論：商店應(yīng)該建在商店應(yīng)該建在 v4 村。村。第33頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)中心和重心問題（2）重心問題 vj vi gidij123456710120160200280320400275075501001251753180135022522527036041506015006090150514080100400206062801752101053507075003504002501501000h(vj)13259201095870850(min)9251215結(jié)論：結(jié)論：小學(xué)應(yīng)該建在小學(xué)應(yīng)該建在 v5 村。村。第34頁/共59頁第四節(jié) 最大流問題 如下是一運輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問：該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432312234第35頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)流問題定義1：定一個有向圖D=(V,E),在V中有一個發(fā)點vs和一收點vt，其余的點為中間點。對于每一條弧(vi,vj),對應(yīng)有一個c(vi,vj)0,(cij)稱為弧的容量。這樣的有向圖稱為容量網(wǎng)絡(luò)。記為D=(V,E,C)。1、網(wǎng)絡(luò)流義在弧集合E上的一個函數(shù)f=f(vi,vj)，稱f(vi,vj)為弧(vi,vj)上的流量，簡記fij。2、可行流3、最大流4、增廣鏈5、最小截集第36頁/共59頁2、可行流與最大流、可行流與最大流定義定義2 滿足下列條件的流稱為滿足下列條件的流稱為可行流可行流：1)0 fij cij2)平衡條件：平衡條件：中間點中間點 fij=fji(vi,vj)A(vj,vi)A發(fā)點發(fā)點vs fsj fjs=v(f)(vs,vj)A(vj,vs)A ftj fjt=v(f)(vt,vj)A收點vt，(vj,vt)A式中v(f)稱為這個可行流的流量，即發(fā)點的凈輸出量（或收點的凈輸入量）。第37頁/共59頁最大流問題：求一流最大流問題：求一流fij滿足滿足0 fij cij v(f)i=s fij fji=0 i s，t v(f)i=t且使且使v(f)達到最大。達到最大。第38頁/共59頁3、增廣鏈、增廣鏈 給定可行流給定可行流f=fij，使，使fij=cij的弧稱為的弧稱為飽和弧飽和弧，使使fij0的弧稱為的弧稱為非零流弧非零流弧。若若 是網(wǎng)絡(luò)中連接發(fā)點是網(wǎng)絡(luò)中連接發(fā)點vs和收點和收點vt的一條鏈，定的一條鏈，定義鏈的方向是從義鏈的方向是從vs到到vt，則鏈上的弧被分成兩類：，則鏈上的弧被分成兩類：前向弧：弧的方向與鏈的方向一致前向?。夯〉姆较蚺c鏈的方向一致 全體全體+后向?。夯〉姆较蚺c鏈的方向相反后向?。夯〉姆较蚺c鏈的方向相反 全體全體 定義3 設(shè)f是一可行流，是從vs到vt的一條鏈，若 滿足下列條件，則稱之為（關(guān)于流f的）一條增廣鏈：在弧(vi,vj)+上，0 fijcij 在弧(vi,vj)上，0fij cij第39頁/共59頁 4、截集與截量、截集與截量 定義定義4 給定網(wǎng)絡(luò)給定網(wǎng)絡(luò)D=(V,A,C)，若點集，若點集V被被剖分為兩個非空集合剖分為兩個非空集合V1和和V1，使，使vs V1，vt V1，則把弧集，則把弧集(V1,V1)稱為是（分離稱為是（分離vs和和vt的）的）截集。截集。截集是從截集是從vs到到vt的必經(jīng)之路。的必經(jīng)之路。定義定義5 給定一截集給定一截集(V1,V1)，把截集，把截集(V1,V1)中所有弧的容量之和稱為這個截集的容量中所有弧的容量之和稱為這個截集的容量(截量截量),記為記為C(V1,V1)。v(f)C(V1,V1)第40頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)流問題1、流量截量定理容量網(wǎng)絡(luò)上任何一個可行流的流量不超過任何一個截集的截量。2、增廣鏈調(diào)整定理在增廣鏈上對可行流進行調(diào)整可以得到一個流量更大的可行流。3、最大流定理可行流是最大流的充分必要條件是不存在關(guān)于該可行流的增廣鏈。第41頁/共59頁步驟步驟：2、標(biāo)號過程標(biāo)號過程1、選取一個可行流（可選擇零流?。?、選取一個可行流（可選擇零流?。膹腣s出發(fā)，出發(fā)，在在前向前向弧弧上上(vi,vj)，若，若fij0，則給，則給vj標(biāo)號標(biāo)號(Vi,l(vj)，其中其中l(wèi)(vj)=minl(vi)，fji。二、尋找最大流的標(biāo)號法二、尋找最大流的標(biāo)號法(Ford Fulkerson)思想：從一可行流出發(fā)，檢查關(guān)于此流是否思想：從一可行流出發(fā)，檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈，則增大流存在增廣鏈。若存在增廣鏈，則增大流量，使此量，使此鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，鏈變?yōu)榉窃鰪V鏈；這時再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。第42頁/共59頁 3、若標(biāo)號延續(xù)到、若標(biāo)號延續(xù)到vt，表明得到一條從，表明得到一條從vs到到vt的增的增廣鏈廣鏈，轉(zhuǎn)入調(diào)整階段，轉(zhuǎn)入調(diào)整階段4，否則當(dāng)前流即為最大流。，否則當(dāng)前流即為最大流。4、調(diào)整過程、調(diào)整過程令調(diào)整量為令調(diào)整量為=l(vt)令令 fij+(vi,vj)+fij=fij (vi,vj)fij (vi,vj)去掉所有的標(biāo)號，對新的可行流去掉所有的標(biāo)號，對新的可行流f=fij，重新進，重新進入標(biāo)號過程。入標(biāo)號過程。第43頁/共59頁可結(jié)合下圖理解其實際涵義。可結(jié)合下圖理解其實際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第44頁/共59頁vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例例 求下列網(wǎng)絡(luò)的最大流與最小截集。求下列網(wǎng)絡(luò)的最大流與最小截集。解解一、標(biāo)號過程一、標(biāo)號過程則則v1的標(biāo)號為的標(biāo)號為(vs,l(v1)，其中，其中第45頁/共59頁l(v1)=minl(vs)，cs1fs1=min+，9 2=2（3）檢查）檢查v1,在弧在弧(v1,v4)上上,f14=7,c14=9,f140，則則v3的標(biāo)號為的標(biāo)號為(-v4,l(v3)，其中，其中l(wèi)(v3)=minl(v4)，f34=min2，1=1（5）檢查）檢查v3,在弧在弧(v3,vt)上上,f3t=3,c3t=6,f3tc3t,第46頁/共59頁則則vt的標(biāo)號為的標(biāo)號為(v3,l(vt)，其中，其中l(wèi)(vt)=minl(v3)，c3tf3t=min1，6-3=1這樣，我們得到了一增廣鏈這樣，我們得到了一增廣鏈,如圖所示。如圖所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0,)(vs,2)(v1,2)(-v4,1)(v3,1)其中其中+=(vs,v1),(v1,v4),(v3,vt)，=(v3,v4)第47頁/共59頁二、調(diào)整過程二、調(diào)整過程取調(diào)整量為取調(diào)整量為=1，在，在 上調(diào)整上調(diào)整f。在在+上：上：fs1+=7+1=8 f14+=2+1=3 f4t+=5+1=6在在 上：上：f43=11=0s1vtvv3(9,8)(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7)第48頁/共59頁 在上圖中重復(fù)上述標(biāo)號過程，依次給在上圖中重復(fù)上述標(biāo)號過程，依次給vs,v2,v1,v4標(biāo)號標(biāo)號后，由于標(biāo)號無法繼續(xù)下去，算法結(jié)束。這時的流為最后，由于標(biāo)號無法繼續(xù)下去，算法結(jié)束。這時的流為最大流，最大流的流量為大流，最大流的流量為vvv(4,4)v(f)=8+3=11 與此同時，可找到最小截集與此同時，可找到最小截集(V1,V1)，其中，其中V1為標(biāo)號點集為標(biāo)號點集合，合，V1為未標(biāo)號點集合，弧集合為未標(biāo)號點集合，弧集合(V1,V1)即為最小截集。即為最小截集。此例中，此例中，V1=vs,v2,v1,v4,V1=v3,vt,(V1,V1)=(v1,v3)，(v4,vt)第49頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory網(wǎng)絡(luò)流問題容量網(wǎng)絡(luò) N 上最大流的標(biāo)號（Ford-Fulkerson）算法：下面，我們采用此算法來求解前面的旅行總社計劃問題案例第50頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最大流問題 各辦事處已訂購機票情況表成都成都vs重慶重慶v1武漢武漢v2上海上海v3西安西安v4鄭州鄭州v5沈陽沈陽v6昆明昆明v7廣州廣州v8北京北京vt成都成都 重慶重慶 武漢武漢 上海上海 西安西安 鄭州鄭州 沈陽沈陽 昆明昆明 廣州廣州 北京北京10 15 12 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10 8 2 6 10 第51頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最大流問題 發(fā)點vs=成都，收點vt=北京。前面已訂購機票情況表中的數(shù)字即是各邊上的容量（允許通過的最大旅客量），當(dāng)各邊上的實際客流量為零時略去不寫，以零流作為初始可行流。重武昆上廣西鄭沈京成0，+標(biāo)號，但未檢查標(biāo)號，但且已檢查 vs，300+30第52頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最大流問題重武昆上廣西鄭沈京成300，+vs，10vs，15vs，12vs，10vs，8vs，150，+v7，10v7，8vs，120+100+10第53頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最大流問題重武昆上廣西鄭沈京成301066122841221061010000010801801000，+vs，8vs，13v2，4vs，13-v2，4 v1，4-v2，40+44-42+4v1，4第54頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最大流問題重武昆上廣西鄭沈京成30106612280126106101000001080184100vs，8vs，9v2，40，+-v4，6vs，8 v1，6-v4，64+66-60+6vs，9第55頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最大流問題重武昆上廣西鄭沈京成301006122801261061010600010801810100vs，90，+vs，2v2，4vs，9v3，4v2，4v5，4-v5，2v3，4-v5，2v5，4vs，2第56頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最大流問題重武昆上廣西鄭沈京成301006122801261061010600010801810100v(f*)=10+6+12+30+12+10+6=86第57頁/共59頁圖與網(wǎng)絡(luò)模型Graph Theory最小費用大流問題五、最小費用大流問題 前面討論的旅行社的計劃問題中，旅行社解決了將盡可能多的游客（86人）送往了目的地北京，但旅行社計劃時沒有考慮機票的成本。現(xiàn)在旅行社考慮的問題是既要送出盡可能多的游客（86人），又要使機票的總成本最低，應(yīng)該如何制定新的計劃呢？這就是最小費用大流所研究解決的一類流量問題。最小費用大流問題還廣泛應(yīng)用于諸如最優(yōu)匹配，運輸問題等一類問題。應(yīng)該注意的是：最小費用大流問題首先要解決網(wǎng)絡(luò)上的最大流，目的是尋找使總費用達到最小的那個最大流。第58頁/共59頁感謝您的觀看！第59頁/共59頁