圖與網(wǎng)絡(luò)模型

圖與網(wǎng)絡(luò)模型第一頁，共一百一十頁，2022年，8月28日1引言

圖論是應(yīng)用非常廣泛的運(yùn)籌學(xué)分支，它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論，信息論，工程技術(shù)，交通運(yùn)輸，經(jīng)濟(jì)管理，電子計(jì)算機(jī)等各項(xiàng)領(lǐng)域。對(duì)于科學(xué)研究，市場和社會(huì)生活中的許多問題，可以同圖論的理論和方法來加以解決。例如，各種通信線路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問題，都可以應(yīng)用圖論的方法，簡便、快捷地加以解決。第二頁，共一百一十頁，2022年，8月28日2

隨著科學(xué)技術(shù)的進(jìn)步，特別是電子計(jì)算機(jī)技術(shù)的發(fā)展，圖論的理論獲得了更進(jìn)一步的發(fā)展，應(yīng)用更加廣泛。如果將復(fù)雜的工程系統(tǒng)和管理問題用圖的理論加以描述，可以解決許多工程項(xiàng)目和管理決策的最優(yōu)問題。因此，圖論越來越受到工程技術(shù)人員和經(jīng)營管理人員的重視。第三頁，共一百一十頁，2022年，8月28日3

1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問題。德國的哥尼斯堡城有一條普雷格爾河，河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接，如圖1a所示。第四頁，共一百一十頁，2022年，8月28日4AB圖1aCD第五頁，共一百一十頁，2022年，8月28日5

當(dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問題，一個(gè)漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。盡管試驗(yàn)者很多，但是都沒有成功。為了尋找答案，1736年歐拉將這個(gè)問題抽象成圖1b所示圖形的一筆畫問題。即能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)。歐拉在他的論文中證明了這是不可能的，因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個(gè)著名問題。第六頁，共一百一十頁，2022年，8月28日6圖1bACDB第七頁，共一百一十頁，2022年，8月28日7§1圖與網(wǎng)絡(luò)的基本概念

在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的示意圖。例1:圖8-1是我國北京、上海、重慶等十四個(gè)城市之間的鐵路交通圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。第八頁，共一百一十頁，2022年，8月28日8太原重慶武漢南京徐州連云港上海鄭州石家莊塘沽青島濟(jì)南天津北京圖11-1第九頁，共一百一十頁，2022年，8月28日9

例2:有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)v1…v6表示這六支球隊(duì)，它們之間的比賽情況，也可以用圖反映出來，已知v1隊(duì)?wèi)?zhàn)勝v2隊(duì)，v2隊(duì)?wèi)?zhàn)勝v3隊(duì)，v3隊(duì)?wèi)?zhàn)勝v5隊(duì)，如此等等。這個(gè)勝負(fù)情況，可以用圖8-2所示的有向圖反映出來。第十頁，共一百一十頁，2022年，8月28日10v3v1v2v4v6v5圖8-2第十一頁，共一百一十頁，2022年，8月28日11例3：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示，圖11-3就是一個(gè)表示這種關(guān)系的圖。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5圖8-3第十二頁，共一百一十頁，2022年，8月28日12

