第四章圖與網(wǎng)絡(luò)

第四章圖與網(wǎng)絡(luò)第一頁(yè)，共五十五頁(yè)，編輯于2023年，星期五圖和網(wǎng)絡(luò)圖論廣泛地應(yīng)用與物理學(xué)、化學(xué)、控制論、信息、科學(xué)管理、電子計(jì)算機(jī)等領(lǐng)域。很多實(shí)際問題可以采用圖論的理論和方法來解決。圖論的歷史最早可以追溯到1736年瑞士數(shù)學(xué)家E.Euler解決著名的哥尼斯堡七橋問題。第二頁(yè)，共五十五頁(yè)，編輯于2023年，星期五哥尼斯堡七橋問題18世紀(jì)在哥尼斯堡城(今俄羅斯加里寧格勒)的普萊格爾河上有7座橋，將河中的兩個(gè)島和河岸連結(jié)，如圖1所示。城中的居民經(jīng)常沿河過橋散步，于是提出了一個(gè)問題：能否一次走遍7座橋，而每座橋只許通過一次，最后仍回到起始地點(diǎn)。這就是七橋問題，一個(gè)著名的圖論問題。第三頁(yè)，共五十五頁(yè)，編輯于2023年，星期五哥尼斯堡七橋問題第四頁(yè)，共五十五頁(yè)，編輯于2023年，星期五圖與網(wǎng)絡(luò)的基本概念V1V2V3de2e3e6e4e5V4V5e1V={v1,v2,v3,v4,v5}E={e1,e2,e3,e4,e5}G=(V,E)端點(diǎn)；關(guān)聯(lián)邊無向邊；有向邊（?。┉h(huán)（自回路）多重邊簡(jiǎn)單圖；多重圖懸掛點(diǎn)網(wǎng)絡(luò)第五頁(yè)，共五十五頁(yè)，編輯于2023年，星期五連通圖點(diǎn)邊序列；點(diǎn)邊交替序列；在點(diǎn)邊交替系列中，順序排列的任意兩條邊均為相鄰邊，則稱該點(diǎn)邊交替序列為鏈；點(diǎn)邊列中沒有重復(fù)的點(diǎn)和重復(fù)邊者稱為初等鏈圈（回路）V1V2V3V4V5V6e1e2e3e4e5e6e7e8e9e10第六頁(yè)，共五十五頁(yè)，編輯于2023年，星期五鏈、路(1)第七頁(yè)，共五十五頁(yè)，編輯于2023年，星期五鏈、路(2)v1a1v2a2v3a7v4v5a4a3a8a9路：在一條鏈中，每條弧的方向與序列的走向一致，則稱該鏈為路?；芈罚浩瘘c(diǎn)和終點(diǎn)重合與同一節(jié)點(diǎn)的路?；芈放c圈的區(qū)別是所有弧的方向一致。第八頁(yè)，共五十五頁(yè)，編輯于2023年，星期五圖、子圖、支撐子圖第九頁(yè)，共五十五頁(yè)，編輯于2023年，星期五樹一個(gè)無圈的連通圖稱為樹。第十頁(yè)，共五十五頁(yè)，編輯于2023年，星期五樹例：五個(gè)城市之間架設(shè)電話線。要求任何兩個(gè)城市都可以相互通話（允許通過其他城市），并且電話線的根數(shù)最少。V2V1V3V4V5第十一頁(yè)，共五十五頁(yè)，編輯于2023年，星期五圖的基本概念小結(jié)邊、弧無向圖、有向圖無向圖:(1)端點(diǎn)、相鄰、關(guān)聯(lián)邊 (2)環(huán)、多重邊、簡(jiǎn)單圖(3)懸掛點(diǎn)(4)鏈、圈、初等鏈(5)連通圖、支撐子圖有向圖:(1)始點(diǎn)、終點(diǎn)(2)路、回路第十二頁(yè)，共五十五頁(yè)，編輯于2023年，星期五割集v2v1v3v4v5v6abcdefghkv1v2v6v3v4v5在一個(gè)連通圖中割集是一些邊的集合，從G中移去這些邊，則G不連通，并且不存在這些邊的真子集使圖不連通第十三頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路問題設(shè)G=(V,E)為連通圖，圖中各邊(vi,vj)有權(quán)

