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

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

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

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

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

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

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

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

v1開鏈：v1v2v3

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

v3v4

v2初等圈：初等閉鏈，v1

v2v3v4

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

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

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

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

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

到Vt

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

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

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

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

例8-13（1）計算機編程48

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