第4章 網絡規(guī)劃

第4章

網絡規(guī)劃

圖的基本概念

樹和最小支撐樹

最短路問題

網絡上的最大流問題本章內容重點第4章

網絡規(guī)劃§4.1

圖論導引§4.2最小支撐樹§4.3最短路問題§4.4網絡上的最大流問題§4.1

圖論導引

圖論已經廣泛應用于物理學、控制論、信息論、工程技術、交通運輸、經濟管理、電子計算機等各項領域。生產和生活中的許多問題，都可以用圖論的理論和方法來加以解決，例如：各種通信線路的架設，輸油管道的鋪設，鐵路或者公路交通網絡的合理布局，等?！?.1圖論導引1736年瑞士科學家歐拉發(fā)表第一篇圖論方面的論文，解決著名的哥尼斯堡七座橋問題：布勒格爾河流經哥尼斯堡，河中有兩個中心島，它們彼此以及河岸共有七座橋連接。能否無遺漏又不重復地走遍七座橋而又回到出發(fā)地？（圖4.1a）§4.1圖論導引圖4.1a§4.1圖論導引1736年歐拉把這個問題抽象成圖4.1b所示圖形的一筆畫問題，即能否從某一點開始不重復地一筆畫出這個圖形，最終回到原點。歐拉證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出。§4.1圖論導引圖4.1bACDB

例1

有六個公司存在債務關系，我們分別用點v1…v6表示這六個公司，它們之間的債務情況，可以用下圖4.3反映出來：如v1借債給v2，v2借債給v3，如此等等。§4.1圖論導引§4.1圖論導引v3v1v2v4v6v5圖4.3可以看出：用點表示研究對象，用點與點之間的線表示研究對象之間的特定關系；由點和線所構成的圖，能夠反映實際問題的相互關系。由于在一般情況下，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關系，顯得并不重要，因此，圖論中的圖與幾何圖，工程圖等本質上是不同的?！?.1圖論導引

圖是由點和點與點之間的線所組成的。通常，把點與點之間不帶箭頭的線叫做邊，帶箭頭的線叫做弧。如果一個圖是由點和邊所構成的，則稱為無向圖，記作G=(V，E)，其中V表示頂點集，E表示邊集。連接vi,vj

V的邊記作[vi,vj]，或者[vj,vi]。如果一個圖是由點和弧所構成的，則稱為有向圖，記作D=(V,A)，其中V表示頂點集，A表示弧集合。一條方向從vi指向vj的弧，記作(vi,vj)。§4.1圖論導引例2

圖4.4是一個無向圖G=（V，E）,其中V={v1,v2,v3,v4},E={e1,e2,e3,e4,e5,e6}§4.1圖論導引v4v3v2v1圖4.4e1e6e3e4e2e5例3

圖4.5是一個有向圖D=（V，A）,其中V={v1,v2,v3,v4,v5,v6,v7}A={(v1,v2),(v1,v3),(v3,v2),(v2,v4),(v2,v5)(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)}§4.1圖論導引v7v5v3v4v2v1v6圖4.5

下面介紹一些常用的名詞：如果邊[vi,vj]

E，則稱vi,vj是邊的端點，或者vi,vj是相鄰的。如果一條邊的兩個端點是相同的,則稱之為環(huán)，如圖4.4中的邊e5是環(huán)。如果兩個端點之間有兩條以上的邊，則稱它們?yōu)槎嘀剡叄鐖D4.4中的邊e2和e3。一個無環(huán)無多重邊的圖稱為簡單圖?！?.1圖論導引

設G1=[V1,E1],G2=[V2,E2]子圖：如果V2

V1,E2

E1

，稱

G2

是G1

的子圖；支撐子圖：如果V2

=V1,E2

E1

，稱G2

是G1

的支撐子圖.§4.1

圖論導引

§4.1圖論導引G16個點，9條邊G2：子圖§4.1圖論導引5個點，4條邊

§4.1圖論導引G3：支撐子圖6個點，5條邊鏈：由兩兩相鄰的點及相關聯(lián)的邊構成的點邊序列。如：v1,e1,v2,e2,v3,e3,v4,…,vn-1,en-1,vn

.

