運(yùn)籌學(xué)圖論課件

第五章圖與網(wǎng)絡(luò)分析§1圖與網(wǎng)絡(luò)的基本概念

§2最小生成樹問題

§3最短路問題

§4最大流問題

運(yùn)籌學(xué)圖論5-1圖與網(wǎng)絡(luò)的基本概念運(yùn)籌學(xué)圖論一、圖與網(wǎng)絡(luò)的基本概念1、圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系。例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來表示，圖7-1就是一個表示這種關(guān)系的圖。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5圖7-1運(yùn)籌學(xué)圖論

當(dāng)然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的，如對趙等七人的相互認(rèn)識關(guān)系我們也可以用圖5-2來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5圖5-2運(yùn)籌學(xué)圖論a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳圖5-3

如果我們把上面例子中的“相互認(rèn)識”關(guān)系改為“認(rèn)識”的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧。圖5-3就是一個反映這七人“認(rèn)識”關(guān)系的圖。相互認(rèn)識用兩條反向的弧表示。運(yùn)籌學(xué)圖論2、無向圖：由點(diǎn)和邊構(gòu)成的圖，記作G=（V，E）。3、有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D=（V，A）。4、連通圖：對無向圖G，若任何兩個不同的點(diǎn)之間，至少存在一條鏈，則G為連通圖。5、回路：若路的第一個點(diǎn)和最后一個點(diǎn)相同，則該路為回路。6、賦權(quán)圖：對一個無向圖G的每一條邊(vi,vj)，相應(yīng)地有一個數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。7、網(wǎng)絡(luò)：在賦權(quán)的有向圖D中指定一點(diǎn)，稱為發(fā)點(diǎn)，指定另一點(diǎn)稱為收點(diǎn)，其它點(diǎn)稱為中間點(diǎn)，并把D中的每一條弧的賦權(quán)數(shù)稱為弧的容量，D就稱為網(wǎng)絡(luò)。運(yùn)籌學(xué)圖論二、七橋問題ACBD哥尼斯堡的普雷格爾河運(yùn)籌學(xué)圖論提出問題：一個散步者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點(diǎn)。1973年，歐拉將此問題歸結(jié)為如圖所示的一筆畫問題。

·

·

·

·ACBDd(A)=3d(B)=3d(C)=5d(D)=3運(yùn)籌學(xué)圖論將點(diǎn)看成事物，邊看成事物與事物的聯(lián)系。秩為奇數(shù)的為奇頂點(diǎn)；秩為偶數(shù)的為偶頂點(diǎn)。如何一個圖都可以由邊的集合和點(diǎn)的集合所組成。點(diǎn)——不考慮位置；邊——不考慮形狀與聯(lián)系；歐拉定理：

a、一個圖奇頂點(diǎn)的個數(shù)為“0”時，可既不重復(fù)，也不遺漏走完所有橋還能回到原處。

b、一個圖奇頂點(diǎn)的個數(shù)為“2”時，可不重復(fù)，不遺漏走完所有橋但不能回到原處；

c、一個圖奇頂點(diǎn)的個數(shù)大于“2”時，不可能既不重復(fù)，也不遺漏走完而且回到原處。運(yùn)籌學(xué)圖論案例1：有甲、乙、丙、丁、戊、己六名運(yùn)動員報名參加A、B、C、D、E、F六個項(xiàng)目的比賽。如表所示中打的是各運(yùn)動員報名參加的比賽項(xiàng)目。問六個項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動員都不連續(xù)地參加兩項(xiàng)比賽。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√ABCDEF●●●●●●A-C-B-F-E-D運(yùn)籌學(xué)圖論ABCDEF●●●●●●A-E-B-C-D-FA-E-C-B-D-F案例2：某廠辦公室在三天內(nèi)開一個會，請10位領(lǐng)導(dǎo)第一天上午開幕式A第三天下午閉幕式F每天每位領(lǐng)導(dǎo)只能開半天會。

領(lǐng)導(dǎo)內(nèi)容12345678910A√√√√√√B√√√√C√√√√√D√√√E√√√F√√√√√運(yùn)籌學(xué)圖論5-2最小生成樹問題運(yùn)籌學(xué)圖論樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。

圖7-4中，(a)就是一個樹，而(b)因?yàn)閳D中有圈所以就不是樹，(c)因?yàn)椴贿B通所以也不是樹。圖7-4v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)運(yùn)籌學(xué)圖論