當(dāng)然圖論不僅僅是要描述對(duì)象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的，如對(duì)趙等七人的相互認(rèn)識(shí)關(guān)系我們也可以用圖8-4來表示。(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5圖8-4第十三頁，共一百一十頁，2022年，8月28日13

從以上的幾個(gè)例子可以看出，我們用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖，反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。一般來說，通常用點(diǎn)表示研究對(duì)象用點(diǎn)與點(diǎn)之間的線表示研究對(duì)象之間的特定關(guān)系。由于在一般情況下，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線的長短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。第十四頁，共一百一十頁，2022年，8月28日14a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳圖11-5如果我們把上面例子中的“相互認(rèn)識(shí)”關(guān)系改為“認(rèn)識(shí)”的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧。圖11-5就是一個(gè)反映這七人“認(rèn)識(shí)”關(guān)系的圖。相互認(rèn)識(shí)用兩條反向的弧表示。第十五頁，共一百一十頁，2022年，8月28日15

§1圖與網(wǎng)絡(luò)的基本概念無向圖：由點(diǎn)和邊構(gòu)成的圖，記作G=（V，E）。有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D=（V，A）。第十六頁，共一百一十頁，2022年，8月28日16次（度）：與頂點(diǎn)關(guān)聯(lián)的邊數(shù)。簡單圖：沒有環(huán)和重邊的圖。懸掛點(diǎn)：次為1的點(diǎn)。懸掛邊：次為1的邊。孤立點(diǎn)：次為0的點(diǎn)。(e8)=(v4，v4),稱為自回路(環(huán))；v6是孤立點(diǎn)，v5為懸掛點(diǎn)，e7為懸掛邊，頂點(diǎn)v3的次為4，頂點(diǎn)v2的次為3。第十七頁，共一百一十頁，2022年，8月28日17定理1：在一個(gè)圖中，所有頂點(diǎn)次的和等于邊的兩倍。定理2：在任意一個(gè)圖中，奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)。第十八頁，共一百一十頁，2022年，8月28日18圈（Circuit）封閉的鏈稱為圈如：μ={(1,2),(2,4),(4,3),(3,1}

鏈:由圖G中的某些點(diǎn)與邊相間構(gòu)成的序列{V1,e1,V2,e2,……,Vk,ek},若滿足ei=[Vi,Vi],則稱此點(diǎn)邊序列為G中的一條鏈。如：μ={(1,2),(3,2),(3,4)}4231第十九頁，共一百一十頁，2022年，8月28日19回路：若路的第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則該路為回路。賦權(quán)圖：對(duì)一個(gè)無向圖G的每一條邊(vi,vj)，相應(yīng)地有一個(gè)數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。網(wǎng)絡(luò)：

在賦權(quán)的圖D中指定一點(diǎn)，稱為發(fā)點(diǎn)，指定另一點(diǎn)稱為收點(diǎn)，其它點(diǎn)稱為中間點(diǎn)，并把D中的每一條弧的賦權(quán)數(shù)稱為弧的容量，D就稱為網(wǎng)絡(luò)。第二十頁，共一百一十頁，2022年，8月28日20連通圖：對(duì)無向圖G，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則G為連通圖。第二十一頁，共一百一十頁，2022年，8月28日21二、圖的矩陣表示

圖非常直觀，但是不容易計(jì)算，特別不容易在計(jì)算機(jī)上進(jìn)行計(jì)算，一個(gè)有效的解決辦法是將圖表示成矩陣形式，通常采用的矩陣是鄰接矩陣、邊長鄰接矩陣、弧長矩陣和關(guān)聯(lián)矩陣。第二十二頁，共一百一十頁，2022年，8月28日221鄰接矩陣

鄰接矩陣A表示圖G的頂點(diǎn)之間的鄰接關(guān)系，它是一個(gè)n×n的矩陣，如果兩個(gè)頂點(diǎn)之間有邊相聯(lián)時(shí)，記為1，否則為0。第二十三頁，共一百一十頁，2022年，8月28日23v1v2v3v4第二十四頁，共一百一十頁，2022年，8月28日24

v1v2v3v4v10111v21110v31101v41010無向圖的鄰接矩陣是對(duì)稱矩陣。v1v2v3v4第二十五頁，共一百一十頁，2022年，8月28日25v1v5v4v3v2也可以對(duì)有向圖第二十六頁，共一百一十頁，2022年，8月28日26

v1v2v3v4v5v100011v210010v301100v401101v510010第二十七頁，共一百一十頁，2022年，8月28日27二、邊長矩陣

在圖的各邊上一個(gè)數(shù)量指標(biāo)，具體表示這條邊的權(quán)（距離，單價(jià)，通過能力等）——賦權(quán)圖或網(wǎng)絡(luò)。以邊長代替鄰接矩陣中的元素得到邊長矩陣。第二十八頁，共一百一十頁，2022年，8月28日28v1v2v3v4256434第二十九頁，共一百一十頁，2022年，8月28日29

v1v2v3v4v10256v22430v35304v46040第三十頁，共一百一十頁，2022年，8月28日303弧長矩陣對(duì)有向圖的弧可以用弧長矩陣來表示。其中0表示兩點(diǎn)之間沒有弧連接。第三十一頁，共一百一十頁，2022年，8月28日31v1v5v4v3v2142322612第三十二頁，共一百一十頁，2022年，8月28日32

v1v2v3v4v5v1010

02v200204v302010

v403206v50

0

0

00第三十三頁，共一百一十頁，2022年，8月28日33§2最短路問題最短路問題：對(duì)一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)Vs和Vt找到一條從Vs

