[互聯(lián)網(wǎng)]12997171025437500011-圖與網(wǎng)絡(luò)

1、chapter 11：圖與網(wǎng)絡(luò)模型圖與網(wǎng)絡(luò)模型l11.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念l11.2最短路問(wèn)題最短路問(wèn)題l11.3 最小生成樹(shù)問(wèn)題最小生成樹(shù)問(wèn)題l11.4 最大流問(wèn)題最大流問(wèn)題l11.5 最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題page 3圖論：圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系 圖g區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)、以及哪些點(diǎn)之間有連線。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示一般情況下，圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。(v1)趙趙

2、(v2)錢(qián)錢(qián)(v3)孫孫(v4)李李(v5)周周(v6)吳吳(v7)陳陳e2e1e3e4e5(v1)趙趙(v2)錢(qián)錢(qián)孫孫(v3) 李李(v4)周周(v5)吳吳(v6)陳陳(v7)e2e1e3e4e5page 4圖論：圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。圖論：圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。圖的定義：若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象

3、之間的聯(lián)系，則圖則圖g可以定義為可以定義為 “點(diǎn)點(diǎn)” 和和 “邊邊” 的集合，記作：的集合，記作：,evg 其中其中: v點(diǎn)集點(diǎn)集 e邊集邊集 圖圖g區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。及哪些點(diǎn)之間有連線。無(wú)向圖page 5定義定義: 圖中的點(diǎn)用圖中的點(diǎn)用v表示，邊用表示，邊用e表示。表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：，記作：e1=v1,v1; e2=v1,v2; v3e7e4e8e5e6e1e2e3v1v2v4v5l 端點(diǎn)，關(guān)聯(lián)邊，相鄰若有邊若有邊e可表示為可表示為 e=vi,vj，稱，稱vi和和vj是是 邊

4、邊 e 的的端點(diǎn)端點(diǎn)，反之稱，反之稱 邊邊e 為為 點(diǎn)點(diǎn)vi或或vj的的關(guān)聯(lián)邊關(guān)聯(lián)邊。若若 點(diǎn)點(diǎn)vi、vj 與同一條邊關(guān)聯(lián)，稱與同一條邊關(guān)聯(lián)，稱 點(diǎn)點(diǎn)vi和和vj 相鄰相鄰；若；若 邊邊ei和和ej 具有公共的端具有公共的端點(diǎn)，稱點(diǎn)，稱 邊邊ei和和ej 相鄰相鄰。page 6如果如果 邊邊e 的兩個(gè)端點(diǎn)相重，稱該邊的兩個(gè)端點(diǎn)相重，稱該邊為為 環(huán)環(huán)如右圖中邊如右圖中邊e1為環(huán)為環(huán)如果兩個(gè)點(diǎn)之間多于一條邊，稱為如果兩個(gè)點(diǎn)之間多于一條邊，稱為多重邊多重邊，如右圖中的，如右圖中的e4和和e5對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖簡(jiǎn)單圖v3e7e4e8e5e6e1e2e3v1v2v4v

5、5l 環(huán)，多重邊，簡(jiǎn)單圖page 7與某一個(gè)與某一個(gè) 點(diǎn)點(diǎn)vi 相關(guān)聯(lián)的相關(guān)聯(lián)的 邊的數(shù)目邊的數(shù)目 稱為稱為 點(diǎn)點(diǎn)vi的的次次（也叫做度），記作（也叫做度），記作d(vi)右圖中右圖中d(v1)4，d(v3)=5，d(v5)=1次為奇數(shù)的點(diǎn)稱作次為奇數(shù)的點(diǎn)稱作奇點(diǎn)奇點(diǎn)，次為偶數(shù)的，次為偶數(shù)的點(diǎn)稱作點(diǎn)稱作偶點(diǎn)偶點(diǎn)，次為，次為1的點(diǎn)稱為的點(diǎn)稱為懸掛點(diǎn)懸掛點(diǎn)，次為次為0的點(diǎn)稱作的點(diǎn)稱作孤立點(diǎn)孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次圖的次: 一個(gè)圖的次等于各點(diǎn)的次之和。一個(gè)圖的次等于各點(diǎn)的次之和。l 次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)page 8圖中某些點(diǎn)和邊的交替序列，若其圖中某些點(diǎn)和