給了一個無向圖G=(V,E)，我們保留G的所有點(diǎn)，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在圖7-5中，(b)和(c)都是(a)的生成子圖。如果圖G的一個生成子圖還是一個樹，則稱這個生成子圖為生成樹，在圖7-5中，(c)就是(a)的生成樹。最小生成樹問題就是指在一個賦權(quán)的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權(quán)數(shù)之和為最小。圖7-5(a)(b)(c)運(yùn)籌學(xué)圖論一、求解最小生成樹的破圈算法算法的步驟：1、在給定的賦權(quán)的連通圖上任找一個圈。2、在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。3、如果所余下的圖已不包含圈，則計(jì)算結(jié)束，所余下的圖即為最小生成樹，否則返回第1步。運(yùn)籌學(xué)圖論e3e7V1V3V2V4V5V6e1e6e8e251e452e5734e94例1：如何架設(shè)電話線，使得耗材最少？5（一）破圈法：丟邊（大邊），破圈?！嘧钌儋M(fèi)用為：5+1+2+3+4=15運(yùn)籌學(xué)圖論e3e7V1V3V2V4V5V6e6e8e251e452e5734e94例2：如何架設(shè)電話線，使得耗材最少？e15（二）避圈法：∴最少費(fèi)用為：5+1+2+3+4=15運(yùn)籌學(xué)圖論練習(xí)：（a）3213232252534222破圈法：最小支撐樹=18運(yùn)籌學(xué)圖論3213232252534222避圈法：最小支撐樹=18運(yùn)籌學(xué)圖論（b）7538623554破圈法：最小支撐樹=22運(yùn)籌學(xué)圖論（b）7538623554避圈法：最小支撐樹=22運(yùn)籌學(xué)圖論5-3最短路問題運(yùn)籌學(xué)圖論最短路問題：對一個賦權(quán)的有向圖D中的指定的兩個點(diǎn)Vs和Vt找到一條從Vs

到Vt

的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。一、Dijkstra算法1、思路：這種算法的基本思路是：假定V1-V2-V3-V4是V1-V4的最短路。2、假設(shè)：若用dij表示兩相鄰點(diǎn)i與j的距離，若i與j不相鄰，令dij=∞，顯然dii=0。3、步驟：（1）從點(diǎn)s出發(fā)，因Lss=0，將此值標(biāo)注在s旁的小方框內(nèi)，表示s點(diǎn)已標(biāo)號；（2）從s點(diǎn)出發(fā)，找出與s相鄰的點(diǎn)中距離最小的一個，設(shè)為r。將Lsr=Lss+dsr的值標(biāo)注在r旁的小方框內(nèi)，表明點(diǎn)r已標(biāo)號；（3）從已標(biāo)號的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號點(diǎn)p。若有Lsp=min{Lss+dsp；Lsr+drp}，則對p點(diǎn)標(biāo)號，并將Lsp的值標(biāo)注在p點(diǎn)旁的小方框內(nèi)；（4）重復(fù)第3步，一直到t點(diǎn)得到標(biāo)號為止；運(yùn)籌學(xué)圖論例1、從發(fā)電廠向某城市輸送電，必須通過中轉(zhuǎn)站轉(zhuǎn)送，如下圖，電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。1642534323322解：L1r=min{d12,d13}=min{4，3}=3=L13L1p=min{L11+d12，L13+d35}=min{0+4，3+3}=4=L12L1p=min{L12+d24，L12+d25，L13+d35}=min{4+3，4+2，3+3}=6=L15L1p=min{L12+d24，L15+d56}=min{4+3，6+2}=7=L14L1p=min{L14+d46，L15+d56}=min{7+2，6+2}=8=L16所以：最短路是V1V3V5V6

路長是P（6）=8運(yùn)籌學(xué)圖論例2：求下圖中V1到V6的最短路1563423253725115解：L1r=min{d12,d14，d13}=min{3，5，2}=2=d13L1p=min{L11+d12，L11+d14，L13+d34}=min{3，5，3}=3=L12=L14L1p=min{L12+d26，L14+d46}=min{3+7，3+5}=8=L16得到結(jié)果：從1—6最短路為1—3—4—6，5沒有標(biāo)號，說明從1—5沒有有向路運(yùn)籌學(xué)圖論

例3求下圖中v1到v6的最短路解：采用Dijkstra算法，可解得最短路徑為v1v3v4v6

各點(diǎn)的標(biāo)號圖如下：v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4運(yùn)籌學(xué)圖論

例4電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。