v1和vn分別為鏈的起點和終點。簡單鏈：鏈中所含的邊均不相同。初等鏈：鏈中所含的點均不相同?！?.1圖論導引圈：起點和終點相同的鏈。連通圖：圖中任意兩點之間均至少有一條鏈。樹：一個無圈的連通圖叫做樹?！?.1圖論導引§4.1圖論導引樹的性質：（1）樹的充分必要條件是任意兩個頂點之間有且僅有一條鏈。（2）在樹中的兩個不相鄰的點之間加上一條邊，那么恰好得到一個圈。（3）如果樹中點的個數(shù)為n，那么樹中邊的個數(shù)為n-1?！?.1圖論導引支撐樹6個點，5條邊有向圖?。篴=(u,v)A，起點u，終點v；路：若有從u到v（不考慮方向）鏈，且各方向一致，則稱之為從u到v的路；初等路：各頂點都不相同的路；初等回路：u=v的初等路;連通圖：若不考慮方向是無向連通圖;§4.1圖論導引Return§4.2最小支撐樹圖G=（V，E），對于G中的每一條邊[vi,vj]，相應地有一個數(shù)Wij，那么稱這樣的圖G為賦權圖，Wij稱為邊[vi,vj]的權。

這里的權，是具有廣義的數(shù)量值，例如：長度，費用、流量等。最小支撐樹問題是賦權圖的最優(yōu)化問題之一?！?.2最小支撐樹

在已知的幾個城市之間聯(lián)結電話線網或交通線網，要求總長度最短和總建設費用最少，可以歸結為最小支撐樹問題。

Kruskal算法

步驟1

把圖中所有的邊，按照每一條邊的權從小到大的次序排列起來，并選取最前面的一條邊，作為支撐樹的第一條邊，把它從排列中劃去?！?.2最小支撐樹

Kruskal算法

步驟2

如果排列中已經沒有邊，那么得到的支撐樹就是最小支撐樹，算法終止；否則，檢查排列中最前面的一條邊，轉步驟3?！?.2最小支撐樹

Kruskal算法步驟3

如果選取最前面的邊與已經有的支撐樹不會形成圈，就把它加到支撐樹中去，并把它從排列中劃去；否則，直接把它從排列中劃去，轉步驟2?！?.2最小支撐樹§4.2最小支撐樹v6v5v2v3v4v162453544v3v2v1v4v6v55131421，2，3，4，4，5，5，6，7已得到最小支撐樹，權=1+2+3+4+5=15.！一棵樹點的個數(shù)為n，邊的個數(shù)為n-1。如果再加一條邊，一定會產生圈。例4（續(xù)）兩個習題：§4.2最小支撐樹§4.2最小支撐樹v6v5v2v3v4v1v7v10v9v11v81212631110968991111512127最小支撐樹的權=751.求下圖最小支撐樹§4.2最小支撐樹v6v4v1v6v8v5v10v7251428187661312204167最小支撐樹的權=73v2v3v92.求下圖最小支撐樹§4.3最短路問題

最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，可以解決生產實際中的許多問題，比如：城市中的管道鋪設，線路安排，工廠布局，設備更新等等；也可以用于解決其它的最優(yōu)化問題。最短路問題——Dijkstra算法（1959年）

§4.3最短路問題Dijksta算法基本步驟（1）給發(fā)點vs標號(0,s)，表示從vs到終點vt的距離為0；（2）找出已標號的點的集合I、沒標號的點的集合J以及弧的集合{vi,vj|vi

I,vj

J}；§4.3最短路問題Dijksta算法基本步驟（3）如果上述弧的集合是空集，則算法結束。此時有兩種情況：如果vt已標號(lt,kt)，則從vs到vt的距離即為lt

，而從vs到vt的最短路，可以從vt反向追蹤到vs而得到。如果vt未標號，則不存在從vs到vt的（有向）路。如果上述弧的集合不是空集，轉到第（4）步；

§4.3最短路問題Dijksta算法基本步驟（4）對上述弧集合的每一條弧，計算sij=li+cij，找出sij值最小的弧，不妨設為(vc,vd)，給此弧的終點以雙標號(scd,c)，返回第（2）步。

§4.3最短路問題例5