lij(lij=∞表示vi,vj之間無邊)，vs,vt為圖中任意兩點(diǎn)，求一條路μ，使它是從vs到vt的所有路中總權(quán)數(shù)最小的路。第十四頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路問題123434563234221第十五頁(yè)，共五十五頁(yè)，編輯于2023年，星期五EdsgerWybeDijkstra中文名：艾茲格·迪科斯徹家鄉(xiāng)：荷蘭出生年月：1930年5月11日去世年月：2002年8月6日成就：1972年獲得過素有計(jì)算機(jī)科學(xué)界的諾貝爾獎(jiǎng)之稱的圖靈獎(jiǎng)1989年ACMSIGCSE計(jì)算機(jī)科學(xué)教育教學(xué)杰出貢獻(xiàn)獎(jiǎng)2002年ACMPODC最具影響力論文獎(jiǎng)第十六頁(yè)，共五十五頁(yè)，編輯于2023年，星期五D氏標(biāo)號(hào)法思路：從始點(diǎn)出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。條件：網(wǎng)絡(luò)中所有的弧權(quán)為非負(fù)。第十七頁(yè)，共五十五頁(yè)，編輯于2023年，星期五開始給發(fā)點(diǎn)標(biāo)上P(Vs)=0,其余節(jié)點(diǎn)標(biāo)上臨時(shí)標(biāo)號(hào)T(Vj)=∞，j≠1;設(shè)節(jié)點(diǎn)Vi是剛得到的P類標(biāo)號(hào)，把與節(jié)點(diǎn)Vi有弧直接相連而又屬于T類標(biāo)號(hào)的各節(jié)點(diǎn)Vj的標(biāo)號(hào)改為：

T(Vj)=min{T(Vj),P(Vj)+dij}在T類標(biāo)號(hào)中選標(biāo)號(hào)最小的節(jié)點(diǎn)Vj0，并把它的臨時(shí)標(biāo)號(hào)T(Vj0)改為P(Vj0)，若終點(diǎn)獲得P類標(biāo)號(hào)，則停止，否則轉(zhuǎn)上一步。D氏標(biāo)號(hào)法步驟第十八頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路問題???????v1v2v7v5v4171344452572v3v6第十九頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求解圖中()內(nèi)的數(shù)表示P標(biāo)號(hào)，[]內(nèi)的數(shù)表示T標(biāo)號(hào)。???????v1(0)v2v7v5v411344452572v3[∞]v6[∞][∞][∞][∞][∞]7

(1)首先給v1以P標(biāo)號(hào),P(v1)=0,其余所有點(diǎn)給T標(biāo)號(hào),T(vi)=+∞；第二十頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法

(2)由于弧(v1,v2)、(v1,v3)、(v1,v4)屬于D，且v2、

v3、

v4為T標(biāo)號(hào)，所以修改這三個(gè)點(diǎn)的標(biāo)號(hào)：

T(v2)=min{T(v2),P(v1)+ω12}=min{∞,0+4}=4

T(v3)=min{T(v3),P(v1)+ω13}=min{∞,0+2}=2

T(v4)=min{T(v4),P(v1)+ω14}=min{∞,0+5}=5???????v1(0)v2v7v5v411344452572v3[2]v6[4][5][∞][∞][∞]7第二十一頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法(3)比較所有T標(biāo)號(hào)，T(v3)最小，故令P(v3)=2???????v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]7第二十二頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法(4)v3為剛得到P標(biāo)號(hào)的點(diǎn)，考察弧(v3,v4)，(v3,v6)的端點(diǎn)v4,v6

T(v4)=min{T(v4),P(v3)+ω34}=min{5,2+2}=4

T(v6)=min{T(v6),P(v3)+ω36}=min{∞,2+7}=9???????v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]7第二十三頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法

(5)比較所有T標(biāo)號(hào)，T(v2),T(v4)最小，所以令P(v2)=P(v4)=4???????v1(0)v2v7v5v411344452572v3(2)v6[4][4][9][∞][∞]7第二十四頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法???????v1(0)v2v7v5v411344452572v3(2)v6(4)(4)[9][∞][∞]7第二十五頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法

(6)v2,v4為剛得到P標(biāo)號(hào)的點(diǎn),考察弧(v2,v5)，(v4,v5)，(v4,v6)的端點(diǎn)v5,v6

T(v5)=min{T(v5),P(v4)+ω45,P(v2)+ω25} =min{∞,4+3,4+4}=7

T(v6)=min{T(v6),P(v4)+ω46}=min{9,4+4}=8???????v1(0)v2v7v5v411344452572(4)(4)[8][7][∞]7v3(2)v6第二十六頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法

(7)比較所有T標(biāo)號(hào)，T(v5)最小，所以令P(v5)=7???????v1(0)v2v7v5v411344452572(4)(4)(7)[∞][8]v3(2)v67第二十七頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法???????v1(0)v2v7v5v411344452572(4)(4)(7)[14][8]v3(2)v6(8)v5為剛得到P標(biāo)號(hào)的點(diǎn)，考察弧(v5,v6)，(v5,v7)的端點(diǎn)v6,v7