到Vt

的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。第三十四頁，共一百一十頁，2022年，8月28日34最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問題。第三十五頁，共一百一十頁，2022年，8月28日35一、求解最短路的Dijkstra算法(雙標(biāo)號(hào)法）步驟：1.給出點(diǎn)V1以標(biāo)號(hào)(0,s)2.找出已標(biāo)號(hào)的點(diǎn)的集合I，沒標(biāo)號(hào)的點(diǎn)的集合J以及弧的集合3.如果上述弧的集合是空集，則計(jì)算結(jié)束。如果vt已標(biāo)號(hào)（lt,kt），則vs到vt的距離為lt，而從vs到vt的最短路徑，則可以從kt

反向追蹤到起點(diǎn)vs

而得到。如果vt

未標(biāo)號(hào)，則可以斷言不存在從vs到vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。4.對(duì)上述弧的集合中的每一條弧，計(jì)算sij=li+cij

。在所有的sij中，找到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號(hào)（scd,Vc）,返回步驟2。第三十六頁，共一百一十頁，2022年，8月28日36例：求v1至v8的最短路。v2v3v7v1v8v4v5v66134105275934682第三十七頁，共一百一十頁，2022年，8月28日37(1)v1:[0,v1]計(jì)算min{0+2,0+1,0+3}=min{2,1,3}=1v4:[1.v1]v2v3v7v1v8v4v5v66134105275934682[1,v1][0,v1](2)I={v1}檢查?。╲1,v2),(v1,v4),(v1,v6)第三十八頁，共一百一十頁，2022年，8月28日38v2v3v7v1v8v4v5v66134105275934682(3)I={v1,v4}計(jì)算min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2v2:[2,v1][0,v1][1,v1][2,v1]考慮?。╲1,v2),(v1,v6),(v4,v2),(v4,v7)第三十九頁，共一百一十頁，2022年，8月28日39v2v3v7v1v8v4v5v66134105275934682（4）I={v1,v2,v4}

計(jì)算min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3v6:[3,v1][2,v1][1,v1][0,v1][3,v1]考慮?。╲1,v6),(v2,v3),(v2,v5),(v4,v7)第四十頁，共一百一十頁，2022年，8月28日40v2v3v7v1v8v4v5v66134105275934682(5)I={V1,V2,V4,V6}計(jì)算min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3v7:[3,v4][2，V1][1，V1][0，V1][3，V1][3,v4]考慮弧(v2,v3),(v2,v5),(v4,v7),(v6,v7)第四十一頁，共一百一十頁，2022年，8月28日41V2V3V7V1V8V4V5V66134105275934682(6)I={V1,V2,V4,V6,V7}計(jì)算min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6v5:[6,v7][2,v1][1,v1][0,v1][3,v1][3,v4][6,v7]考慮弧(v2,v3),(v2,v5),(v7,v5),(v7,v8)第四十二頁，共一百一十頁，2022年，8月28日42v2v3v7v1v8v4v5v66134105275934682(7)I={V1,V2,V4,V6,V7}計(jì)算min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8v3:[8,v2][2,V1][1,V1][0,V1][3,V1][3,V4][6,V7][8,v2]考慮弧(v2,v3),(v5,v3),(v5,v8),(v7,v8)第四十三頁，共一百一十頁，2022年，8月28日43v2v3v7v1v8v4v5v66134105275934682(8)I={v1,v2,v3,v4,v6,v7}