6、邊的交替序列，若其中各邊互不相同，且對(duì)任意中各邊互不相同，且對(duì)任意vt-1和和vt均相鄰，稱為均相鄰，稱為鏈鏈。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起點(diǎn)與終點(diǎn)重合的鏈稱作起點(diǎn)與終點(diǎn)重合的鏈稱作圈（回路）圈（回路）如果任意兩個(gè)頂點(diǎn)之間至少存在一條如果任意兩個(gè)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為鏈，稱這樣的圖為連通圖連通圖l 鏈，圈（回路），連通圖 如果我們把上面例子中的如果我們把上面例子中的“相互認(rèn)識(shí)相互認(rèn)識(shí)”關(guān)系改為關(guān)系改為“認(rèn)識(shí)認(rèn)識(shí)” ” 的關(guān)系，那么只的關(guān)系，那么只用兩點(diǎn)之間的連線就很難用兩點(diǎn)之間的連線就很難刻畫(huà)他們之間的關(guān)系了，

7、刻畫(huà)他們之間的關(guān)系了，這時(shí)我們引入一個(gè)這時(shí)我們引入一個(gè)帶箭頭帶箭頭的連線的連線，稱為，稱為弧弧。相互認(rèn)。相互認(rèn)識(shí)用兩條反向的弧表示。識(shí)用兩條反向的弧表示。11.1 圖與網(wǎng)絡(luò)的基本概念有向圖的定義：圖圖d被定義為被定義為 “點(diǎn)點(diǎn)” 和和 “弧弧” 的集合，記作：的集合，記作：其中其中: v點(diǎn)集；點(diǎn)集； a弧集弧集a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙趙(v2)錢(qián)錢(qián)(v3)孫孫(v4)李李(v5)周周(v6)吳吳(v7)陳陳,avd page 10無(wú)向圖無(wú)向圖 g(v, e)，對(duì)，對(duì)g的每一條的每一條 邊邊(vi , vj) 相應(yīng)賦予數(shù)量指標(biāo)相應(yīng)賦予數(shù)量

8、指標(biāo)wij，稱稱wij為邊為邊(vi , vj)上的上的權(quán)權(quán)，稱圖，稱圖g為為賦權(quán)圖賦權(quán)圖賦權(quán)的有向圖賦權(quán)的有向圖 d = (v, a)，指定一點(diǎn)為，指定一點(diǎn)為 發(fā)點(diǎn)發(fā)點(diǎn)（vs），指定另一點(diǎn)為），指定另一點(diǎn)為 收點(diǎn)收點(diǎn)（vt），稱其它點(diǎn)為），稱其它點(diǎn)為中間點(diǎn)中間點(diǎn)，并把，并把 d 中每一條弧的中每一條弧的 賦權(quán)數(shù)賦權(quán)數(shù) cij 稱為弧稱為弧(vi,vj)的的容量容量，這樣的賦權(quán)有向圖，這樣的賦權(quán)有向圖d就稱為就稱為網(wǎng)絡(luò)網(wǎng)絡(luò)910201571419256l 賦權(quán)圖，網(wǎng)絡(luò)權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量) 等等page 11有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投有些問(wèn)題，如選址、管道

9、鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短路的問(wèn)題。因此這類(lèi)問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。路的問(wèn)題。因此這類(lèi)問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。最短路問(wèn)題對(duì)一個(gè)賦權(quán)的圖（對(duì)一個(gè)賦權(quán)的圖（g或或d）中的指定的兩個(gè)點(diǎn)）中的指定的兩個(gè)點(diǎn) vs 和和 vt 找到一條從找到一條從 vs 到到 vt 的路，使得這條路上所有的路，使得這條路上所有 ?。ㄟ叄┑臋?quán)數(shù)的總和最小，?。ㄟ叄┑臋?quán)數(shù)的總和最小，這條路被稱之為從這條路被稱之為從vs到到vt的最短路。的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從這條路上所有弧的權(quán)數(shù)的總和被稱為

