關于運籌學圖與網絡模型圖論

GraphTheory哥尼斯堡七橋問題(K?nigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年發(fā)表第一篇圖論方面的論文，奠基了圖論中的一些基本定理很多問題都可以用點和線來表示，一般點表示實體，線表示實體間的關聯BACD第2頁,共56頁，2024年2月25日，星期天§1

圖與網絡的基本概念

1.1圖與網絡節(jié)點(Vertex)物理實體、事物、概念一般用vi

表示邊(Edge)節(jié)點間的連線，表示有關系一般用eij

表示圖(Graph)節(jié)點和邊的集合，一般用G(V,E)表示點集V={v1,v2,…,vn}邊集E={eij}網絡(Network)邊上具有表示連接強度的權值，如wij又稱加權圖(Weightedgraph)第3頁,共56頁，2024年2月25日，星期天1.2無向圖與有向圖邊都沒有方向的圖稱為無向圖，如圖1在無向圖中eij=eji，或(vi,vj)=(vj,vi)當邊都有方向時，稱為有向圖，用G(V,A)表示在有向圖中，有向邊又稱為弧，用aij表示，i,j的順序是不能顛倒的，圖中弧的方向用箭頭標識圖中既有邊又有弧，稱為混合圖第4頁,共56頁，2024年2月25日，星期天

1.3端點，關聯邊，相鄰，次圖中可以只有點，而沒有邊；而有邊必有點若節(jié)點vi,vj

之間有一條邊eij，則稱vi,vj

是eij的端點(endvertex)，而eij

是節(jié)點vi,vj的關聯邊(incid%ntedge)同一條邊的兩個端點稱為相鄰(adjacent)節(jié)點，具有共同端點的邊稱為相鄰邊一條邊的兩個端點相同，稱為自環(huán)(self-loop)；具有兩個共同端點的兩條邊稱為平行邊(paralleledges)既沒有自環(huán)也沒有平行邊的圖稱為簡單圖(simplegraph)在無向圖中，與節(jié)點相關聯邊的數目，稱為該節(jié)點的“次”(degree)，記為d

；次數為奇數的點稱為奇點(odd),次數為偶數的點稱為偶點(even)；圖中都是偶點的圖稱為偶圖(evengraph)第5頁,共56頁，2024年2月25日，星期天

1.3端點，關聯邊，相鄰，次有向圖中，由節(jié)點指向外的弧的數目稱為正次數，記為d+，指向該節(jié)點的弧的數目稱為負次數，記為d–次數為0的點稱為孤立點(isolatedvertex)

，次數為1的點稱為懸掛點(pendantvertex)定理1：圖中奇點的個數總是偶數個

1.4鏈，圈，路徑，回路，歐拉回路相鄰節(jié)點的序列

{v1

,v2

,…,vn

}構成一條鏈(link)，又稱為行走(walk)；首尾相連的鏈稱為圈(loop)，或閉行走在無向圖中，節(jié)點不重復出現的鏈稱為路徑(path)；在有向圖中，節(jié)點不重復出現且鏈中所有弧的方向一致，則稱為有向路徑(directedpath)首尾相連的路徑稱為回路(circuit)；第6頁,共56頁，2024年2月25日，星期天

1.4鏈，圈，路徑，回路，連通圖走過圖中所有邊且每條邊僅走一次的閉行走稱為歐拉回路定理2：偶圖一定存在歐拉回路(一筆畫定理)1.4連通圖，子圖，成分設有兩個圖G1(V1,E1),G2(V2,E2),若V2

V1,E2

E1，則G2是G1的子圖無向圖中，若任意兩點間至少存在一條路徑，則稱為連通圖(connectedgraph)，否則為非連通圖(discon-nectedgraph)；非連通圖中的每個連通子圖稱為成分

(component)鏈，圈，路徑(簡稱路)，回路都是原圖的子圖平面圖(planargraph)，若在平面上可以畫出該圖而沒有任何邊相交第7頁,共56頁，2024年2月25日，星期天§2樹圖與最小生成樹一般研究無向圖樹圖：倒置的樹，根(root)在上，樹葉(leaf)在下多級輻射制的電信網絡、管理的指標體系、家譜、分類學、組織結構等都是典型的樹圖第8頁,共56頁，2024年2月25日，星期天

2.1樹的定義及其性質任兩點之間有且只有一條路徑的圖稱為樹(tree)，記為T

樹的性質：最少邊的連通子圖，樹中必不存在回路任何樹必存在次數為1的點具有n

個節(jié)點的樹T的邊恰好為

n

1條，反之，任何有n

個節(jié)點，n

1條邊的連通圖必是一棵樹

2.2圖的生成樹樹T是連通圖G的生成樹(spanningtree)，若T是G的子圖且包含圖G的所有的節(jié)點；包含圖G中部分指定節(jié)點的樹稱為steinertree第9頁,共56頁，2024年2月25日，星期天

2.3

最小生成樹有n個鄉(xiāng)村，各村間道路的長度是已知的，如何鋪設光纜線路使n個鄉(xiāng)村連通且總長度最短顯然，這要求在已知邊長度的網路圖中找最小生成樹

第10頁,共56頁，2024年2月25日，星期天2.4求解最小生成樹的破圈算法所謂的最小生成樹問題就是在一個賦權的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權數之和為最小。算法的具體步驟如下：在給定的賦權的連通圖上任找一個圈；在所找的圈中去掉一條權數最大的邊（如果有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條。如果所余下的圖中已不含圈，則計算結束，所余下的圖即為最小生成數，否則返回第1步。第11頁,共56頁，2024年2月25日，星期天應用舉例：某大學準備對其所屬的7個學院辦公室計算機聯網，這個網絡的可能連通的路徑如圖G所示，圖中v1,…,v7表示7個學院辦公室，圖中的邊為可能聯網的路徑，邊上所賦的權數為這條路線的長度，單位為百米。請設計一個網絡能連通7個學院辦公室，并使總的線路長度最短。v1v2v3v4v6v5v7103343278541G第12頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v7103343278541G1

1.

在G中找到一個圈（v1,v7,v6,v1），并知在此圈上邊[v1,v6]的權數10為最大，在G中去掉邊[v1,v6]得圖G1。第13頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v7334327541G2

2.

在G1中找到一個圈（v3,v4,v5,v7,v3），并知在此圈上邊[v4,v5]的權數8為最大，在G1中去掉邊[v4,v5]得圖G2。8第14頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v733432741G33.

在G2中找到一個圈（v2,v3,v5,v7,v2），并知在此圈上邊[v5,v7]的權數5為最大，在G2中去掉邊[v5,v7]得圖G3。5第15頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v733432741G44.

在G3中找到一個圈（v3,v5,v6,v7,v3），并知在此圈上邊[v5,v6]和[v3,v7]的權數4為最大，在G3中去掉邊[v5,v6]得圖G4。第16頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v73343271G55.

在G4中找到一個圈（v2,v3,v7,v2），并知在此圈上邊[v3,v7]的權數5為最大，在G2中去掉邊[v5,v7]得圖G3。第17頁,共56頁，2024年2月25日，星期天v1v2v3v4v6v5v7333271G56.在G5中已找不到任何一個圈了，可知G5即為圖G的最小生成樹。這個最小生成樹的所有邊的總權數為3+3+3+1+2+7=19。第18頁,共56頁，2024年2月25日，星期天§3最短路問題最短路問題是對一個賦權的有向圖G（權數可能是路程的長度、花費的成本等等）中的指定的兩個點Vs和Vt找到一條從Vs到Vt的路，使得這條路上所有弧的權數的總和最小，這條路被稱為從Vs到Vt的最短路，這條路上所有弧的權數的總和被稱之為從Vs到Vt的距離。第19頁,共56頁，2024年2月25日，星期天3.1求解最短路的Dijkstra算法（Dijkstraalgorithm,1959）

Dijkstra算法也稱為雙標號算法。所謂雙標號，也就是對圖中的點vj賦予兩個標號(lj,kj)，第一個標號lj表示從起點vs到vj的最短路的長度，第二個標號kj表示在vs到vj的最短路上vj前面一個鄰點的下標。給起點v1以標號(0,s)表示從v1到v1的距離為0，v1為起點。找出已標號的點的集合I，沒標號的點的集合J以及弧的集合{(vi,vj)|vi∈I,vj∈J}，這里這個弧的集合是指所有從已標號的點到未標號的點的弧的集合。如果上述弧的集合是空集，則計算結束。如果vt已標號(lt,kt)，則vs到vt的距離即為lt，而從vs到vt的最短路徑，則可以從kt反向追蹤到起點vs而得到。如果vt未標號，則可以斷言不存在從vs到vt的有向路。否則轉下一步。對上述弧的集合中的每一條弧，計算sij=li+cij在所有的sij中，找到其值為最小的弧，不妨設此弧為(vc,vd)，則給此弧的終點以雙標號(scd,c),返回第2步。第20頁,共56頁，2024年2月25日，星期天例1.求下圖中v1到v6的最短路。v1v4v3v2v5v62531255173第21頁,共56頁，2024年2月25日，星期天給起始點v1標以(0,s)，表示從v1到v1的距離為0。已標號點集I={v1}，未標號點集J={v2,v3,v4,v5,v6}，弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4)}，并有s12=l1+c12=0+3=3,s13=l1+c13=0+2=2,s14=l1+c14=0+5,min(s12,s13,s14)=s13=2.我們給弧(v1,v3)的終點v3標以(2,1).I={v1,v3},J={v2,v4,v5,v6},弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v4),(v3,v4)}且s34=l3+c34=2+1=3,min(s12,s14,s34)=s12=s34=3.給弧(v1,v2)的終點標以(3,1),弧(v3,v4)的終點標以(3,3).I={v1,v2,v3,v4},J={v5,v6},弧集{(vi,vj)|vi∈I,vj∈J}={(v2,v6),(v4,v6)},并有s26=l2+c26=3+7=10,s46=l4+c46=3+5=8,min(s26,s46)=s46=8.I={v1,v2,v3,v4,v6},J={v5},弧集為?，計算結束。v5沒有標號表明從v1到v5沒有有向路。最短路徑為v1?v3?v4?v6.第22頁,共56頁，2024年2月25日，星期天例1的各點的標號如下(v1到v5沒有有向路）v1v4v3v2v5v62531255173(0,s)(3,3)(8,4)(3,1)(2,1)第23頁,共56頁，2024年2月25日，星期天3.2最短路問題的應用例2.電信公司準備在甲、乙兩地沿路架設一條光纜線，問如何架設使其光纜線路最短？下圖給了甲、乙兩地間的交通圖，圖中的點v1,v2,...,v7表示7個地點，其中v1表示甲地，v7表示乙地，點之間的聯線（邊）表示兩地之間的公路，邊所賦的權數表示兩地間的公路長度。v1甲地v7乙地v3v4v6v2v51510173465642第24頁,共56頁，2024年2月25日，星期天起始點v1標號為(0,s).I={v1},J={v2,v3,v4,v5,v6,v7},邊集{[vi,vj]|vi,vj中一個∈I,另一個∈J}={[v1,v2],[v1,v3]}，且s12=l1+c12=0+15=15，s13=l1+c13=0+10=10，min(s12,s13)=s13=10，邊[v1,v3]中未標號點v3標以(10,1).I={v1,v3},J={v2,v4,v5,v6,v7},邊集{[vi,vj]}={[v1,v2],[v3,v2],[v3,v5]},且s32=l3+c32=10+3=13，s35=l3+c35=10+4=14，min(s12,s32,s35)=s32=13.邊[v3,v2]中未標號的點v2標以(13,3).I={v1,v3,v2},J={v4,v5,v6,v7},邊集{[vi,vj]}={[v3,v5],[v2,v4],[v2,v7]},且s24=l2+c24=13+6=19,s27=l2+c27=13+17=30,min(s35,s24,s27)=s35=14.邊[v3,v5]中未標號的點v5標以(14,3).I={v1,v2,v3,v5},J={v4,v6,v7},邊集{[vi,vj]}={[v2,v4],[v5,v4],[v2,v7],[v5,v6]},并有s54=l5+c54=14+4=18,s56=l5+c56=14+2=16,min(s24,s54,s27,s56)=s56=16.邊[v5,v6]中未標號的點v6標以(16,5).第25頁,共56頁，2024年2月25日，星期天I={v1,v2,v3,v5,v6},J={v4,v7}.邊集{[vi,vj]}={[v2,v4],[v2,v7],[v5,v4],[v6,v7]},且s67=l6+c67=16+6=22,min(s24,s27,s54,s67)=s54=18.邊[v5,v4]中未標號的點v4標以(18,5).I={v1,v2,v3,v4,v5,v6},J={v7}.邊集{[vi,vj]}={[v2,v7],[v4,v7],[v6,v7]},且s47=l4+c47=18+8=23,min(s27,s47,s67)=s67=22.邊[v6,v7]中未標號的點v7標以(22,6).此時I={v1,v2,v3,v4,v5,v6,v7},J=?.邊集合{[vi,vj]}為空集，計算結束。從v1到v7的最短距離為22,其最短路徑為v1?v3?v5?v6?v7.第26頁,共56頁，2024年2月25日，星期天例2的各點標號如下：v1甲地v7乙地v3v4v6v2v51510173465642(0,s)(18,5)(10,1)(16,5)(14,3)(13,3)(22,6)第27頁,共56頁，2024年2月25日，星期天例3.設備更新問題。某公司試用一臺設備，在每年年初，公司就要決定是購買新設備還是繼續(xù)使用舊設備。如果購置新設備，就要支付一定的購置費，當然新設備的維修費用就低。如果繼續(xù)使用舊設備，可以省去購置費，但維修費用就高了。現在需要我們制定一個五年之內的更新設備計劃，使得五年內購置費和維修總的支付費用最小。這種設備每年年初的價格以及使用不同時間的設備所需要的維修費如下表所示。年份12345年初價格1111121213使用年數0-11-22-33-44-5每年維修費用5681118第28頁,共56頁，2024年2月25日，星期天將該問題轉化成求最短路問題，vi表示“第i年年初購進一臺新設備”，對于弧(vi,vj)，它的權數定義為從第i年年初購進設備使用到第j-1年年底所花費的購置費及維修費的總和，計算結果如下：ji1234561—16223041592——162230413———1723314————17235—————186——————第29頁,共56頁，2024年2月25日，星期天v1v2v3v4v5v6161817171623312322304159413022第30頁,共56頁，2024年2月25日，星期天起始點v1標以(0,s).I={v1},J={v2,v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4),(v1,v5),(v1,v6)}并有s12=l1+c12=0+16=16,s13=l1+c13=0+22=22,s14=l1+c14=0+30=30,s15=l1+c15=0+41=41,s16=l1+c16=0+59=59,min(s12,s13,s14,s15,s16)=s12=16.給弧(v1,v2)的終點v2標以(16,1).I={v1,v2},J={v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v3),(v1,v4),(v1,v5),(v1,v6),(v2,v3),(v2,v4),(v2,v5),(v2,v6)}并有s23=l2+c23=16+16=32,s24=l2+c24=16+22=38,s25=l2+c25=16+30=46,s26=l2+c26=16+41=57,min(s13,s14,s15,s16,s23,s24,s25,s26)=s13=22.給弧(v1,v3)的終點v3標以(22,1).第31頁,共56頁，2024年2月25日，星期天I={v1,v2,v3},J={v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v4),(v1,v5),(v1,v6),(v2,v4),(v2,v5),(v2,v6),(v3,v4),(v3,v5),(v3,v6)}并有s34=l3+c34=22+17=39,s35=l3+c35=22+23=45,s36=l3+c36=22+31=53,min(s14,s15,s16,s24,s25,s26,s34,s35,s36)=s14=30.給弧(v1,v4)的終點v4標以(30,1).I={v1,v2,v3,v4},J={v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v5),(v1,v6),(v2,v5),(v2,v6),(v3,v5),(v3,v6),(v4,v5),(v4,v6)}并有s45=l4+c45=30+17=47,s46=l4+c46=30+23=53,min(s15,s16,s25,s26,s35,s36,s45,s46)=s15=41.給弧(v1,v5)的終點v5標以(41,1).I={v1,v2,v3,v4,v5},J={v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v6),(v2,v6),(v3,v6),(v4,v6),(v5,v6)}并有s56=l5+c56=41+18=59,min(s16,s26,s36,s46,s56)=s36=s46=53.給弧(v3,v6)和(v4,v6)的終點v6標以(53,3)和(53,4).第32頁,共56頁，2024年2月25日，星期天v1v2v3v4v5v6161817171623312322304159413022(0,s)(16,1)(30,1)(41,1)(53,4)(53,3)(22,1)第33頁,共56頁，2024年2月25日，星期天§4最大流問題最大流問題：給了一個帶收發(fā)點的網絡，其每條弧的賦權稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。第34頁,共56頁，2024年2月25日，星期天4.1最大流的數學模型例：某石油公司擁有一個管道網絡，使用這個網絡可以把石油從開采地運送到一些銷售點。由于管道的直徑的變化，他的各段管道(vi,vj)的流量cij也不一樣，如下圖所示。cij的單位為萬加侖/小時。如果使用這個網絡系統從開采地v1向銷地v7運送石油，問每小時能運送多少加侖石油？v1v6v3v4v5v2v761223236542第35頁,共56頁，2024年2月25日，星期天設弧(vi,vj)上的流量為fij，網絡上的總的流量為F，則上述問題的線性規(guī)劃模型為：目標函數：maxF=f12+f14約束條件：f12=f23+f25f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fijcij,(i=1,2,...,6;j=2,...,7)fij0,(i=1,2,...,6;j=2,...,7)第36頁,共56頁，2024年2月25日，星期天4.2最大流問題網絡圖論的解法對一條弧(vi,vj)的容量用一對數(cij,0)標在弧(vi,vj)上，cij表示從vi到vj容許通過的容量，0表示從vj到vi容許通過的容量。vivjvivjvivjcijvivj0cjicijcijcjicij第37頁,共56頁，2024年2月25日，星期天求最大流的基本算法找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于0。如果不存在這樣的路，則已求得最大流。找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網絡的流量pf。在這條路上，減少每一條弧的順流容量pf，同時增加這些弧的逆流容量pf，返回步驟①。注意：在步驟①中盡量選擇包含弧數最少的路。第38頁,共56頁，2024年2月25日，星期天引例的Ford-Fulkerson標號算法：(貝爾曼-福特算法)第一次迭代：選擇路為：v1v4v7.弧(v4,v7)的順流容量為2，決定了pf=2，改進的網絡流量如圖所示：v1v6v3v4v5v7612232365422000000000042020v2第39頁,共56頁，2024年2月25日，星期天第二次迭代：選擇路為：v1v2v5v7.弧(v2,v5)的順流容量為c25=3，決定了pf=3，改進的網絡流量如圖所示：v1v6v3v4v5v7612323542200000000420233230350v2第40頁,共56頁，2024年2月25日，星期天第三次迭代：選擇路為：v1v4v6v7.弧(v4,v6)的順流容量為c46=1，決定了pf=1，改進的網絡流量如圖所示：v1v6v3v4v5v7122342500000420233230363301310v2第41頁,共56頁，2024年2月25日，星期天第四次迭代：選擇路為：v1v4v3v6v7.弧(v3,v6)的順流容量為c36=2，決定了pf=2，改進的網絡流量如圖所示：v1v6v3v4v5v702234261000033023323038151321020v2第42頁,共56頁，2024年2月25日，星期天第五次迭代：選擇路為：v1v2v3v5v7.弧(v2,v3)的順流容量為c23=2，決定了pf=2，改進的網絡流量如圖所示：v1v6v3v4v5v7022110812032150233230310105022005v2第43頁,共56頁，2024年2月25日，星期天最大流如圖所示：v1v6v3v4v5v72101223252355v2第44頁,共56頁，2024年2月25日，星期天§5最小費用最大流問題最小費用最大流問題：給了一個帶收發(fā)點的網絡，對每一條弧(vi,vj),除了給出了容量cij外，還給出了這條弧的單位流量的費用bij，要求一個最大流F,并使總運送費用最小。第45頁,共56頁，2024年2月25日，星期天5.1最小費用最大流的數學模型例：在上例中，假設不同的單位流量的費用為bij，對每段管道(vi,vj)用(cij,bij)表示流量和費用，如圖所示。如果使用這個網絡系統從開采地v1向銷地v7運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最少？求出每小時的最大流量及相應的最小費用。v1v6v3v4v5v2v7(6,6)(6,3)(3,4)(2,3)(2,4)(1,3)(3,2)(2,8)(2,5)(4,4)(5,7)第46頁,共56頁，2024年2月25日，星期天設弧(vi,vj)上的流量為fij，網絡上的總的流量為F，則上述問題的線性規(guī)劃模型為：目標函數：minz=fij

