運(yùn)籌學(xué)第八章-圖與網(wǎng)絡(luò)分析-胡運(yùn)權(quán)

運(yùn)籌學(xué)趙明霞山西大學(xué)經(jīng)濟(jì)與管理學(xué)院2

第八章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)的基本概念樹最短路問(wèn)題最大流問(wèn)題最小費(fèi)用最大流問(wèn)題2024/8/163柯尼斯堡七橋問(wèn)題歐拉回路：經(jīng)過(guò)每邊且僅一次厄尼斯堡七橋問(wèn)題、郵路問(wèn)題哈密爾頓回路：經(jīng)過(guò)每點(diǎn)且僅一次貨郎擔(dān)問(wèn)題、快遞送貨問(wèn)題4第一節(jié)圖與網(wǎng)絡(luò)的基本概念圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示，圖8.1就是一個(gè)表示這種關(guān)系的圖。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5圖8.15描述對(duì)象之間關(guān)系，研究特定關(guān)系之間的內(nèi)在規(guī)律，圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5圖8.26a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳圖8.3

如果我們把上面例子中的“相互認(rèn)識(shí)”關(guān)系改為“認(rèn)識(shí)”的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧。無(wú)向圖：由點(diǎn)和邊構(gòu)成的圖，記作G=（V，E）。有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D=（V，A）。無(wú)向圖是有向圖的基礎(chǔ)圖G(D)有限圖無(wú)限圖2024/8/16運(yùn)籌學(xué)--線性規(guī)劃7G=(V,E)關(guān)聯(lián)邊(m)：ei端（頂）點(diǎn)(n)：vi,vj點(diǎn)相鄰(同一條邊)：

v1,v3邊相鄰(同一個(gè)端點(diǎn))：e2,e3環(huán)：e1多重邊：

e4,e58簡(jiǎn)單圖：無(wú)環(huán)無(wú)多重邊

多重圖：多重邊2024/8/16運(yùn)籌學(xué)--線性規(guī)劃9完全圖：每一對(duì)頂點(diǎn)間都有邊（?。┫噙B的簡(jiǎn)單圖2024/8/16運(yùn)籌學(xué)--線性規(guī)劃10次（d）：結(jié)點(diǎn)的關(guān)聯(lián)邊數(shù)目d(v3)=4，偶點(diǎn)d(v2)=3，奇點(diǎn)d(v1)=4d(v4)=1，懸掛點(diǎn)e6,懸掛邊d(v5)=0，孤立點(diǎn)出次：d+(vi)入次：d-(vi)d

(vi)=d+(vi)+d-(vi)定理1頂點(diǎn)次數(shù)總和等于邊數(shù)的兩倍。定理2次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。11若,則G’是G的子圖，G是G’的母圖若,則G’是G的真子圖，若,則G’是G的支撐（生成）圖。鏈：點(diǎn)邊交替序列閉鏈：v1v2v3v4

v1開鏈：v1v2v3

邊不同，簡(jiǎn)單鏈：v3v4v5v1v6v5邊不同且結(jié)點(diǎn)不同，初等鏈：v1v2v3v4v5v6圈：閉鏈，且至少有3個(gè)不同結(jié)點(diǎn)，v2

v3v4

v2初等圈：初等閉鏈，v1

v2v3v4

v112路：有向圖：弧的方向與鏈的方向一致開路:v1v2v4v5回路：第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)相同。v1v2v4v5v113連通圖：若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則G為連通圖。賦權(quán)圖：對(duì)一個(gè)圖的每一條邊（弧）(vi,vj)，相應(yīng)地有一個(gè)數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。網(wǎng)絡(luò)：賦權(quán)連通圖無(wú)向圖：開鏈即開路，閉鏈即回路有向圖：弧的方向與鏈的方向一致。2024/8/16運(yùn)籌學(xué)--線性規(guī)劃142024/8/1615柯尼斯堡七橋問(wèn)題歐拉回路：經(jīng)過(guò)每邊且僅一次厄尼斯堡七橋問(wèn)題、郵路問(wèn)題充要條件：無(wú)向圖中無(wú)奇點(diǎn)，有向圖每個(gè)頂點(diǎn)出次等于入次16第二節(jié)樹樹是圖論中的重要概念，所謂樹就是一個(gè)無(wú)圈的連通圖。

圖8-4中，(a)就是一個(gè)樹，而(b)因?yàn)閳D中有圈所以就不是樹，(c)因?yàn)椴贿B通所以也不是樹。圖8-4v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)樹的基本性質(zhì)任意兩點(diǎn)間有且僅有一條鏈不相鄰兩點(diǎn)間添加一條邊，有且僅有一個(gè)圈任意去掉一條邊，得不連通圖.存在懸掛點(diǎn)m=n-11718

(a)(b)(c)生成（支撐）樹若,則G’是G的支撐（生成）樹。191、破圈算法步驟：（1）在給定的賦權(quán)的連通圖上任找一個(gè)圈。（2）在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。（3）如果所余下的圖已不包含圈，則計(jì)算結(jié)束，所余下的圖即為最小樹，否則返回第1步。最小生成樹問(wèn)題就是指在一個(gè)賦權(quán)的連通的無(wú)向圖G中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。20例8.12、避圈算法步驟：（1）任找一個(gè)點(diǎn)S，其余各點(diǎn)就是。（2）在連接S與

的所有邊中，選擇權(quán)數(shù)最小的邊(i,k)；（3）將最小邊(i,k)的另一個(gè)端點(diǎn)移入S；（4）若