10、從vs到到vt的距離。的距離。從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn) 或任意兩點(diǎn)之間距離最短的一條路 dijkstra 算法 (雙標(biāo)號(hào)法）(3,1)v23527531512 v1（0,s)v5(8,4)v6(2,1)v3(3,3)v41. 給出給出 點(diǎn)點(diǎn)vs 以標(biāo)號(hào)以標(biāo)號(hào) ( 0, s )2. 找出已標(biāo)號(hào)的點(diǎn)的集合找出已標(biāo)號(hào)的點(diǎn)的集合 i，沒(méi)標(biāo)號(hào)的點(diǎn)的集合，沒(méi)標(biāo)號(hào)的點(diǎn)的集合 j，以及，以及弧的集合弧的集合 3. 如果如果 b是空集，則計(jì)算結(jié)束。是空集，則計(jì)算結(jié)束。 如果如果vt已標(biāo)號(hào)已標(biāo)號(hào) ( lt, kt )，則，則 vs到到vt的距離為的距離為lt，而，而從從 vs到到vt的最短路徑，則可以從的最

11、短路徑，則可以從vt 反向追蹤到起點(diǎn)反向追蹤到起點(diǎn)vs （根據(jù)（根據(jù) kt 的記錄）而得到。的記錄）而得到。 如果如果vt 未標(biāo)號(hào)，則可以斷言不存在從未標(biāo)號(hào)，則可以斷言不存在從 vs到到vt的路。的路。11.2 最短路問(wèn)題dijkstra 雙標(biāo)號(hào)法 的步驟：jvivvvbjiji,),(如果上述的弧如果上述的弧(b)的集合不是空集，則轉(zhuǎn)下一步。的集合不是空集，則轉(zhuǎn)下一步。4. 對(duì)對(duì)b中的每一條弧，計(jì)算中的每一條弧，計(jì)算 sij = li + cij 。在所有的。在所有的 sij中，中，找到其值為最小的弧。不妨設(shè)此弧為（找到其值為最小的弧。不妨設(shè)此弧為（vc,vd），則給），則給此弧的終點(diǎn)以雙標(biāo)

12、號(hào)（此弧的終點(diǎn)以雙標(biāo)號(hào)（scd , c），返回步驟），返回步驟2。11.2 最短路問(wèn)題dijkstra 雙標(biāo)號(hào)法 的步驟：例例1. 求下圖中求下圖中v1到到v6的最短路的最短路11.2 最短路問(wèn)題dijkstra 雙標(biāo)號(hào)法 ：v23527531512v1v6v5v3v4v23527531512v1v6v5v3v4（0，s）0+30+20+5（2，1）2+1（3，1）(3,3)3+73+5(8,4) v1 v1到到v6v6的最短距離的最短距離為為8 8；最短路為：最短路為：v1 v3 v1 v3 v4 v4 v6v6page 15從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)從上例知，只要某點(diǎn)已標(biāo)號(hào)，

13、說(shuō)明已找到起點(diǎn)vs到到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出號(hào)，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能不能標(biāo)號(hào)，說(shuō)明標(biāo)號(hào)，說(shuō)明vs不可達(dá)不可達(dá)vj 。注：無(wú)向圖最短路的求法只將上述步驟中的弧改成邊即可。注：無(wú)向圖最短路的求法只將上述步驟中的弧改成邊即可。page 16例例3. 求下圖求下圖v1到各點(diǎn)的最短距離及最短路線。到各點(diǎn)的最短距離及最短路線。4526178393261216180452231039612641166188122482418所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是 v1 到該點(diǎn)的最短距離，

14、最短路線就是紅色的鏈。page 17課堂練習(xí)：課堂練習(xí)：1. 用用dijkstra算法求下圖從算法求下圖從v1到到v6的最短距離及路線。的最短距離及路線。v3v54v1v2v4v635222421v1到到v6的最短路為：的最短路為：6521vvvvpage 182. 求從求從v1到到v8的最短路徑的最短路徑237184566134105275934682page 19237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路徑為的最短路徑為v1v4v7v5v8，最短距離為，最短距離為10page 203. 求下圖中求下