bij=6f12+3f14+4f25+5f23+2f43+4f35+7f57+3f36+3f46+8f47+4f67約束條件：f12+f14=F=10f12=f23+f25f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fijcij,(i=1,2,...,6;j=2,...,7)fij0,(i=1,2,...,6;j=2,...,7)第47頁,共56頁，2024年2月25日，星期天5.2最小費用最大流問題網絡圖論的解法對一條弧(vi,vj)的容量用一對數(cij,0)標在弧(vi,vj)上，cij表示從vi到vj容許通過的容量，0表示從vj到vi容許通過的容量。vivjvivjvivj(cij,bij)(cij,bij)(0,-bij)(0,-bji)(0,-bij)(cji,bji)(cij,bij)vjvi(cji,bji)(cij,bij)第48頁,共56頁，2024年2月25日，星期天求最小費用最大流的基本算法找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于0。如果不存在這樣的路，則已求得最大流。找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網絡的流量pf。在這條路上，減少每一條弧的順流容量pf，同時增加這些弧的逆流容量pf，返回步驟①。注意：在步驟①中選擇一條從發(fā)點到收點的費用的最短路。第49頁,共56頁，2024年2月25日，星期天第一次迭代：選擇最短路為：v1v4v6v7，此路的總單位費用為3+3+4=10，弧(v4,v6)的順流容量為1，決定了pf=1，改進的網絡流量如圖所示：v1v6v3v4v5v2v7(6,6)(5,3)(3,4)(2,3)(2,4)(0,3)(3,2)(2,8)(2,5)(3,4)(5,7)第一次迭代后總流量為1，總的費用為10×1=10.(0,-3)(0,-4)(0,-5)(0,-2)(1,-3)(1,-3)(1,-4)(0,-7)(0,-4)(0,-6)(0,-8)1第50頁,共56頁，2024年2月25日，星期天第二次迭代：選擇最短路為：v1v4v7，此路的總單位費用為3+8=11，弧(v4,v7)的順流容量為2，決定了pf=2，改進的網絡流量如圖所示：