則停止，否則返回（2）。2122例8.1有向樹：不考慮方向時(shí)是樹根樹（外向樹）：只有一個(gè)頂點(diǎn)入次為0，其余頂點(diǎn)入次為1根：入次為0的頂點(diǎn)葉：出次為0的頂點(diǎn)分支點(diǎn)層次：根到頂點(diǎn)的長(zhǎng)度2024/8/16運(yùn)籌學(xué)--線性規(guī)劃23m叉樹：每個(gè)頂點(diǎn)的出次小于等于m完全m叉樹：每個(gè)頂點(diǎn)的出次等于m或02024/8/16運(yùn)籌學(xué)--線性規(guī)劃242024/8/16運(yùn)籌學(xué)--線性規(guī)劃25霍夫曼樹：最優(yōu)二叉樹26第三節(jié)最短路問(wèn)題最短路問(wèn)題：對(duì)一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)Vs(起點(diǎn))和Vt（終點(diǎn)）找到一條從Vs

到Vt

的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。27適用于：每條?。ㄟ叄┑馁x權(quán)數(shù)wij≥0優(yōu)點(diǎn)：能夠求出某點(diǎn)至各點(diǎn)的最短路基本思想：T(j)（tentativelabel）——從始點(diǎn)s到j(luò)點(diǎn)的最短路長(zhǎng)上界，稱為試探性標(biāo)號(hào);P(j)

（permanentlabel）——從始點(diǎn)s到j(luò)點(diǎn)的最短路長(zhǎng)，稱為永久性標(biāo)號(hào).一、狄氏標(biāo)號(hào)法（Dijkstra算法）例8-92024/8/16運(yùn)籌學(xué)--線性規(guī)劃28基本步驟標(biāo)號(hào)T(j)→P(j)2024/8/16運(yùn)籌學(xué)--線性規(guī)劃292024/8/1630最長(zhǎng)路問(wèn)題例8-10（7-9）設(shè)某臺(tái)新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表。試確定今后5年內(nèi)的更新策略，使總收益最大。役齡項(xiàng)目012345效益vk(t)54.543.7532.5維修費(fèi)uk(t)0.511.522.53更新費(fèi)ck(t)-1.52.22.533.52024/8/16運(yùn)籌學(xué)--線性規(guī)劃31網(wǎng)絡(luò)中心（r點(diǎn)）32例8-11某連鎖企業(yè)有6個(gè)銷售點(diǎn)，問(wèn)倉(cāng)庫(kù)應(yīng)建在哪個(gè)地點(diǎn)，可使各銷售點(diǎn)離倉(cāng)庫(kù)較近？2024/8/16運(yùn)籌學(xué)--線性規(guī)劃33各點(diǎn)間的最短距離34二、Floyd算法2024/8/1635例8-12求任意兩點(diǎn)間的最短路2024/8/16362024/8/16372024/8/16運(yùn)籌學(xué)--線性規(guī)劃38容量網(wǎng)絡(luò)(網(wǎng)絡(luò))：N=(V,A,c)或

N=(V,A)，最大流量cij=c(i,j)網(wǎng)絡(luò)流：可行流：s發(fā)點(diǎn)，t收點(diǎn)可行流流量：39第四節(jié)最大流問(wèn)題割(截)集：S中各點(diǎn)聯(lián)通，S

中各點(diǎn)聯(lián)通始點(diǎn)在S，終點(diǎn)在S的集合，稱為一個(gè)分離發(fā)點(diǎn)s和收點(diǎn)t的割集，（S,S）割集容量：最小割：最小的割集容量40定理8-10：網(wǎng)絡(luò)任一可行流的流量恒不超過(guò)任一割集的容量。定理8-11：最大流=最小割2024/8/16運(yùn)籌學(xué)--線性規(guī)劃41增廣（容）鏈：為從發(fā)點(diǎn)s到收點(diǎn)t的一條鏈，且前向弧均非飽和，后向弧均非零流。最大流：流量最大的可行流。可行流為最大流的充要條件：不存在從s到t的增廣鏈2024/8/16運(yùn)籌學(xué)--線性規(guī)劃42（一）線性(整數(shù))規(guī)劃法例8-132024/8/1644（二）網(wǎng)絡(luò)分析法增廣鏈調(diào)整法45Ford—Fulkerson標(biāo)號(hào)法基本思想：先確定一個(gè)初始可行流，再找增容鏈，調(diào)整流量，直到找不到增容鏈為止。雙標(biāo)號(hào)（i,b(j)），b(j)—當(dāng)前最大可調(diào)容量運(yùn)算步驟：發(fā)點(diǎn)s標(biāo)號(hào)（0,∞）；給所有相鄰點(diǎn)標(biāo)號(hào)正向弧且，則j標(biāo)號(hào)（i,b(j)）

，則j不標(biāo)號(hào)逆向弧且，則j標(biāo)號(hào)（-i,b(j)）檢查標(biāo)號(hào)調(diào)整量47

例8-13（1）計(jì)算機(jī)編程48

（2）手算f*=112024/8/16492024/8/1650最小費(fèi)用最大流問(wèn)題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)N=(V,A,c,d)，對(duì)每一條?。╥，j），除了給出容量cij外，還給出了這條弧的單位流量的費(fèi)用dij，要求一個(gè)最大流f，并使得總運(yùn)送費(fèi)用最小。51先求出此網(wǎng)絡(luò)圖中的最大流量f。在最大流量f的所有解中，找出一個(gè)最小費(fèi)用的解（一）線性(整數(shù))規(guī)劃法第五節(jié)最小費(fèi)用最大流問(wèn)題2024/8/1652例8-15第一步第二步53對(duì)偶網(wǎng)絡(luò)