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

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

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

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

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

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

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

7、（雙標號法）本算法適用于每條弧的長度cijno的情況雙標號：對一般頂點vi都賦予兩個標號（厶，k）,厶是從起點v1到vi的最短路長度ki是最短路徑上m點前面一個鄰點的下標（正整數(shù)）。dijkstra算法基本步驟：1. 給起點vi標(0,1)2. 求出此時的點集合i, j與弧集合ai：具有未賦標號鄰點的已賦標號點vi的下標i的集合 (已賦標號點t鄰點)j： i中各點所具有的未賦標號鄰點vj的下標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. 對a中的每條弧(i, 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)的終點vd標雙標號gd, c),返回步驟2。例中：給v3標(2, 1)以上，經(jīng)過一個循環(huán)的計算，求出v到一個頂點vj的最 短路徑及長度，使一個頂點v)得到雙標號。圖中共有n個頂 點，最多計算(ml)個循環(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標(3,1), 給v4標(3,3) 第三次迭代：i=2,4j=6a=(2, 6) (4, 6)s26 =】2 +c26=3+7=10s46 =仃 +c46=3+5=8=min 給v6標(& 4)第四次迭代：i=j=a= 4),停止迭代。最后結(jié)果：此吋v5未得到標號，表明從v1 v5無有向路。從v到v6的最短路徑是vt v3t v4t v6,最短距離為8o得到一族最優(yōu)結(jié)果。 dijkstra算法是一個公認的好算法(多項式算法)。三、

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

11、每條弧上通過的貨物總量不能超過這條弧的容量。應(yīng)怎 樣安排運輸,才能使從起點v.到終點v7的總運量達到最大？2. 什么叫可行流？設(shè)切是通過弧(i, j)的運輸量，則滿足下面二條件的組 網(wǎng)絡(luò)流國叫可行流：(1) 可行條件：對每一條弧(i,j),有owfijwqj(2) 守恒條件:對頂點旳而言式中a是所有以百為起點的弧的集合，b是所有以w為終點的弧的集合。上述f20,稱為這個可行流的值(運輸總量)。3. 最大流問題是線性規(guī)劃問題例：設(shè)各弧(i,j)上的可行流為角，總的可行流的值為f： 目標函數(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. 什么叫可擴充路？設(shè)fij是一組可行流，若存在一條連接v1與vn的路p(假 設(shè)其方向為由v1到vn),滿足(1) 在p的所有前向弧上ffcij(2) 在p的所有后向弧上血0則稱p是關(guān)于流垢的一條可擴充路。2. 引理1對于一個可行流琮1)來說，如果能找到一條可擴充路p,那么血就可以改進成一個值更大的可行流 fij(2) o3. 定理1已知肉是網(wǎng)絡(luò)的一個可行流，且對于切而言，不存在 可擴充路，貝ll切是最大流。4. 算法步驟(1) 給泄一組初始可行流血及其值f例如，可給定初始值為全0。(2

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

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

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

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

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