15、圖中v1點(diǎn)到另外任意一點(diǎn)的最短路徑點(diǎn)到另外任意一點(diǎn)的最短路徑v1v2v3v4v6v5322762133page 21v1v2v3v4 v6v5322762133024714page 22v1v2v3v4 v6v5322762133024714page 23例例4. 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。通圖。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。 v1 （甲地）（甲地）1517624431065

16、v2v7 (乙地乙地)v3v4v5v6page 24解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題。解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題。 v1 （甲地）（甲地）1517624431065v2v7 (乙地乙地)v3v4v5v6(0,s)(10,1)(13,3)(14,3)(16,5)(18,5)(22,6)甲地到乙地的最短路為：甲地到乙地的最短路為：76531vvvvvpage 25例例5. 設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買(mǎi)新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)公司就要決定是購(gòu)買(mǎi)新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)置新設(shè)備，就要支付一定

17、的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：設(shè)備每年年初的價(jià)格表設(shè)備每年年初的價(jià)格表年份年份12345年初價(jià)格年初價(jià)格1111121213page 26設(shè)備維修費(fèi)如下表設(shè)備維修費(fèi)如下表使用年數(shù)使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用每年維修費(fèi)用568111

18、8解：解：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖：用將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖：用vi表示表示“第第i年年年年初購(gòu)進(jìn)一臺(tái)新設(shè)備初購(gòu)進(jìn)一臺(tái)新設(shè)備”,?。ɑ。╲i,vj）表示第）表示第i年年初購(gòu)進(jìn)的設(shè)備一年年初購(gòu)進(jìn)的設(shè)備一直使用到第直使用到第j年年初。年年初。v1v2v3v4v5v6page 27把所有弧的權(quán)數(shù)計(jì)算如下表，把權(quán)數(shù)賦到圖中，再用把所有弧的權(quán)數(shù)計(jì)算如下表，把權(quán)數(shù)賦到圖中，再用dijkstra算法求最短路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723pag

19、e 28 最終得到下圖，可知，最終得到下圖，可知，v1到到v6的距離是的距離是53，最短路徑有兩條：，最短路徑有兩條： v1v3v6和和 v1v4v6 v1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 v2（16,1）16(30,1)(53,3)(53,4)page 29性質(zhì)性質(zhì)1：任何樹(shù)中必存在次為：任何樹(shù)中必存在次為1的點(diǎn)。的點(diǎn)。性質(zhì)性質(zhì)2：n 個(gè)頂點(diǎn)的樹(shù)必有個(gè)頂點(diǎn)的樹(shù)必有n-1 條邊。條邊。性質(zhì)性質(zhì)3：樹(shù)中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。：樹(shù)中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)性質(zhì)4：樹(shù)連通，但去掉任一條邊，必變?yōu)椴贿B

20、通。：樹(shù)連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)性質(zhì)5：樹(shù)無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，?。簶?shù)無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。得到一個(gè)圈。v1v2v3v4v5v6l 樹(shù)：無(wú)圈的連通圖即為樹(shù)11.3 最小生成樹(shù)問(wèn)題圖圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)下列圖中，哪些是樹(shù)？下列圖中，哪些是樹(shù)？page 31圖圖g1=v1、e1和圖和圖g2=v2，e2，如果有如果有 ，稱，稱g1是是g2的一個(gè)的一個(gè)子圖子圖若有若有 ，則稱，則稱g1是是g2的一個(gè)的一個(gè)支撐子圖支撐子圖2121

