運(yùn)籌學(xué)－圖與網(wǎng)絡(luò)分析

1、第十三章圖與網(wǎng)絡(luò)分析圖論的第篇論文：1736年，瑞士數(shù)學(xué)家歐拉的“依據(jù)幾何位置的解題方法”有效解決了哥尼斯堡七橋難題。圖論的第一本專(zhuān)著：1936年，匈牙利數(shù)學(xué)家狄.考尼格的 "有限圖與無(wú)限圖的理論”。哥尼斯堡七橋問(wèn)題:圖 13.1.1(a)d哥尼斯堡城中有一條普雷格爾河，河中有b、d兩島， 河上有七座橋，如圖13.1.1(a)。當(dāng)時(shí)那里的居民熱衷于這樣 的游戲：一個(gè)散步者能否連續(xù)走過(guò)七座橋，且走過(guò)每橋只一 次，最后回到出發(fā)點(diǎn)。歐拉將此問(wèn)題歸結(jié)為圖13.1.1(b)的一筆畫(huà)問(wèn)題，證明了 這是不可能的。當(dāng)且僅當(dāng)圖中全部頂點(diǎn)都與偶數(shù)條線相關(guān)聯(lián) 時(shí)，該圖才能一筆畫(huà)成。圖論中的圖用點(diǎn)代表所研究

2、的對(duì)象，用連線代表兩對(duì)象 之間的特定關(guān)系。這種圖與幾何圖形、函數(shù)圖形不同。13.1圖與網(wǎng)絡(luò)的基本知識(shí)一、無(wú)向圖1.無(wú)向圖邊：點(diǎn)與點(diǎn)之間的沒(méi)有方向性的連線。連接vi、vj兩 點(diǎn)的邊記作vi，vj或vj, vjo無(wú)向圖：由點(diǎn)和邊構(gòu)成的圖，記作g=(v, e),式中 v是圖g的點(diǎn)的集合，e是圖g的邊集合。v = vp v2，v5e = ep e?,ei= vp v2 = v2, vj2.簡(jiǎn)單圖環(huán)：兩個(gè)端點(diǎn)重合的邊。多重邊：兩個(gè)端點(diǎn)之間的邊數(shù)22。簡(jiǎn)單圖：無(wú)環(huán)也無(wú)多重邊的無(wú)向圖。以后說(shuō)到圖，如 無(wú)特殊說(shuō)明，均指簡(jiǎn)單圖。3.連通圖路：圖中一個(gè)以頂點(diǎn)始、以頂點(diǎn)終的頂點(diǎn)和邊的交替 序列（允許有頂點(diǎn)重復(fù)和邊重

3、復(fù)）。圖 13.1.2 中,（v3,知 v2，ep vp e8, v5, e9 g v）是一條路。簡(jiǎn)單路：如果出現(xiàn)在一條路中的邊都互不相同（允許 頂點(diǎn)重復(fù)，邊不重復(fù)），則這條路叫簡(jiǎn)單路。圖 13.1.2 中，（v3, e3, v2，ep vp e8, v5, e9, v2） 是一條簡(jiǎn)單路。初級(jí)路：如果出現(xiàn)在一條路中的頂點(diǎn)都互相不同，則 這條路叫初級(jí)路。（頂點(diǎn)不重復(fù)，邊當(dāng)然也不重復(fù)） 一般情況下，我們尋求的都是初級(jí)路。圖 13.1.2 中，（v3, e3, v2，ep v）是一條初級(jí)路。連通圖：圖g屮，若任何兩個(gè)不同的頂點(diǎn)之間，至少存在一條路，則稱(chēng)g是連通圖。二、有向圖1. 有向圖?。狐c(diǎn)與點(diǎn)之間

4、的有方向性的(用箭頭表示)連線。 若一條弧a=(vj, vj),則稱(chēng)vi為a的始點(diǎn)，比為a 的終點(diǎn)，弧a是從匕指向v)的。圖 13.1.3有向圖：由點(diǎn)和弧構(gòu)成的圖，記作d=(v, a),式中 v是圖d的點(diǎn)集合，a是圖d的弧集合。v = v1，v2，v5a = a, a?,39al = (vp v2)h(v2，vi)2. 簡(jiǎn)單有向圖環(huán)：兩個(gè)端點(diǎn)重合的弧。多重?。簝蓚€(gè)端點(diǎn)之間的同向弧數(shù)22。簡(jiǎn)單有向圖：無(wú)環(huán)也無(wú)多重弧的有向圖。簡(jiǎn)單有向圖 中，ai = (vi，vj) =(i, j)3路與有向路設(shè)有向圖為 d=(v,a), p= vp ap v2，a2? vk.p ak.pvd是一個(gè)由d的頂點(diǎn)和弧組

