運籌學第八章-圖與網絡分析-胡運權

運籌學趙明霞山西大學經濟與管理學院2

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

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

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

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

多重圖：多重邊2024/8/16運籌學--線性規(guī)劃9完全圖：每一對頂點間都有邊（?。┫噙B的簡單圖2024/8/16運籌學--線性規(guī)劃10次（d）：結點的關聯邊數目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頂點次數總和等于邊數的兩倍。定理2次為奇數的頂點必為偶數個。11若,則G’是G的子圖，G是G’的母圖若,則G’是G的真子圖，若,則G’是G的支撐（生成）圖。鏈：點邊交替序列閉鏈：v1v2v3v4

v1開鏈：v1v2v3

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

v3v4

v2初等圈：初等閉鏈，v1

v2v3v4

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

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

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

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

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

到Vt

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

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

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

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

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

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

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