21、eevv 和和2121eevv ，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5(a)v3e7e4e8e6e2e3v1v2v4v5(b)（g圖）圖）l 子圖，支撐子圖page 32如果如果g2是是g1的支撐圖（生成圖），又是樹(shù)圖，則稱的支撐圖（生成圖），又是樹(shù)圖，則稱g2是是g1的的生成樹(shù)（或支撐樹(shù)）。生成樹(shù)（或支撐樹(shù)）。v1v2v3v4v5v1v2v3v4v5g1g2l 圖的生成樹(shù)（支撐樹(shù)）page 33破圈法l 求支撐樹(shù)的方法：破圈法 和 避圈法page 34生成樹(shù)（支撐樹(shù)）生成樹(shù)（支撐樹(shù)）l 求支撐樹(shù)的方法：破圈法 和 避圈法page 35v1v2v

22、3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5l 求支撐樹(shù)的方法：破圈法 和 避圈法避圈法page 36最小生成樹(shù)問(wèn)題：在一個(gè)賦權(quán)的、連通的、無(wú)向圖 g 中找出一個(gè)生成樹(shù)，并使得這個(gè)生成樹(shù)的所有邊的權(quán)數(shù)之和為最小l 圖的最小生成樹(shù)（支撐樹(shù)）1. 在給定的賦權(quán)的連通圖上任找一個(gè)圈在給定的賦權(quán)的連通圖上任找一個(gè)圈2. 在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。3、如果所余下的圖已不包含圈，則計(jì)算結(jié)束

23、，所余下的、如果所余下的圖已不包含圈，則計(jì)算結(jié)束，所余下的圖即為最小生成樹(shù)，否則返回第圖即為最小生成樹(shù)，否則返回第1步。步。求解最小生成樹(shù)的破圈算法page 37v1v2v4v5v6435215878破圈法破圈法：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。5v1v2v3v4v5v6843752618v3邊數(shù)邊數(shù)n-1=5l 圖的最小生成樹(shù)（支撐樹(shù)）6page 38v1v2v3v4v5v643521min c(t)=15l 圖的最小生成樹(shù)（支撐樹(shù)）page 39page 40page 413749346321min c(t)=12min c(t)=15254173

24、314475答案：答案：page 4234122323242min c(t)=12213638534567454321min c(t)=18例例6. 用破圈算法求圖（用破圈算法求圖（a）中的一個(gè)最小生成樹(shù)）中的一個(gè)最小生成樹(shù)11.3 最小生成樹(shù)問(wèn)題v1331728541034v7v6v5v4v2v3(a)7v6v5v4v2v3(b)v133725434v7v6v5v4v2v31(c)v13372434v7v6v5v4v2v31(d)v4v1337234v7v6v5v2v31(e)v133723v7v6v5v4v2v31(f)例例7. 某大學(xué)準(zhǔn)備對(duì)其所屬的某大學(xué)準(zhǔn)備對(duì)其

25、所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中v1,v7 表表示示7個(gè)學(xué)院辦公室，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通個(gè)學(xué)院辦公室，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通7個(gè)學(xué)院辦個(gè)學(xué)院辦公室，并使總的線路長(zhǎng)度為最短。公室，并使總的線路長(zhǎng)度為最短。11.3 最小生成樹(shù)問(wèn)題v1331728541034v7v6v5v4v2v3圖圖11-14 此問(wèn)題實(shí)際上是求圖此問(wèn)題實(shí)際上是求圖11-1411-14的最小生成樹(shù)，的最小生成樹(shù)，這在例這在例6 6中已經(jīng)求得，中已經(jīng)求得，即按照?qǐng)D即按照?qǐng)D (f) (f) 的設(shè)計(jì)，的設(shè)計(jì)，可使此網(wǎng)絡(luò)的總的線可使此網(wǎng)絡(luò)的總的線

26、路長(zhǎng)度為最短，為路長(zhǎng)度為最短，為1919百米。百米。v563522241263v1v2v7v4v3v6圖圖11-2611.4 最大流問(wèn)題最大流問(wèn)題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過(guò)每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。一、最大流的數(shù)學(xué)模型 例例8. 某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷(xiāo)售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑運(yùn)送到一些銷(xiāo)售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（的變化，它的各段管道（vi,vj）的流量）的流量cij（容量