5、成的交替序列：路：若有 ai=(vi,j)或(vi+”vi) (i=l,2,.,k-l),則稱(chēng) p是一條連接vi與vk的路。例如圖13.1.4.(a)o有向路:若有 ai=(vi,vi+l) (i=l,2,.,k-l),則稱(chēng) p 是一條從v1到vk的有向路。例如圖13.1.4.(b)o圖 13.1.4.(a)圖 13.1.4.(b)4.前向弧與后向弧前向?。河幸粭l連接頂點(diǎn)v與vk的路，給定這條路 的一個(gè)假定方向，例如從v1到vk，則方向與路的假 定方向相同的弧叫“前向弧"。后向?。荷鲜銮闆r下，方向與路的假定方向相反的弧, 叫"后向弧”。圖13.14(a)中，假定路的方向是從

6、vi到v7，則a?、 a6是后向弧，其它均為前向弧。三、網(wǎng)絡(luò)網(wǎng)絡(luò)：給定有向圖d=(v, a),在v中指定了起點(diǎn)與 終點(diǎn)，其余點(diǎn)稱(chēng)為中間點(diǎn)。對(duì)于每一條弧(vi,vj)wa, 對(duì)應(yīng)有一個(gè)數(shù)qi，稱(chēng)為弧上的“權(quán)”，這種賦權(quán)有向 圖d稱(chēng)為網(wǎng)絡(luò)。每條弧可有一個(gè)或多個(gè)''權(quán)”，“權(quán)” 的含義可以是各種各樣的。13.2最短路問(wèn)題、最短路問(wèn)題舉例v6 (& 4)v5v)(0,1：v3 n 、(2, 1)圖 1321圖13.2.1是一個(gè)簡(jiǎn)單有向圖，每條?。╥, j）都有一個(gè)長(zhǎng)度cjj,求起點(diǎn)v1到終點(diǎn)v6的最短有向路。最短路問(wèn)題屬于線性規(guī)劃問(wèn)題，是運(yùn)輸問(wèn)題的特例。二、dijkstra算法

7、（雙標(biāo)號(hào)法）本算法適用于每條弧的長(zhǎng)度cijno的情況雙標(biāo)號(hào)：對(duì)一般頂點(diǎn)vi都賦予兩個(gè)標(biāo)號(hào)（厶，k）,厶是從起點(diǎn)v1到vi的最短路長(zhǎng)度ki是最短路徑上m點(diǎn)前面一個(gè)鄰點(diǎn)的下標(biāo)（正整數(shù)）。dijkstra算法基本步驟：1. 給起點(diǎn)vi標(biāo)(0,1)2. 求出此時(shí)的點(diǎn)集合i, j與弧集合ai：具有未賦標(biāo)號(hào)鄰點(diǎn)的已賦標(biāo)號(hào)點(diǎn)vi的下標(biāo)i的集合 (已賦標(biāo)號(hào)點(diǎn)t鄰點(diǎn))j： i中各點(diǎn)所具有的未賦標(biāo)號(hào)鄰點(diǎn)vj的下標(biāo)j的集合a； (i,j)liei, jej(弧的指向由 itj)例中第一次迭代：1= 1 j=2, 3, 4 a=(1,2) (1,3) (1,4)3. 若上述弧集合a是空集，則得到一族最優(yōu)結(jié)果。若上述弧

8、集合a不是空集，轉(zhuǎn)步驟4。4. 對(duì)a中的每條弧(i, j),分別計(jì)算sq = li + cij,令其中 sij值最小的弧為(c, d)例中：s)2 =/ +c 12=0+3=3s13 =/1 +c 13=0+2=2s4 =l +c4=°+5=5min(s12, s13, s14) = s3 =2即 scd=2, c=l, d=35. 給弧(c, d)的終點(diǎn)vd標(biāo)雙標(biāo)號(hào)gd, c),返回步驟2。例中：給v3標(biāo)(2, 1)以上，經(jīng)過(guò)一個(gè)循環(huán)的計(jì)算，求出v到一個(gè)頂點(diǎn)vj的最 短路徑及長(zhǎng)度，使一個(gè)頂點(diǎn)v)得到雙標(biāo)號(hào)。圖中共有n個(gè)頂 點(diǎn)，最多計(jì)算(ml)個(gè)循環(huán)，即可得最后結(jié)果。例中第二次迭代：

9、i= 1, 3 j=2, 4 a=(1, 2) (1,4) (3, 4) s34 =】3 +c34=2+1 =3 min = si2= s34 =3 給 v2標(biāo)(3,1), 給v4標(biāo)(3,3) 第三次迭代：i=2,4j=6a=(2, 6) (4, 6)s26 =】2 +c26=3+7=10s46 =仃 +c46=3+5=8=min 給v6標(biāo)(& 4)第四次迭代：i=j=a= 4),停止迭代。最后結(jié)果：此吋v5未得到標(biāo)號(hào)，表明從v1 v5無(wú)有向路。從v到v6的最短路徑是vt v3t v4t v6,最短距離為8o得到一族最優(yōu)結(jié)果。 dijkstra算法是一個(gè)公認(rèn)的好算法(多項(xiàng)式算法)。三、