下圖是單行線交通網，每個弧旁邊的數(shù)字表示這條單行線的長度?，F(xiàn)在有一個人要從v1出發(fā)，經過這個交通網到達v8，要尋求是總路程最短的線路。§4.3最短路問題8114219182421225V3V1V2V8V4V5V6V7例5（續(xù)）§4.3最短路問題8114219182421225V3V1(0,0)V2V8V4V5V6V71128解：§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2V8V4V5V6V71128解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2V8V4V5V6V7112876解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4V5V6V7112876解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4V5V6V711287615解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4V5V6(7,3)V711287615解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4V5V6(7,3)V71128761581115解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4(8,6)V5V6(7,3)V71128761581115解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4(8,6)V5V6(7,3)V7112876158112015解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4(8,6)V5V6(7,3)V7(11,6)112876158112015解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8V4(8,6)V5V6(7,3)V7(11,6)11287615811201315解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,4)V4(8,6)V5V6(7,3)V7(11,6)11287615811201315解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（續(xù)）§4.3最短路問題8114219182421225V3(2,1)V1(0,0)V2(6,3)V8(13,7)V4(8,6)V5V6(7,3)V7(11,6)解（續(xù)）§4.3最短路問題8114219182421225V3V1V2V8V4V5V6V7最短鏈問題解（續(xù)）§4.3最短路問題8114219182421225V3V2V8V4V5V6V7V1(0,0)解（續(xù)）§4.3最短路問題8114219182421225V3V2V8V4V5V6V7V1(0,0)8211解（續(xù)）§4.3最短路問題8114219182421225V2V8V4V5V6V7V1(0,0)8211V3(2,1)解（續(xù)）§4.3最短路問題8114219182421225V2V8V4V5V6V7V1(0,0)8211V3(2,1)674解（續(xù)）§4.3最短路問題8114219182421225V2V8V4(4,3)V5V6V7V1(0,0)8211V3(2,1)647解（續(xù)）§4.3最短路問題8114219182421225V2V8V4(4,3)V5V6V7V1(0,0)8211V3(2,1)674165解（續(xù)）§4.3最短路問題8114219182421225V2V8V4(4,3)V5V6(5,4)V7V1(0,0)8211V3(2,1)674165解（續(xù)）§4.3最短路問題8114219182421225V2V8V4(4,3)V5V6(5,4)V7V1(0,0)8211V3(2,1)6741657139解（續(xù)）4.3最短路問題8114219182421225V2(6,3)V8V4(4,3)V5V6(5,4)V7V1(0,0)8211V3(2,1)6741657139解（續(xù)）§4.3最短路問題8114219182421225V2(6,3)V8V4(4,3)V5V6(5,4)V7V1(0,0)8211V3(2,1)674165713915解（續(xù)）§4.3最短路問題8114219182421225V2(6,3)V8V4(4,3)V5(7,6)V6(5,4)V7V1(0,0)8211V3(2,1)674165713915解（續(xù)）§4.3最短路問題8114219182421225V2(6,3)V8V4(4,3)V5(7,6)V6(5,4)V7V1(0,0)8211V3(2,1)6741657139158解（續(xù)）§4.3最短路問題8114219182421225V2(6,3)V8(8,5)V4(4,3)V5(7,6)V6(5,4)V7V1(0,0)8211V3(2,1)6741657139158解（續(xù)）§4.3最短路問題8114219182421225V2(6,3)V8(8,5)V4(4,3)V5(7,6)V6(5,4)V7V1(0,0)V3(2,1)解（續(xù)）§4.3最短路問題思考題：從V1到V8的最短路的距離為什么不會比最短鏈的距離??？

Return§4.4網絡上的最大流問題

在許多實際的網絡系統(tǒng)中都存在著最大流問題,例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等等。最大流問題算法——Ford-Fulkerson算法（1956年）§4.4網絡上的最大流問題V6V3V2V5V1645126156735V4