27、）是不一樣的。（容量）是不一樣的。cij的單的單位為萬(wàn)加侖位為萬(wàn)加侖/小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷(xiāo)地向銷(xiāo)地 v7運(yùn)送石油，運(yùn)送石油，問(wèn)每小時(shí)能運(yùn)送多少加侖石油？問(wèn)每小時(shí)能運(yùn)送多少加侖石油？v563522241263v1v2v7v4v3v6圖圖11-2611.4 最大流問(wèn)題 我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型： 設(shè)弧設(shè)弧(vi,vj)上流量為上流量為fij，網(wǎng)絡(luò)上的總的流量為，網(wǎng)絡(luò)上的總的流量為f，則有：，則有：1 41 22 32 51 44 34 64 72 34 33 53 62 53 55 73 64

28、66 75 76 74 71 21 4,1, 2, 6;1, 2,70,1, 2, 6;1, 2,71 2ijijijm a xf =fffffffffffffffffffffffffcijfij目 標(biāo) 函 數(shù) ：約 束 條 件 ：一、最大流的數(shù)學(xué)模型11.4 最大流問(wèn)題 1、在這個(gè)線性規(guī)劃模型中，其約束條件中的前、在這個(gè)線性規(guī)劃模型中，其約束條件中的前6個(gè)方程表示個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件：了網(wǎng)絡(luò)中的流量必須滿足守恒條件：發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量

29、必須等于總流出量。2、對(duì)每一條弧、對(duì)每一條弧(vi,vj)的流量的流量fij要滿足流量的可行條件，應(yīng)小要滿足流量的可行條件，應(yīng)小于等于弧于等于弧(vi,vj)的容量的容量cij，并大于等于零，即，并大于等于零，即0fij cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 fij 稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。11.4 最大流問(wèn)題一、最大流的數(shù)學(xué)模型二、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法 對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。對(duì)一條弧（對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。對(duì)一條弧（vi,vj)的的容量我們用一對(duì)數(shù)容量我們用一

30、對(duì)數(shù)cij,0標(biāo)在?。?biāo)在弧（vi,vj) 上，上，cij靠近靠近vi點(diǎn)點(diǎn)，0靠靠近近vj點(diǎn)，表示從點(diǎn)，表示從vi到到vj容許通過(guò)的容量為容許通過(guò)的容量為cij，而從，而從vj到到vi 容容許通過(guò)的容量為許通過(guò)的容量為0，這樣我們可以省去弧的方向了。如下圖，這樣我們可以省去弧的方向了。如下圖: (a)和和 (b)、(c)和和(d)的意義相同。的意義相同。vivjcij0（b）vivj（a） cijcijvivj（cji）（c）vivj cij cji（d）11.4 最大流問(wèn)題63522241263v1v2v5v7v4v3v60000000000011.4 最大流問(wèn)題二、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法

31、用以上方法對(duì)例用以上方法對(duì)例8的圖的容量標(biāo)號(hào)作改進(jìn)，得下圖：的圖的容量標(biāo)號(hào)作改進(jìn)，得下圖：（1）找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條?。┱页鲆粭l從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧 順流方向順流方向的容量都大于零的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。如果不存在這樣的路，則已經(jīng)求得最大流。（2）找出這條路上各條弧的）找出這條路上各條弧的 最小的順流的容量最小的順流的容量pf，從而通過(guò)這條路，從而通過(guò)這條路增加網(wǎng)絡(luò)的流量增加網(wǎng)絡(luò)的流量pf。（3）在這條路上，減少每一條弧的順流容量）在這條路上，減少每一條弧的順流容量pf ，同時(shí)增加這些弧的，同時(shí)增加這些弧的逆流容量逆流容量

32、pf，返回步驟（，返回步驟（1）。）。 * * * * * 為了使算法更快捷有效，我們一般在步驟（為了使算法更快捷有效，我們一般在步驟（1 1）中盡量選擇包）中盡量選擇包含弧數(shù)最少的路。含弧數(shù)最少的路。11.4 最大流問(wèn)題二、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法基本算法步驟：基本算法步驟： 第一次迭代：選擇路為第一次迭代：選擇路為 v1 v4 v7 。?。??；。?v4 , v7 ）的）的順流容量為順流容量為2，決定了，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：63522241263v1v2v5v7v4v3v60000000000042022第一次迭代第一次迭代后的總流量后的總流量2