計(jì)算min{8+6,6+4,3+7}=min{14,10,11}=10v8:[10,v5][2,v1][1,v1][0,v1][3,v1][3,v4][6,v7][8,v2][10,v5]考慮?。╲3,v8),(v5,v8),(v7,v8)第四十四頁，共一百一十頁，2022年，8月28日44v2v3v7v1v8v4v5v66134105275934682(9)I={v1,v2,v3,v4,v6,v7,v8}v1到v8的最短路徑為v1—v4—v7—v5—v8，最短路長度為10。[2,v1][1,v1][0,v1][3,v1][3,v4][6,v7][8,v2][10,v5]反向追蹤：v8-v5-v7-v4-v1第四十五頁，共一百一十頁，2022年，8月28日45

例2求下圖中v1到v6的最短路v23527531512v1v6v5v3v4第四十六頁，共一百一十頁，2022年，8月28日46解：采用Dijkstra算法，可解得最短路徑為v1v3v4v6

各點(diǎn)的標(biāo)號(hào)圖如下：(3,1)v23527531512

V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4第四十七頁，共一百一十頁，2022年，8月28日47

例3電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。

V1（甲地）15176244431065v2V7（乙地）v3v4v5v6第四十八頁，共一百一十頁，2022年，8月28日48解：這是一個(gè)求無向圖的最短路的問題?？梢园褵o向圖的每一邊（vi,vj）都用方向相反的兩條?。╲i,vj）和（vj,vi）代替，就化為有向圖，即可用Dijkstra算法來求解。也可直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的弧的集合改成已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的邊的集合即可。第四十九頁，共一百一十頁，2022年，8月28日49最終解得：最短路徑v1v3v5v6v7，每點(diǎn)的標(biāo)號(hào)見下圖（0,s）

V1（甲地）1517624431065(13,3)v2

(22,6)V7（乙地）V5(14,3)V6(16,5)

V3(10,1)

V4(18,5)第五十頁，共一百一十頁，2022年，8月28日50

例4:設(shè)備更新問題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。第五十一頁，共一百一十頁，2022年，8月28日51年份12345年初價(jià)格1111121213使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用5681118已知：設(shè)備每年年初的價(jià)格表維修價(jià)格表：第五十二頁，共一百一十頁，2022年，8月28日52例4的解：將問題轉(zhuǎn)化為最短路問題，如下圖：用vi表示“第i年年初購進(jìn)一臺(tái)新設(shè)備”,?。╲i,vj）表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6第五十三頁，共一百一十頁，2022年，8月28日53123456116223041592162230413172331417235186所有弧的權(quán)數(shù)計(jì)算如下表：第五十四頁，共一百一十頁，2022年，8月28日54

(繼上頁)把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。

v1v2v3v4v5v6162230415916223041312317181723第五十五頁，共一百一十頁，2022年，8月28日55最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條：

v1v3v6和v1v4v6

V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723

V2（16,1）16(30,1)(53,3)(53,4)第五十六頁，共一百一十頁，2022年，8月28日56例：某交通網(wǎng)絡(luò)如下圖，求v1到v8的最短路線v1v2v4v5v6v7v86312216104310446練習(xí)：求最短路第五十七頁，共一百一十頁，2022年，8月28日57樹是圖論中的重要概念，所謂樹就是一個(gè)無圈的連通圖。

圖8-11中，(a)就是一個(gè)樹，而(b)因?yàn)閳D中有圈所以就不是樹，(c)因?yàn)椴贿B通所以也不是樹。圖8-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)8.3最小生成樹問題第五十八頁，共一百一十頁，2022年，8月28日58