10、無(wú)向圖上的dijkstra算法將無(wú)向圖t有向圖：每一條邊用方向相反的兩條弧代替。直接在無(wú)向圖上用dijkstra算法求解：與相應(yīng)有向圖上的 求解相比，鄰點(diǎn)個(gè)數(shù)可能增加，集合i、j、a中的元素均 可能增加，所有頂點(diǎn)都會(huì)得到標(biāo)號(hào)，最優(yōu)結(jié)果可能更優(yōu)。四、求解帶負(fù)權(quán)的最短路問(wèn)題如果權(quán)值有負(fù)的，則最短路問(wèn)題可采用動(dòng)態(tài)規(guī)劃屮不定 期最短路徑問(wèn)題的解法(函數(shù)迭代法、策略迭代法)。133最大流問(wèn)題一、網(wǎng)絡(luò)上的最大流問(wèn)題概述1. 網(wǎng)絡(luò)上的最大流問(wèn)題舉例v2v54vv73»圖 13.3.1例：圖13.3.1中，弧旁數(shù)字為該弧容量列，弧的方向就 是允許流的方向?，F(xiàn)在要把一批貨物由起點(diǎn)v1運(yùn)到終點(diǎn)v7 去，

11、每條弧上通過(guò)的貨物總量不能超過(guò)這條弧的容量。應(yīng)怎 樣安排運(yùn)輸,才能使從起點(diǎn)v.到終點(diǎn)v7的總運(yùn)量達(dá)到最大？2. 什么叫可行流？設(shè)切是通過(guò)弧(i, j)的運(yùn)輸量，則滿足下面二條件的組 網(wǎng)絡(luò)流國(guó)叫可行流：(1) 可行條件：對(duì)每一條弧(i,j),有owfijwqj(2) 守恒條件:對(duì)頂點(diǎn)旳而言式中a是所有以百為起點(diǎn)的弧的集合，b是所有以w為終點(diǎn)的弧的集合。上述f20,稱(chēng)為這個(gè)可行流的值(運(yùn)輸總量)。3. 最大流問(wèn)題是線性規(guī)劃問(wèn)題例：設(shè)各弧(i,j)上的可行流為角，總的可行流的值為f： 目標(biāo)函數(shù)：max f約束條件：f2 +f4 +fi3 =f壇+彳24才12 =0十57 _彳67 = _fowfij

12、wcij(i=l, 2,，6； j=2, 3,，7)二、ford-fulkerson 方法(1956 年)1. 什么叫可擴(kuò)充路？設(shè)fij是一組可行流，若存在一條連接v1與vn的路p(假 設(shè)其方向?yàn)橛蓈1到vn),滿足(1) 在p的所有前向弧上ffcij(2) 在p的所有后向弧上血0則稱(chēng)p是關(guān)于流垢的一條可擴(kuò)充路。2. 引理1對(duì)于一個(gè)可行流琮1)來(lái)說(shuō)，如果能找到一條可擴(kuò)充路p,那么血就可以改進(jìn)成一個(gè)值更大的可行流 fij(2) o3. 定理1已知肉是網(wǎng)絡(luò)的一個(gè)可行流，且對(duì)于切而言，不存在 可擴(kuò)充路，貝ll切是最大流。4. 算法步驟(1) 給泄一組初始可行流血及其值f例如，可給定初始值為全0。(2

13、) 尋找一條可擴(kuò)充路p若不存在可擴(kuò)充路，已得最大流；若存在可擴(kuò)充路p,轉(zhuǎn)步驟(3)。(3) 在p上將偽增流為偽。返回步驟。令e ! = mincij -血i (i,j)是p的前向弧若p上沒(méi)有前向弧，令e i =令e 2=min血i (i, j)是p的后向弧若p上沒(méi)有后向弧，令e 2= +°°增流量 £ = min( e b e 2)r f0)(若(i,j)不在p±)丄ij故fj2)= j + £ (若(i,j)是p的前向弧)f補(bǔ))£ (若(i, j)是p的后向弧)增流的結(jié)果或至少有一條前向弧上的流量血上升到列，成了“飽和弧”。或至少有