T(v6)=min{T(v6),P(v5)+ω56}=min{8,7+1}=8

T(v7)=min{T(v7),P(v5)+ω57}=min{∞,7+7}=147第二十八頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法

(9)比較所有T標(biāo)號(hào)，T(v6)最小，所以令P(v6)=8???????v1(0)v2v7v5v411344452572(4)(4)(7)[14](8)v3(2)v67第二十九頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法

(10)v6為剛得到P標(biāo)號(hào)的點(diǎn)，考察弧(v6,v7)的端點(diǎn)v7

T(v7)=min{T(v7),P(v6)+ω67}=min{14,8+5}=13???????v1(0)v2v7v5v411344452572(4)(4)(7)[13](8)v3(2)v67第三十頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路算法

(11)只有一個(gè)T標(biāo)號(hào)T(v7)，令P(v7)=13，停止。???????v1(0)v2v7v5v411344452572(4)(4)(7)(13)(8)v3(2)v67

計(jì)算結(jié)果見上圖，v1到v7的最短路為：同時(shí)得到v1到其余各點(diǎn)的最短路。第三十一頁(yè)，共五十五頁(yè)，編輯于2023年，星期五應(yīng)用舉例例：(設(shè)備更新問題)某企業(yè)在四年內(nèi)都要使用某種設(shè)備，在每年年初作出是購(gòu)買新設(shè)備還是繼續(xù)使用舊設(shè)備的決策。若購(gòu)買新設(shè)備就要支付購(gòu)置費(fèi)；若繼續(xù)使用舊設(shè)備，則需支付維修費(fèi)用。這種設(shè)備在四年之內(nèi)每年年初的價(jià)格以及使用不同時(shí)間（年）的設(shè)備的維修費(fèi)用估計(jì)為：年份1234年初購(gòu)價(jià)10111213維修費(fèi)用24714第三十二頁(yè)，共五十五頁(yè)，編輯于2023年，星期五應(yīng)用舉例問題：制定一個(gè)四年之內(nèi)的設(shè)備更新計(jì)劃，使得四年之內(nèi)的設(shè)備購(gòu)置費(fèi)和維修費(fèi)用之和最小?？梢杂们笞疃搪穯栴}的方法來解決總費(fèi)用最少的設(shè)備更新計(jì)劃問題。第三十三頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求法（2）構(gòu)造長(zhǎng)度矩陣L計(jì)算

其中第三十四頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求法（2）長(zhǎng)度矩陣第三十五頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求法（2）表示vi到vj兩步中距離最短的一條表示vi到vj兩步不能到達(dá)第三十六頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求法（2）第三十七頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求法（2）第三十八頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求法（2）第三十九頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求法（2）求任意兩點(diǎn)最短距離均為mxn矩陣第四十頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最短路求法（2）矩陣中元素為兩點(diǎn)間最頓距離第四十一頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最大流引入輸油管道網(wǎng)，如何安排各管道的輸油量，才能使從vs到vt總油量最大？第四十二頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最大流問題管道網(wǎng)絡(luò)中每邊的最大通過能力即容量是有限的，實(shí)際流量也并不一定等于容量；如何充分利用裝置的能力，以取得最好效果（流量最大），這類問題通常稱為最大流問題。第四十三頁(yè)，共五十五頁(yè)，編輯于2023年，星期五基本概念容量：G=(V,E)，每條邊上有非負(fù)數(shù)cij稱為邊的容量；發(fā)點(diǎn)（源），收點(diǎn)（匯），中間點(diǎn)；對(duì)G中的邊（vi,vj）有流量fij,稱集合f={fij}為網(wǎng)絡(luò)G上的流；第四十四頁(yè)，共五十五頁(yè)，編輯于2023年，星期五基本概念可行流容量限制：對(duì)G中的每條邊（vi,vj）,有平衡條件：對(duì)中間點(diǎn)vi,有對(duì)收點(diǎn)、發(fā)點(diǎn)有所謂最大流問題，就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。當(dāng)fij=cij,則稱流對(duì)邊（vi,vj）是飽和的。第四十五頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最大流－最小割第四十六頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最大流－最小割在容量網(wǎng)絡(luò)中割集是由vs到vt的必經(jīng)之路，無論拿掉哪個(gè)割集，vs到vt便不再相通，所以任何一個(gè)可行流的流量不會(huì)超過任一割集的容量；定理：任一個(gè)網(wǎng)絡(luò)G中，從vs到vt的最大流的流量等于分離vs、vt的最小割的容量。第四十七頁(yè)，共五十五頁(yè)，編輯于2023年，星期五最