給了一個(gè)無向圖G=(V,E)，我們保留G的所有點(diǎn)，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在圖8-12中，(b)和(c)都是(a)的生成子圖。如果圖G的一個(gè)生成子圖還是一個(gè)樹，則稱這個(gè)生成子圖為生成樹，在圖8-12中，(c)就是(a)的生成樹。最小生成樹問題就是指在一個(gè)賦權(quán)的連通的無向圖G中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。圖8-12(a)(b)(c)第五十九頁，共一百一十頁，2022年，8月28日59樹的性質(zhì)243512435124351如果樹T有m個(gè)結(jié)點(diǎn)，則邊的個(gè)數(shù)為m-1。

樹中任意兩個(gè)節(jié)點(diǎn)間有且只有一條鏈。

在樹中任意去掉一條邊，則不連通。第六十頁，共一百一十頁，2022年，8月28日60定理圖G有生成樹的充分必要條件為圖是連通圖。定義（最優(yōu)樹）在賦權(quán)圖G中，一棵生成樹所有樹枝上權(quán)的和，稱為生成樹的權(quán)。具有最小權(quán)的生成樹，稱為最優(yōu)樹（或最小樹）。求最小樹的方法有破圈法和避圈法。第六十一頁，共一百一十頁，2022年，8月28日61一求解最小支撐樹問題的破圈法方法：去邊破圈的過程。步驟：1）在給定的賦權(quán)的連通圖上任找一個(gè)圈。

2）在所找的圈中去掉一條權(quán)數(shù)最大的邊。

3）若所余下的圖已不含圈，則計(jì)算結(jié)束，余下的圖即為最小支撐樹，否則返回1）。第六十二頁，共一百一十頁，2022年，8月28日62423142314231生成樹2生成樹3生成樹1////例：用破圈法求右圖的最小支撐樹。4231

74581總權(quán)數(shù)=3+4+1=8第六十三頁，共一百一十頁，2022年，8月28日63二求解最小支撐樹的避圈法方法：選邊的過程。步驟：1）從網(wǎng)絡(luò)中任意選一點(diǎn)vi，找出與vi相關(guān)聯(lián)的權(quán)最小的邊[vi,vj]，得第二個(gè)頂點(diǎn)vj。

2）把頂點(diǎn)集V分為互補(bǔ)得兩部分A,ā，其中：

A：與已選邊相關(guān)聯(lián)得點(diǎn)集

ā

：不與已選邊相關(guān)聯(lián)得點(diǎn)集第六十四頁，共一百一十頁，2022年，8月28日64

3)考慮所有這樣的邊[vi,vj]，其中vi∈A,vj∈ā,挑選其中權(quán)最小的。

4）重復(fù)3），直至全部頂點(diǎn)均屬于A即可。V4V2V3V1

74581例：用避圈法求由圖的最小支撐樹。第六十五頁，共一百一十頁，2022年，8月28日65①任選點(diǎn)v1，挑與之相關(guān)聯(lián)的權(quán)最小的邊（v1,v4）.②A={v1,v4},ā={v3,v2}

從邊（v1,v3）,（v1,v2）,（v2,v4）,（v4,v3）中選權(quán)最小的邊（v1,v2）。V4V2V3V1

74581③A={v1,v2,v4},ā={v3}

從邊（v1,v3）,（v2,v3）,（v3,v8）中選權(quán)最小的邊（v2,v3）。④A={v1,v2,v3，

v4}第六十六頁，共一百一十頁，2022年，8月28日66

例5、某大學(xué)準(zhǔn)備對(duì)其所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中v1,…,v7

表示7個(gè)學(xué)院辦公室，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通7個(gè)學(xué)院辦公室，并使總的線路長度為最短。