上圖是聯(lián)結發(fā)點（起始地）v1和收點（目的地）v6的交通運輸網，每一條?。╲i,vi）旁邊的權cij表示這段運輸線的最大通過能力（容量），貨物經過交通岡從v1運送到v6.要求確定一個運輸方案，使得從v1到v6的貨運量最大，這個問題就是尋求網絡系統(tǒng)的最大流問題。例6§4.4網絡上的最大流問題V6V4V3V2V5V16,04,05,012,06,0515,06,07,03,01266V1V2V355,0371564V5V4V6流量|f|=0增量網絡解：§4.4網絡上的最大流問題V451266V1V2V35371564V5V6在增量網絡中找到從V1到V6的路:V1-V3-V4-V6,路的容量為6。解（續(xù)）§4.4網絡上的最大流問題V6V4V3V2V5V16,04,05,012,06,6515,66,07,63,01266V1V2V355,031964V5V4V6流量|f|=6增量網絡66解（續(xù)）§4.4網絡上的最大流問題V451266V1V2V3531964V5V666在增量網絡中找到從V1到V6的路:V1-V2-V4-V6,路的容量為5。解（續(xù)）§4.4網絡上的最大流問題V6V4V3V2V5V16,04,05,512,56,615,116,07,63,0766V1V2V355,031464V5V4V6流量|f|=11增量網絡61155解（續(xù)）§4.4網絡上的最大流問題V4766V1V2V3531464V5V661155在增量網絡中找到從V1到V6的路:V1-V2-V3-V4-V6,路的容量為1。解（續(xù)）§4.4網絡上的最大流問題V6V4V3V2V5V16,04,05,512,66,615,126,17,73,0665V1V2V355,03364V5V4V6流量|f|=12增量網絡712651解（續(xù)）§4.4網絡上的最大流問題V4666V1V2V353364V5V671265在增量網絡中不存在從V1到V6的路，已經是最大流！解（續(xù)）§4.4網絡上的最大流問題V6V3V2V5V100566121700V4最大流如下圖所示，最大流的流量|f|=12。解（續(xù)）例7

以下圖中給出的流作為初始流（流量|f|為12），求從發(fā)點V1到收點V6的最大流。V6V3V2V5V19,63,07,48,89,48,63,32,23,15,5V4§4.4網絡上的最大流問題V6V3V2V54V6V3V2V5V19,63,07,48,89,48,63,32,23,15,5V444166流量|f|=12增量網絡解：V6V3V2V5444166在增量網絡中找到從V1到V6的路，容量為3：

V1-V3-V2-V4-V5-V6.

§4.4網絡上的最大流問題解（續(xù)）V6V3V2V5V138223225V4V6V3V2V5V19,93,37,78,89,78,63,02,23,15,5V477169流量|f|=15增量網絡解（續(xù)）V6V3V2V5V138223225V477169在增量網絡中不存在從V1到V6的路，已達到最大流！§4.4網絡上的最大流問題解（續(xù)）§4.4網絡上的最大流問題最大流如下圖所示，最大流的流量|f|=15。V6V3V2V5V19378760215V4解（續(xù)）§4.4網絡上的最大流問題V8V5V2V7V154671232649V4例8

求V1到V8的最大流。V3V6538V8V5V2V7V154671232649V4V3V6538V8V5V2V7V15,04,06,07,012,03,02,06,04,09,0V4V3V65,03,08,0流量|f|=0增量網絡解：V8V5V2V7V154671232649V4V3V6538在增量網絡中找到從V1到V8的兩條路:V1-V2-V4-V8和V1-V5-V7-V8，總容量為4+5=9?！?.4網絡上的最大流問題解（續(xù)）V8V5V2V7V146373269V4V3V634V8V5V2V7V15,54,06,07,412,53,02,06,04,49,0V4V3V65,53,08,4流量|f|=9增量網絡444555解（續(xù)）V8V5V2V7V146373269V4V3V634444555在增量網絡中找V1到V8的兩條路:V1-V2-V3-V8和V1-V5-V6-V8，總容量為3+4=7。§4.4網絡上的最大流問題解（續(xù)）V8V5V2V7V133265V4V3V634V8V5V2V7V15,54,46,37,712,93,32,06,04,49,4V4V3V65,53,08,4流量|f|=16增量網絡7449553344解（續(xù)）V8V5V2V7V133265V4V3V6347449553344在增量網絡中找到從V1到V8的路，容量為2：

V1-V5-V6-V2-V3-V4-V8.§4.4網絡上的最大流問題解（續(xù)）V8V5V2V7V11143V4V3V632V8V5V2V7V15,54,46,57,712,113,32,26,24,49,6V4V3V65,53,08,6流量|f|=18增量網絡74611555346解（續(xù)）V8V5V2V7V11143V4V3V63274611555346在增量網絡中不存在從V1到V8的路（到V7點為止），已達到最大流?！?.4網絡上的最大流問題解（續(xù)）V8V5V2V7V154571132246V4V3V6506最大流如下圖所示，最大流的流量：|f|=18.§4.4網絡上的最大流問題解（續(xù)）例9

以下圖中給出的流作為初始流（流量|f|為3），求從發(fā)點V1到收點V5的最大流。V5V3V2V15,13,02,14,23,22,12,2V4§4.4網絡上的最大流問題V5V3V2V143112V41221211增量網絡§4.4網絡上的最大流問題解：V5V3V2V143112V41221