33、11.4 最大流問(wèn)題二、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法用此方法對(duì)例用此方法對(duì)例8求解：求解： 第二次迭代：選擇路為第二次迭代：選擇路為v1 v2 v5 v7 ?；　；。?v2 , v5 ）的順流容量為）的順流容量為3，決定了，決定了pf=3，改進(jìn)的網(wǎng)，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：絡(luò)流量圖如下圖：635222413v1v2v5v7v4v3v6000000004202203330355第二次迭代第二次迭代后的總流量后的總流量11.4 最大流問(wèn)題二、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法 第三次迭代：選擇路為第三次迭代：選擇路為v1 v4 v6 v7 ?；??；。?v4 , v6 ）的順流容量為）的順流容量為1，決定了，決定

34、了pf=1，改進(jìn)的網(wǎng)，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：絡(luò)流量圖如下圖：222413v1v2v5v7v4v3v600000042022033333013166第三次迭代第三次迭代后的總流量后的總流量11.4 最大流問(wèn)題二、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法 第四次迭代：選擇路為第四次迭代：選擇路為v1 v4 v3 v6 v7 。弧?；。?v3 , v6 ）的順流容量為）的順流容量為2，決定了，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：圖如下圖： 22233v1v2v5v7v4v3v611000203203335031200213388第四次迭代第四次迭代后的總流量后的總流量111.4 最大流問(wèn)題二、

35、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法 第五次迭代：選擇路為第五次迭代：選擇路為v1 v2 v3 v5 v7 ?；??；。?v2 , v3 ）的順流容量為）的順流容量為2，決定了，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：圖如下圖：22v1v2v5v7v4v3v6101202033350120213315002020510第五次迭代第五次迭代后的總流量后的總流量1011.4 最大流問(wèn)題二、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法經(jīng)過(guò)第五次迭代后在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)的一經(jīng)過(guò)第五次迭代后在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)的一條路條路路上的每一條弧順流容量都大于零，運(yùn)算停止。路上的每一條弧順流容量都大于零，運(yùn)算停止

36、。得到最大流量為得到最大流量為10。 最大流量圖如下圖：最大流量圖如下圖：22v1v2v5v7v4v3v612352235511.4 最大流問(wèn)題二、最大流問(wèn)題的網(wǎng)絡(luò)圖論解法11.5 最小費(fèi)用最大流問(wèn)題一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條?。╲i,vj），除了給出容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個(gè)最大流 f，并使得總運(yùn)送費(fèi)用最小(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)一、最小費(fèi)用最大流的數(shù)學(xué)模型 例例9. 由于輸油管道的長(zhǎng)短不一，所以在例由于輸油管道的長(zhǎng)短不一，所以在例6中每段管道

37、（中每段管道（ vi,vj ）除了）除了有不同的流量限制有不同的流量限制cij外，還有不同的單位流量的費(fèi)用外，還有不同的單位流量的費(fèi)用bij ，cij的單位為的單位為萬(wàn)加侖萬(wàn)加侖/小時(shí)，小時(shí)， bij的單位為百元的單位為百元/萬(wàn)加侖。如下圖所示。從采地萬(wàn)加侖。如下圖所示。從采地 v1 向銷(xiāo)向銷(xiāo)地地 v7 運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最??？求出最大流量的最小費(fèi)用。??？求出最大流量的最小費(fèi)用。11.5 最小費(fèi)用最大流問(wèn)題(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2

38、）v1v2v5v7v4v3v6(6,3) 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1, 2,6;ijijijvvaijijfbfffffffffffs tffffffffffffffffffffffffffcij2,3,7),0,(1, 2,6;2,3,7),ijfij一、最小費(fèi)用最大流的數(shù)學(xué)模型11.5 最小費(fèi)用最大流問(wèn)題一、最小費(fèi)用最大流的數(shù)學(xué)模型 一般來(lái)說(shuō)，所謂最小費(fèi)用流的問(wèn)題就是：在給定了收點(diǎn)和一般來(lái)說(shuō)，所謂最小費(fèi)用流的問(wèn)題就是：在給定了收