v1331728541034v7v6v5v4v2v3圖8-14第六十七頁，共一百一十頁，2022年，8月28日67解：此問題實(shí)際上是求圖8-14的最小生成樹，這在例4中已經(jīng)求得，也即按照?qǐng)D8-13的(f)設(shè)計(jì)，可使此網(wǎng)絡(luò)的總的線路長度為最短，為19百米?！肮芾磉\(yùn)籌學(xué)軟件”有專門的子程序可以解決最小生成樹問題。第六十八頁，共一百一十頁，2022年，8月28日68v1v7v4v3v2v5v620159162532817412336練習(xí)用破圈法或者避圈法求最小生成樹

第六十九頁，共一百一十頁，2022年，8月28日69v1v7v4v3v2v5v693174123總造價(jià)=1+4+9+3+17+23=57第七十頁，共一百一十頁，2022年，8月28日70§4最大流問題最大流問題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。第七十一頁，共一百一十頁，2022年，8月28日71一、最大流的數(shù)學(xué)模型例6某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬加侖/小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運(yùn)送石油，問每小時(shí)能運(yùn)送多少加侖石油？63522241263v1v2v7v4v3v6圖8-26v5第七十二頁，共一百一十頁，2022年，8月28日72

我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，則有：第七十三頁，共一百一十頁，2022年，8月28日73

在這個(gè)線性規(guī)劃模型中，其約束條件中的前6個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。其后面幾個(gè)約束條件表示對(duì)每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應(yīng)小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流{fij}稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。

第七十四頁，共一百一十頁，2022年，8月28日74二、最大流問題網(wǎng)絡(luò)圖論的解法

對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖:(a)和(b)、(c)和(d)的意義相同。

vivjvivjcij0（a）（b）

cijcijvivj（cji）（c）vivj

cij

cji（d）第七十五頁，共一百一十頁，2022年，8月28日75用以上方法對(duì)例6的圖的容量標(biāo)號(hào)作改進(jìn)，得下圖63522241263v1v2v5v7v4v3v600000000000第七十六頁，共一百一十頁，2022年，8月28日76

求最大流的基本算法（1）找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。（2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。（3）在這條路上，減少每一條弧的順流容量pf

，同時(shí)增加這些弧的逆流容量pf，返回步驟（1）。

第七十七頁，共一百一十頁，2022年，8月28日77用此方法對(duì)例6求解：第一次迭代：選擇路為v1v4v7

。?。╲4,

v7

）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：第七十八頁，共一百一十頁，2022年，8月28日7863522241263v1v2v5v7v4v3v6000000000004202第七十九頁，共一百一十頁，2022年，8月28日79

第二次迭代：選擇路為v1v2v5v7

?；。╲2,

v5

）的順流容量為3，決定了pf=3，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：

635222413v1v2v5v7v4v3v60000000042022033303第八十頁，共一百一十頁，2022年，8月28日80第三次迭代：選擇路為v1v4v6v7

?；。╲4,

v6

）的順流容量為1，決定了pf=1，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：222413v1v2v5v7v4v3v600100042022033333013第八十一頁，共一百一十頁，2022年，8月28日81

第四次迭代：選擇路為v1v4v3v6v7

?；。╲3,

v6

）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：

22243v1v2v5v7v4v3v61100012032033350312002333第八十二頁，共一百一十頁，2022年，8月28日82第五次迭代：選擇路為v1v2v3v5v7

。?。╲2,

v3

）的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如下圖：22v1v2v5v7v4v3v61012020333501202333150020205第八十三頁，共一百一十頁，2022年，8月28日83

經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)的一條路，路上的每一條弧順流容量都大于零，運(yùn)算停止。得到最大流量為10。最大流量圖如下圖：22v1v2v5v7v4v3v6123522355第八十四頁，共一百一十頁，2022年，8月28日84練習(xí)：求從發(fā)點(diǎn)V1到收點(diǎn)V7的最大流。弧的流量放在括號(hào)內(nèi)。如圖.V=20v1v2v34v5v6v786314383410764第八十五頁，共一百一十頁，2022年，8月28日85§5最小費(fèi)用最大流問題最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條?。╲i,vj），除了給出容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個(gè)最大流F，并使得總運(yùn)送費(fèi)用最小。第八十六頁，共一百一十頁，2022年，8月28日86一、最小費(fèi)用最大流的數(shù)學(xué)模型例7由于輸油管道的長短不一，所以在例6中每段管道（vi,vj