14、一條后向弧上的流量血下降到0,成了 “零流弧”。(相當(dāng)丁逆著弧的方向上有值為fij的增流量)臨界弧飽和弧與零流弧都叫做“臨界弧”。5尋找可擴(kuò)充路p的雙標(biāo)號(hào)法尋找可擴(kuò)充路p時(shí)，是從v開(kāi)始逐步向vn尋找。給每個(gè)頂點(diǎn)v）賦兩個(gè)標(biāo)號(hào)：第一個(gè)是k,它表明p上旳前面一個(gè)頂點(diǎn)是vk；第二個(gè)是"+ ”或”表示vk與舟之間沿箭 頭方向的可行流還可增加則表示還可減少圖 13.3.2取一點(diǎn)廉進(jìn)行檢查i:vi是一個(gè)已標(biāo)號(hào)而未檢查的點(diǎn)。對(duì)于vi的檢查，即是對(duì)的所有未標(biāo)號(hào)的鄰點(diǎn)vj進(jìn)行標(biāo)號(hào)(“臨界弧”除外)。(1)檢查所有以vi為起點(diǎn)的弧(i,j),若fijvcij,且vj未標(biāo) 號(hào)，則給vj標(biāo)(i, +) o

15、檢查所有以w為終點(diǎn)的弧(j, i),若切0,且勺未標(biāo) 號(hào)，則給vj標(biāo)(i, -)o 若前向弧(i,j)上有 妒駒,或后向弧(j,i)上有 加0,則 弧是臨界的，此時(shí)對(duì)vj不賦標(biāo)記。 若vi沒(méi)有未標(biāo)號(hào)的鄰點(diǎn),則vi已檢查完。(5)在出的第二個(gè)標(biāo)號(hào)上加一個(gè)小圈，呈或g),表示該點(diǎn)已檢查完。5. ford-fulkerson 方法的缺點(diǎn)當(dāng)網(wǎng)絡(luò)的容量可以取無(wú)理數(shù)時(shí)，用該法可能找不到最 大流。當(dāng)容量全是正整數(shù)時(shí)，有時(shí)需迭代許多次才能得到最 大流，且迭代次數(shù)不僅依賴(lài)于網(wǎng)絡(luò)屮的頂點(diǎn)數(shù)n和弧 數(shù)m,還依賴(lài)丁容量和最大流的值。上述缺點(diǎn)與選取可擴(kuò)充路時(shí)的任意性有關(guān)。三、edmonds-karp 方法(1972 年

16、)1. edmonds-karp方法的特點(diǎn)在ford-fulkerson方法的基礎(chǔ)上，對(duì)標(biāo)有*的部分遵循 “先標(biāo)號(hào)的頂點(diǎn)先檢查”，就可保證每一次迭代找到的可擴(kuò) 充路是“最短”的(即包含的弧數(shù)是最少的)，就能克服 ford-fulkerson方法的缺點(diǎn)。2.計(jì)算舉例圖1檢查完畢，給v4標(biāo)(1)例：用edmonds-karp方法求圖13.3.1所示網(wǎng)絡(luò)的最大流。 解：第一次迭代(見(jiàn)圖1),給定初始可行流為全零流，即 f()=0給起點(diǎn)vi標(biāo)(1, +)檢查v：給v2標(biāo)(1, +),v4 標(biāo)(1，+), v3 標(biāo)(1，+),檢查完畢，給v1標(biāo)(1,0)檢查v2：給v5標(biāo)(2, +),檢查完畢，給v2標(biāo)

17、(1,)檢查v4：給v6標(biāo)(4, +),檢查巾：沒(méi)有未標(biāo)記的鄰點(diǎn)，檢查完畢，給v3標(biāo)(1,) 檢查v5：給v7標(biāo)(5, +),檢查完畢，給v5標(biāo)(2,0 ) 至此，終點(diǎn)v7已標(biāo)號(hào)，得p：viv2v5v7f)=min4, 1,7=1, s 2(1)=<, £ (1)=min £ 1 ，£ 2(1)=1f=1第二次迭代，抹去原來(lái)的標(biāo)號(hào)，見(jiàn)圖2。給起點(diǎn)vi標(biāo)(1, +)檢查v：給v2標(biāo)(1,+),v4 標(biāo)(1，+), v3 標(biāo)(1，+),檢查完畢，給v標(biāo)(1g)檢查v2： v5不標(biāo)，檢查完畢，給v2標(biāo)(1,)% (4, +)(1/+) 4,0圖2v2 1j,0 4,3,0v4，+)3,5,a2,0、v7(5,+)8,0檢查v*給v5標(biāo)(4, +),檢查v3：沒(méi)有未標(biāo)記的鄰點(diǎn),檢查完畢，給v3標(biāo)(1®)給v6標(biāo)(4, +),檢查完畢，給v4標(biāo)(1g)檢查v5：給v7標(biāo)(5, +),檢查完畢，給v5標(biāo)(4，q )至此，終點(diǎn)v7已標(biāo)號(hào),得p:v1v4v5v7£=3f(2) =4第七次迭代，得p:v-> v3v