39、點(diǎn)和發(fā)點(diǎn)并對(duì)每條弧發(fā)點(diǎn)并對(duì)每條弧(vi,vj)賦權(quán)以容量賦權(quán)以容量cij及單位費(fèi)用及單位費(fèi)用bij的網(wǎng)絡(luò)的網(wǎng)絡(luò)中，中，求一個(gè)給定流量 f 的最小費(fèi)用，這個(gè)給定流量，這個(gè)給定流量 f 應(yīng)小應(yīng)小于等于最大流量于等于最大流量f，否則無(wú)解。，否則無(wú)解。 求最小費(fèi)用流的問(wèn)題的線性規(guī)劃的模型只要把最小費(fèi)用最求最小費(fèi)用流的問(wèn)題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量大流模型中的約束條件中的發(fā)點(diǎn)流量f改為改為f即可。即可。11.5 最小費(fèi)用最大流問(wèn)題二、最小費(fèi)用最大流問(wèn)題的網(wǎng)絡(luò)圖論解法 對(duì)網(wǎng)絡(luò)上弧（對(duì)網(wǎng)絡(luò)上?。╲i,vj）的（）的（cij,bij）的表示作如下改動(dòng)）的表示作如下改動(dòng)11

40、.5 最小費(fèi)用最大流問(wèn)題vivj（cij,bij ）（0,-bij ）（b）vivj（a）（cij,bij ）（cij,bij ）vivj（cji,bji ）（c）（cij,bij ）vivj（cji,bji ）（0,-bij)（0,-bji)（d）11.5 最小費(fèi)用最大流問(wèn)題二、最小費(fèi)用最大流問(wèn)題的網(wǎng)絡(luò)圖論解法用以上方法對(duì)例用以上方法對(duì)例9的圖形進(jìn)行改進(jìn)，得下圖：的圖形進(jìn)行改進(jìn)，得下圖：(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-

41、4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖圖11-2811-2811.5 最小費(fèi)用最大流問(wèn)題二、最小費(fèi)用最大流問(wèn)題的網(wǎng)絡(luò)圖論解法最小費(fèi)用最大流的基本算法：最小費(fèi)用最大流的基本算法： 在對(duì)弧的標(biāo)號(hào)作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基在對(duì)弧的標(biāo)號(hào)作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基本算法，與求最大流的基本算法完全一樣，不同的只是：本算法，與求最大流的基本算法完全一樣，不同的只是： * 在步驟（在步驟（1）中要選擇一條總的單位費(fèi)用最小的路，而）中要選擇一條總的單位費(fèi)用最小的路，而不是包含邊數(shù)最小的路。不是包含邊數(shù)最小的路。用上述方法對(duì)例用上述方法對(duì)例9求解：求解： 第一次迭

42、代：找到最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭。第一次迭代后總流量為代后總流量為1，決定了，決定了pf=1,總費(fèi)用為總費(fèi)用為10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖圖11-2911-2911第一次迭代第一次迭代后的總流量后的總流量11.5 最小費(fèi)用最大流問(wèn)題二、最小費(fèi)用最大流問(wèn)題的網(wǎng)絡(luò)圖論解法 第二次迭代：找到最短路第二次迭代：找到最短路

43、v1 v4 v7。第二次迭代。第二次迭代后總流量為后總流量為3，總費(fèi)用，總費(fèi)用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖圖11-3011-3033第二次迭代第二次迭代后的總流量后的總流量11.5 最小費(fèi)用最大流問(wèn)題二、最小費(fèi)用最大流問(wèn)題的網(wǎng)絡(luò)圖論解法 第三次迭代：找到最短路第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后總流量為第三次迭代后總流量為5，總費(fèi)用，總費(fèi)用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-