）除了有不同的流量限制cij外，還有不同的單位流量的費(fèi)用bij

，cij的單位為萬加侖/小時(shí)，bij的單位為百元/萬加侖。如圖。從采地v1向銷地v7運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最小？求出最大流量和最小費(fèi)用。第八十七頁，共一百一十頁，2022年，8月28日87v7(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v4v3v6(6,3)v5（Cij，Bij）第八十八頁，共一百一十頁，2022年，8月28日88

這個(gè)最小費(fèi)用最大流問題也是一個(gè)線性規(guī)劃的問題。解：我們用線性規(guī)劃來求解此題，可以分兩步走。第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例6中建立了線性規(guī)劃的模型，通過管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。

第八十九頁，共一百一十頁，2022年，8月28日89第二步，在最大流量F的所有解中，找出一個(gè)最小費(fèi)用的解，我們來建立第二步中的線性規(guī)劃模型如下：仍然設(shè)弧（vi,vj）上的流量為fij，這時(shí)已知網(wǎng)絡(luò)中最大流量為F，只要在例6的約束條件上，再加上總流量必須等于F的約束條件：f12+f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用。

由此得到線性規(guī)劃模型如下：第九十頁，共一百一十頁，2022年，8月28日90

第九十一頁，共一百一十頁，2022年，8月28日91

用管理運(yùn)籌學(xué)軟件，可求得如下結(jié)果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最優(yōu)值(最小費(fèi)用)=145。第九十二頁，共一百一十頁，2022年，8月28日92如果我們把例7的問題改為：每小時(shí)運(yùn)送6萬加侖的石油從采地v1到銷地v7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個(gè)最小費(fèi)用流的問題。

第九十三頁，共一百一十頁，2022年，8月28日93一般來說，所謂最小費(fèi)用流的問題就是：在給定了收點(diǎn)和發(fā)點(diǎn)并對(duì)每條弧(vi,vj)賦權(quán)以容量cij及單位費(fèi)用bij的網(wǎng)絡(luò)中，求一個(gè)給定值f的流量的最小費(fèi)用，這個(gè)給定值f的流量應(yīng)小于等于最大流量F，否則無解。第九十四頁，共一百一十頁，2022年，8月28日94求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量F改為f即可。在例6中只要把f12+f14=F改為f12+f14=f=6得到了最小費(fèi)用流的線性規(guī)劃的模型了。第九十五頁，共一百一十頁，2022年，8月28日95二、最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法對(duì)網(wǎng)絡(luò)上?。╲i,vj）的（cij,bij）的表示作如下改動(dòng)，用(b)來表示(a)。vivj（cij,bij）（0,-bji

）（b）（a）vivj（cij,bij）（cij,bij）vivj（cji,bji）（cij,bij）vivj（cji,bji）（0,-bji)（0,-bji)（c）（d）第九十六頁，共一百一十頁，2022年，8月28日96用上述方法對(duì)例7中的圖形進(jìn)行改進(jìn)，得圖如下(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖8-28第九十七頁，共一百一十頁，2022年，8月28日97

求最小費(fèi)用最大流的基本算法在對(duì)弧的標(biāo)號(hào)作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基本算法與求最大流的基本算法完全一樣，不同的只是在步驟（1）中要選擇一條總的單位費(fèi)用最小的路，而不是包含邊數(shù)最小的路。第九十八頁，共一百一十頁，2022年，8月28日98用上述方法對(duì)例7求解：第一次迭代：找到最短路v1v4v6v7。第一次迭代后總流量為1，總費(fèi)用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖8-29第九十九頁，共一百一十頁，2022年，8月28日99第二次迭代：找到最短路v1v4v7。第二次迭代后總流量為3，總費(fèi)用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）