解：這是一個求無向圖的最短路的問題。可以把無向圖的每一邊（vi,vj）都用方向相反的兩條?。╲i,vj）和（vj,vi）代替，就化為有向圖，即可用Dijkstra算法來求解。也可直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標(biāo)號的點(diǎn)到未標(biāo)號的點(diǎn)的弧的集合改成已標(biāo)號的點(diǎn)到未標(biāo)號的點(diǎn)的邊的集合即可。V1（甲地）15176244431065v2V7（乙地）v3v4v5v6運(yùn)籌學(xué)圖論例4最終解得：最短路徑v1v3v5v6v7，每點(diǎn)的標(biāo)號見下圖（0,s）

V1（甲地）1517624431065(13,3)v2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)運(yùn)籌學(xué)圖論二、矩陣算法：P1261、思路：這種算法的基本思路是：假定V1-V2-V3-V4是V1-V4的最短路。也是V4-V1的最短路。2、假設(shè)：若用dij表示兩相鄰點(diǎn)i與j的距離，若i與j不相鄰，令dij=∞，顯然dii=0。3、步驟：（1）從點(diǎn)s出發(fā)，因Lss=0，將此值標(biāo)注在s旁的小方框內(nèi)，表示s點(diǎn)已標(biāo)號；（2）從s點(diǎn)出發(fā)，找出與s相關(guān)的所有點(diǎn)，設(shè)為r。將Lsr=Lst+dtr的值，從中選擇min；為此可以構(gòu)造出一個新的矩陣D（1）。則D（1）矩陣給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)和包括經(jīng)過一個中間點(diǎn)時的最短距離。（3）再構(gòu)造矩陣D（2）。令dij(2)=min{dir(1)+drj(1)},則D（2）給出了網(wǎng)絡(luò)中任意兩點(diǎn)直接到達(dá)，及包括經(jīng)過一個至三個中間點(diǎn)時的最短距離。（4）重復(fù)第1，2，3步，一直到出現(xiàn)D(m+1)=D(m)時為止。運(yùn)籌學(xué)圖論練習(xí)：某一個配送中心要給一個快餐店送快餐原料，應(yīng)按照什么路線送貨才能使送貨時間最短。16754324187121626856(4,1)(16,2)(18,3)(22,3)(25,4)(27,5)運(yùn)籌學(xué)圖論

例6設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費(fèi)，但維修費(fèi)用就高了。請?jiān)O(shè)計(jì)一個五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：設(shè)備每年年初的價格表設(shè)備維修費(fèi)如下表年份12345年初價格1111121213使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用5681118運(yùn)籌學(xué)圖論例6的解：將問題轉(zhuǎn)化為最短路問題，如下圖：用vi表示“第i年年初購進(jìn)一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初。把所有弧的權(quán)數(shù)計(jì)算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186運(yùn)籌學(xué)圖論(繼上頁)把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。

最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條：

v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)運(yùn)籌學(xué)圖論5-4最大流問題運(yùn)籌學(xué)圖論最大流問題：給一個帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。一、最大流的數(shù)學(xué)模型例6某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn)，這個網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬加侖/小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運(yùn)送石油，問每小時能運(yùn)送多少加侖石油？v563522241263v1v2v7v4v3v6圖5-6運(yùn)籌學(xué)圖論

我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，則有：運(yùn)籌學(xué)圖論

在這個線性規(guī)劃模型中，其約束條件中的前6個方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。其后面幾個約束條件表示對每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應(yīng)小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流{fij}稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。我們把例6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運(yùn)籌學(xué)軟件”，馬上得到以下的結(jié)果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最優(yōu)值（最大流量）=10。運(yùn)籌學(xué)圖論基本概念：容量：對網(wǎng)絡(luò)上的每條弧都給予一個最大的通過能力，稱為弧的容量。可行流：即滿足最大流：從網(wǎng)絡(luò)的發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量。割：將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使發(fā)點(diǎn)到收點(diǎn)的流中斷的一組弧的集合。P130運(yùn)籌學(xué)圖論求網(wǎng)絡(luò)最大流的標(biāo)號算法步驟：P132例：P132運(yùn)籌學(xué)圖論4、求網(wǎng)絡(luò)最大流，圖中數(shù)據(jù)為Cij1055105155Vt1010252020205551010Vs運(yùn)籌學(xué)圖論P(yáng)137.572426618434732135V1V2V5V3V4V8V7V6破圈法最小支撐樹=16（a）運(yùn)籌學(xué)圖論P(yáng)137.572426618434732135V1V2V5V3V4V8V7V6避圈法最小支撐樹=16運(yùn)籌學(xué)圖論24236106158462182108121057V1V6V5V7V3V2V4V11V9V8V10破圈法：最小支撐樹=32運(yùn)籌學(xué)圖論24236106158462182108121057V1V6V5V7V3V2V4V11V9V8V10避圈法：最小支撐樹=32運(yùn)籌學(xué)圖論P(yáng)137.813