運(yùn)籌學(xué)第7章圖與網(wǎng)絡(luò)優(yōu)化

1、1Chapter 7 圖與網(wǎng)絡(luò)優(yōu)化圖與網(wǎng)絡(luò)優(yōu)化圖的基本概念與模型圖的基本概念與模型樹(shù)樹(shù)最短路問(wèn)題最短路問(wèn)題網(wǎng)絡(luò)最大流問(wèn)題網(wǎng)絡(luò)最大流問(wèn)題最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題2 圖論是應(yīng)用非常廣泛的運(yùn)籌學(xué)分支，它已圖論是應(yīng)用非常廣泛的運(yùn)籌學(xué)分支，它已經(jīng)廣泛地應(yīng)用于物理學(xué)經(jīng)廣泛地應(yīng)用于物理學(xué), 控制論，信息論，工程控制論，信息論，工程技術(shù)，交通運(yùn)輸，經(jīng)濟(jì)管理，電子計(jì)算機(jī)等各技術(shù)，交通運(yùn)輸，經(jīng)濟(jì)管理，電子計(jì)算機(jī)等各項(xiàng)領(lǐng)域。對(duì)于科學(xué)研究，市場(chǎng)和社會(huì)生活中的項(xiàng)領(lǐng)域。對(duì)于科學(xué)研究，市場(chǎng)和社會(huì)生活中的許多問(wèn)題，可以同圖論的理論和方法來(lái)加以解許多問(wèn)題，可以同圖論的理論和方法來(lái)加以解決

2、。例如，各種決。例如，各種通信線路的架設(shè)，輸油管道的通信線路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問(wèn)等問(wèn)題，都可以應(yīng)用圖論的方法，簡(jiǎn)便、快捷地加題，都可以應(yīng)用圖論的方法，簡(jiǎn)便、快捷地加以解決。以解決。引引 言言3 17361736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問(wèn)題。篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問(wèn)題。即一即一個(gè)漫步者如何能夠走過(guò)這七座橋，并且每座橋只能走過(guò)個(gè)漫步者如何能夠走過(guò)這七座橋，并且每座橋只能走過(guò)一次，最終回到原出發(fā)地。一次，最終回到原出發(fā)

3、地。如圖如圖1 1所示。所示。 歐拉將這個(gè)問(wèn)題抽象成歐拉將這個(gè)問(wèn)題抽象成一筆畫一筆畫問(wèn)題問(wèn)題。即能否從某一點(diǎn)開(kāi)始不重。即能否從某一點(diǎn)開(kāi)始不重復(fù)地一筆畫出這個(gè)圖形，最終回復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)。到原點(diǎn)。 歐拉在他的論文中證明了這是歐拉在他的論文中證明了這是不可能的。不可能的。 因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連，不可能將它一筆畫出，這數(shù)條邊相連，不可能將它一筆畫出，這就是古典圖論中的第一個(gè)著名問(wèn)題就是古典圖論中的第一個(gè)著名問(wèn)題。ABCD4 一郵遞員送信，要走完他所負(fù)責(zé)的全部街道分送信件，一郵遞員送信，要走完他所負(fù)責(zé)的全部街道分送信件，最后返回郵局。

4、郵遞員都會(huì)本能地以盡可能少的行程最后返回郵局。郵遞員都會(huì)本能地以盡可能少的行程完成送信任務(wù)。如何走路線最短。完成送信任務(wù)。如何走路線最短。1962年，由我國(guó)數(shù)學(xué)家管梅谷提出，國(guó)際上稱為年，由我國(guó)數(shù)學(xué)家管梅谷提出，國(guó)際上稱為中國(guó)郵中國(guó)郵遞員問(wèn)題遞員問(wèn)題。 中國(guó)郵遞員問(wèn)題，即中國(guó)郵遞員問(wèn)題，即 求一個(gè)圈，過(guò)每邊至少一次，并使圈的長(zhǎng)度最短。求一個(gè)圈，過(guò)每邊至少一次，并使圈的長(zhǎng)度最短。5 能否用四種顏色給地圖染色，使能否用四種顏色給地圖染色，使相鄰的國(guó)家有不同的顏色。相鄰的國(guó)家有不同的顏色。 能否用四種顏色給平面圖的點(diǎn)染能否用四種顏色給平面圖的點(diǎn)染色，使有公共邊的點(diǎn)有不同的顏色。色，使有公共邊的點(diǎn)有不

5、同的顏色。6第一節(jié) 圖的基本概念7 在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用系，常常在紙上用點(diǎn)和線點(diǎn)和線來(lái)畫出各式各樣的示意圖。來(lái)畫出各式各樣的示意圖。例例1. 左圖是我國(guó)北京、上海、重左圖是我國(guó)北京、上海、重慶等十四個(gè)城市之間的鐵路交通慶等十四個(gè)城市之間的鐵路交通圖，這里用圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路點(diǎn)之間的線表示城市之間的鐵路線線。諸如此類還有城市中的市政諸如此類還有城市中的市政管道圖，民用航空線圖等等。管道圖，民用航空線圖等等。連云港連云港武漢武漢南京南京徐州徐州上海上海北京

6、北京塘沽塘沽青島青島濟(jì)南濟(jì)南天津天津鄭州鄭州8 例例2 有甲、乙、丙、丁、戊五支球隊(duì)，它們之間的比賽情況有甲、乙、丙、丁、戊五支球隊(duì)，它們之間的比賽情況也可以用圖表示。設(shè)點(diǎn)也可以用圖表示。設(shè)點(diǎn)v1,v2,v3,v4,v5分別代表甲、乙、丙、丁、分別代表甲、乙、丙、丁、戊五支球隊(duì)。戊五支球隊(duì)。若兩支球隊(duì)之間比賽過(guò)，則在相應(yīng)的點(diǎn)之間聯(lián)若兩支球隊(duì)之間比賽過(guò)，則在相應(yīng)的點(diǎn)之間聯(lián)一條線，且這條線不過(guò)其他點(diǎn)。一條線，且這條線不過(guò)其他點(diǎn)。如下圖所示：如下圖所示：v1v2v3v4v5可知各隊(duì)之間的比賽情況如下：可知各隊(duì)之間的比賽情況如下：甲甲 乙、丙、丁、戊乙、丙、丁、戊乙乙 甲、丙甲、丙丙丙 甲、乙、丁甲、

7、乙、丁丁丁 甲、丙、戊甲、丙、戊戊戊 甲、丁甲、丁9例例3 儲(chǔ)存儲(chǔ)存8種化學(xué)藥品，其中某些藥品不能存放在同一個(gè)庫(kù)種化學(xué)藥品，其中某些藥品不能存放在同一個(gè)庫(kù)房里。房里。 用用v1,v2,v8分別代表這分別代表這8種藥品。種藥品。規(guī)定若兩種藥品不規(guī)定若兩種藥品不能存放在一起，則其相應(yīng)的點(diǎn)之間聯(lián)一條線能存放在一起，則其相應(yīng)的點(diǎn)之間聯(lián)一條線。如下圖所示：。如下圖所示：v1v2v3v4v5v6v7v8可知需要可知需要4個(gè)庫(kù)房，其中個(gè)庫(kù)房，其中一個(gè)答案是：一個(gè)答案是： v1 v2, v4, v7 v3, v5 v6, v8 還有其他的答案。還有其他的答案。10由以上例子可見(jiàn)：由以上例子可見(jiàn)： 圖是反映實(shí)際

8、生活中某些對(duì)象之間關(guān)系的一種工具。通常圖是反映實(shí)際生活中某些對(duì)象之間關(guān)系的一種工具。通常用用點(diǎn)點(diǎn)代表研究的對(duì)象代表研究的對(duì)象，用，用點(diǎn)與點(diǎn)之間的連線表示點(diǎn)與點(diǎn)之間的連線表示這兩個(gè)對(duì)象這兩個(gè)對(duì)象之間有特定的之間有特定的關(guān)系關(guān)系。 在一般情況下，在一般情況下，圖中的圖中的相對(duì)位置相對(duì)位置如何，點(diǎn)與點(diǎn)之間如何，點(diǎn)與點(diǎn)之間線的長(zhǎng)線的長(zhǎng)短曲直短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的并不重要并不重要。如如反映例反映例2 2中球隊(duì)之間的比賽情況的下述兩種圖沒(méi)有本質(zhì)上的區(qū)中球隊(duì)之間的比賽情況的下述兩種圖沒(méi)有本質(zhì)上的區(qū)別。別。11v3v1v2v4v6v5 例例1-1-例例3 3

9、中涉及到的對(duì)象之間的中涉及到的對(duì)象之間的“關(guān)系關(guān)系”具有具有“對(duì)稱性對(duì)稱性”。即：如果甲與乙有某種關(guān)系，則乙與甲也有同樣的這種關(guān)系。即：如果甲與乙有某種關(guān)系，則乙與甲也有同樣的這種關(guān)系。然而實(shí)際生活中，有許多關(guān)系不具有這種對(duì)稱性。如例然而實(shí)際生活中，有許多關(guān)系不具有這種對(duì)稱性。如例2 2中的中的比賽比賽勝負(fù)情況勝負(fù)情況就不能用簡(jiǎn)單的連線來(lái)表示。為了反映這種關(guān)就不能用簡(jiǎn)單的連線來(lái)表示。為了反映這種關(guān)系，可以系，可以用一條帶箭頭的連線表示用一條帶箭頭的連線表示。 例例4 有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)v1v6表示這六表示這六支球隊(duì)，它們之間的比賽情況，也可

10、以用圖反映出來(lái)，已知支球隊(duì)，它們之間的比賽情況，也可以用圖反映出來(lái)，已知v1隊(duì)?wèi)?zhàn)勝隊(duì)?wèi)?zhàn)勝v2隊(duì)，隊(duì)，v2隊(duì)?wèi)?zhàn)勝隊(duì)?wèi)?zhàn)勝v3隊(duì)，隊(duì)，v3隊(duì)?wèi)?zhàn)勝隊(duì)?wèi)?zhàn)勝v5隊(duì)，隊(duì)，如此等等。這個(gè)勝如此等等。這個(gè)勝負(fù)情況，可以用下圖所示的有向圖反映出來(lái)。負(fù)情況，可以用下圖所示的有向圖反映出來(lái)。12基本概念基本概念點(diǎn)：點(diǎn)：研究對(duì)象（車站、國(guó)家、球隊(duì)）；研究對(duì)象（車站、國(guó)家、球隊(duì)）；點(diǎn)間連線：點(diǎn)間連線：對(duì)象之間的特定關(guān)系（陸地間有橋、鐵路線、對(duì)象之間的特定關(guān)系（陸地間有橋、鐵路線、兩球隊(duì)比賽及結(jié)果兩球隊(duì)比賽及結(jié)果) )。對(duì)稱關(guān)系：對(duì)稱關(guān)系：橋、道路；用橋、道路；用不帶箭頭的連線表示，稱為邊。不帶箭頭的連線表示，稱為邊。非對(duì)

11、稱關(guān)系：非對(duì)稱關(guān)系：甲隊(duì)勝乙隊(duì)，用甲隊(duì)勝乙隊(duì)，用帶箭頭的連線表示，稱為帶箭頭的連線表示，稱為 弧?；?。圖：圖：點(diǎn)及邊（或?。┙M成。點(diǎn)及邊（或?。┙M成。對(duì)對(duì)稱稱關(guān)關(guān)系系非非對(duì)對(duì)稱稱關(guān)關(guān)系系13有向圖有向圖 由點(diǎn)及弧所構(gòu)成的圖，記為由點(diǎn)及弧所構(gòu)成的圖，記為D=(V,A)， V, A分別是分別是D的點(diǎn)集合和弧集合。的點(diǎn)集合和弧集合。無(wú)向圖無(wú)向圖由點(diǎn)及邊所構(gòu)成的圖。記為由點(diǎn)及邊所構(gòu)成的圖。記為G=(V,E), V，E分別是分別是G的點(diǎn)集合和邊集合的點(diǎn)集合和邊集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e3e4e5a6e6連接點(diǎn)連接點(diǎn)vi,vjV的邊的邊, 記作記作 vi,vj或或

12、vj,vi。一條方向從一條方向從vi指向指向vj的弧，記作的弧，記作 (vi, vj)。14例如例如.圖圖8-4是一個(gè)無(wú)向圖是一個(gè)無(wú)向圖G=（V，E）其中其中V = v1,v2,v3,v4 E = v1,v2,v2,v1,v2,v3, v3,v4,v1,v4, v2,v4, v3,v3 v3v2v1v4圖圖8-48-415圖圖8-5是一個(gè)有向圖是一個(gè)有向圖D=（V，A）其中其中V = v1,v2,v3,v4,v5,v6,v7 A = (v1 ,v2),(v1 ,v3),(v3 ,v2), (v3 ,v4), (v2 ,v4),(v4 ,v5),(v4 ,v6),(v5 ,v3), (v5 ,v

13、4),(v5 ,v6),(v6 ,v7)v7v5v3v4v2v1v6圖圖8-58-516v3e7e4e8e5e6e1e2e3v1v2v4v5 端點(diǎn)端點(diǎn),關(guān)聯(lián)邊關(guān)聯(lián)邊,相鄰相鄰若邊若邊e可表示為可表示為e=vi,vj，稱，稱vi和和vj是是邊邊e的的端點(diǎn)端點(diǎn)，稱邊，稱邊e為點(diǎn)為點(diǎn)vi或或vj的的關(guān)聯(lián)關(guān)聯(lián)邊邊。若點(diǎn)。若點(diǎn)vi，vj與同一條邊關(guān)聯(lián)，稱與同一條邊關(guān)聯(lián)，稱點(diǎn)點(diǎn)vi和和vj相鄰相鄰；若邊；若邊ei和和ej具有公共具有公共的端點(diǎn)，稱的端點(diǎn)，稱邊邊ei和和ej相鄰相鄰。在一個(gè)圖的幾何實(shí)現(xiàn)中，在一個(gè)圖的幾何實(shí)現(xiàn)中，兩條邊的交點(diǎn)可能不是圖的頂點(diǎn)兩條邊的交點(diǎn)可能不是圖的頂點(diǎn)。例如例如4e1e2e3e

14、5e6e1v2v3v4v圖圖 G 中的中的點(diǎn)數(shù)點(diǎn)數(shù)記為記為 p(G)，邊數(shù)邊數(shù)記為記為q(G) . 簡(jiǎn)記為簡(jiǎn)記為p，q.此時(shí)，圖此時(shí)，圖 G 可以表示為可以表示為G = ( p, q ).17 環(huán)環(huán) 若在圖若在圖G中，某個(gè)邊的兩個(gè)端點(diǎn)相同，中，某個(gè)邊的兩個(gè)端點(diǎn)相同，則稱則稱e是環(huán)。如是環(huán)。如 e7v1v2v3v4e1e2e3e4e5e6e7 多重邊多重邊 若兩個(gè)點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。如若兩個(gè)點(diǎn)之間有多于一條的邊，稱這些邊為多重邊。如 e1, e2 簡(jiǎn)單圖簡(jiǎn)單圖 一個(gè)無(wú)環(huán)，無(wú)多重邊的圖。一個(gè)無(wú)環(huán)，無(wú)多重邊的圖。 多重圖多重圖 一個(gè)無(wú)環(huán)、但允許有多重邊的圖。一個(gè)無(wú)環(huán)、但允許有多重

15、邊的圖。 環(huán)環(huán), 多重邊多重邊, 簡(jiǎn)單圖簡(jiǎn)單圖注：注：無(wú)特別聲明我們今后討論的圖都是無(wú)特別聲明我們今后討論的圖都是簡(jiǎn)單圖簡(jiǎn)單圖 .18 點(diǎn)點(diǎn)v的的次次 以點(diǎn)以點(diǎn)vi為端點(diǎn)邊的個(gè)數(shù)，記為為端點(diǎn)邊的個(gè)數(shù)，記為dG(vi)或或d(vi)。注：環(huán)在計(jì)算次時(shí)算做注：環(huán)在計(jì)算次時(shí)算做兩次兩次v1v2v3v4e1e2e3e4e5e6e7如如 d(v4)=5 d(v2)=4v5 懸掛點(diǎn)懸掛點(diǎn) 次為次為1的點(diǎn)，如的點(diǎn)，如 v5 懸掛邊懸掛邊 懸掛點(diǎn)的關(guān)聯(lián)邊，如懸掛點(diǎn)的關(guān)聯(lián)邊，如 e8e8 孤立點(diǎn)孤立點(diǎn) 次為次為0的點(diǎn)的點(diǎn) 偶點(diǎn)偶點(diǎn) 次為偶數(shù)的點(diǎn)，如次為偶數(shù)的點(diǎn)，如 v2 奇點(diǎn)奇點(diǎn) 次為奇數(shù)的點(diǎn)次為奇數(shù)的點(diǎn), ,

16、 如如 v5 次，奇點(diǎn)，偶點(diǎn)，次，奇點(diǎn)，偶點(diǎn)， 孤立點(diǎn)孤立點(diǎn)19 鏈：鏈： 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列序列, , 如如: : （v0 ,e1 ,v1 ,e2 ,v2 ,e3 ,v3 ,vn-1 ,en , vn ）;其中其中v0 ，vn分別為鏈的分別為鏈的起點(diǎn)起點(diǎn)和和終點(diǎn)終點(diǎn)， v1 ,v2 ,vn-1稱稱為為中間點(diǎn)中間點(diǎn) ； 圈圈： 起點(diǎn)與終點(diǎn)重合的鏈；起點(diǎn)與終點(diǎn)重合的鏈； 簡(jiǎn)單鏈（圈）簡(jiǎn)單鏈（圈）：鏈（圈）中所含的鏈（圈）中所含的邊邊均不相同均不相同； 初等鏈（圈）初等鏈（圈）：鏈（圈）中所含的鏈（圈）中所含的點(diǎn)點(diǎn)均不相同均不相同,也也

17、稱通路；稱通路； 鏈，圈，初等鏈，初等圈，簡(jiǎn)單鏈（圈）鏈，圈，初等鏈，初等圈，簡(jiǎn)單鏈（圈）20 鏈鏈中間點(diǎn)中間點(diǎn)初等鏈初等鏈圈圈初等圈初等圈簡(jiǎn)單圈簡(jiǎn)單圈 v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9 在上圖中在上圖中,(v1, v2 , v3 , v4 , v5 , v3 , v6 , v7)是一條簡(jiǎn)單鏈?zhǔn)且粭l簡(jiǎn)單鏈, 但不是初等鏈但不是初等鏈在該鏈中在該鏈中, v2, v3, v4, v5, v3, v6是中間點(diǎn)是中間點(diǎn)(v1 , v2 , v3 , v6 , v7)是一條初等鏈?zhǔn)且粭l初等鏈(v1 , v2 , v3 , v4 , v1)是一個(gè)初等圈是一個(gè)初等圈(v4 ,

18、 v1 , v2 , v3 , v5 , v7, v6 , v3 , v4)是一個(gè)簡(jiǎn)單圈是一個(gè)簡(jiǎn)單圈21 連通圖連通圖圖圖G中，若任何兩個(gè)點(diǎn)之間，至少有一條鏈，稱為連通圖。否中，若任何兩個(gè)點(diǎn)之間，至少有一條鏈，稱為連通圖。否則稱為不連通圖。則稱為不連通圖。 連通分圖連通分圖( (分圖分圖) )若若G是不連通圖，則它的每個(gè)連通的部分稱為連通分圖。是不連通圖，則它的每個(gè)連通的部分稱為連通分圖。v1v2v3v4e1e2e3e4e5e6v5v6e7如左圖就是個(gè)不連通圖，它如左圖就是個(gè)不連通圖，它是由兩個(gè)是由兩個(gè)連通分圖連通分圖構(gòu)成的。構(gòu)成的。 連通圖、子圖、支撐子圖、基礎(chǔ)圖連通圖、子圖、支撐子圖、基礎(chǔ)

19、圖22給定圖給定圖G=（V，E），若圖），若圖G=（V，E），其中），其中V V，E E ，則稱，則稱G是是G的的子圖子圖。給定圖給定圖G=（V，E），若圖），若圖G=（V，E），其中），其中E E，則稱則稱G是是G的一個(gè)的一個(gè)支撐子圖（部分圖）支撐子圖（部分圖）。點(diǎn)全部保留點(diǎn)全部保留（a）（b）子圖子圖（c）部分圖部分圖子圖與部分圖（支撐子圖）子圖與部分圖（支撐子圖）23e1e3e2Gv3v4v5v2v1G-v1 ,v5 e1e3e2v3v4v5v2v1頂點(diǎn)導(dǎo)出子圖頂點(diǎn)導(dǎo)出子圖： 設(shè)設(shè)W是圖是圖G的一個(gè)非的一個(gè)非空頂點(diǎn)子集空頂點(diǎn)子集, 從從G中刪除中刪除W中頂點(diǎn)以及與這些頂中頂點(diǎn)以及與這些頂

20、點(diǎn)相關(guān)聯(lián)的邊所得到的點(diǎn)相關(guān)聯(lián)的邊所得到的子圖稱為子圖稱為導(dǎo)出子圖導(dǎo)出子圖，記記為為G-W24 基礎(chǔ)圖基礎(chǔ)圖給定一個(gè)有向圖給定一個(gè)有向圖D=(V, A) ，從，從D中中去掉所有弧上的箭頭去掉所有弧上的箭頭，所得到的無(wú)向圖稱為基礎(chǔ)圖。記之為所得到的無(wú)向圖稱為基礎(chǔ)圖。記之為G(D)。v1v2v3v4a1a2a3a4a5a6D=(V, A)v1v2v3v4e1e2e3e4e5e6G(D)25有向圖：有向圖：關(guān)聯(lián)邊有方向關(guān)聯(lián)邊有方向?。夯。河邢驁D的邊有向圖的邊a=(u ,v),起點(diǎn)起點(diǎn)u, ,終點(diǎn)終點(diǎn)v; ;路：路：若有從若有從u到到v不考慮方向的鏈不考慮方向的鏈, ,且各方向一致且各方向一致, ,則則

21、稱之為從稱之為從u到到v的路；的路；初等路初等路: : 各頂點(diǎn)都不相同的路；各頂點(diǎn)都不相同的路； 初等回路初等回路: :u = v 的初等的初等 路路; ; 連通圖：連通圖： 若不考慮方向若不考慮方向 是無(wú)向連通圖是無(wú)向連通圖; ; 強(qiáng)連通圖：強(qiáng)連通圖：任兩點(diǎn)有路任兩點(diǎn)有路; ; 有向圖、弧、路、初等路有向圖、弧、路、初等路26v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7 路路 初等路初等路 回路回路v5是是一一個(gè)個(gè)回回路路。在在上上圖圖中中),( ,385645233vavavavav。的的路路。也也是是一一條條初初等等路路到到是是從從616744321),(vv

22、vavavav27定理定理1 任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。倍。定理定理2 任何圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)。任何圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)。證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)之和等于邊數(shù)的被計(jì)算了兩次，所以頂點(diǎn)次數(shù)之和等于邊數(shù)的2倍。倍。證明：設(shè)證明：設(shè)V1和和V2分別為圖分別為圖G中奇點(diǎn)與偶點(diǎn)的集合。由定理中奇點(diǎn)與偶點(diǎn)的集合。由定理1可得：可得：mvdvdvdVvVvVv2)()()(21 2m為偶數(shù)，且偶點(diǎn)的次之和為偶數(shù)，且偶點(diǎn)的次之和

23、 也為偶數(shù)，所以也為偶數(shù)，所以 必為偶必為偶數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。 2)(Vvvd 1)(Vvvd28第二節(jié) 樹(shù) 樹(shù)的概念樹(shù)的概念 構(gòu)造生成樹(shù)的方法構(gòu)造生成樹(shù)的方法 最小生成樹(shù)問(wèn)題最小生成樹(shù)問(wèn)題29 樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。會(huì)領(lǐng)域應(yīng)用極為廣泛。 乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。圖所示。AB CDEF GH運(yùn)動(dòng)員運(yùn)動(dòng)員30 某企業(yè)的組織機(jī)構(gòu)圖也可用樹(shù)圖表示。某企業(yè)的組織機(jī)構(gòu)圖也可用樹(shù)圖表示。廠長(zhǎng)廠長(zhǎng)人事

24、科人事科財(cái)務(wù)科財(cái)務(wù)科總總工程師工程師生產(chǎn)生產(chǎn)副廠長(zhǎng)副廠長(zhǎng)經(jīng)營(yíng)經(jīng)營(yíng)副廠長(zhǎng)副廠長(zhǎng)技術(shù)科技術(shù)科新產(chǎn)品新產(chǎn)品開(kāi)發(fā)科開(kāi)發(fā)科生產(chǎn)科生產(chǎn)科設(shè)備科設(shè)備科供應(yīng)科供應(yīng)科動(dòng)力科動(dòng)力科檢驗(yàn)科檢驗(yàn)科銷售科銷售科312.1 樹(shù)的定義及性質(zhì)樹(shù)的定義及性質(zhì)也也是是懸懸掛掛點(diǎn)點(diǎn)。為為懸懸掛掛點(diǎn)點(diǎn)。同同理理，所所以以與與假假設(shè)設(shè)矛矛盾盾則則存存在在鏈鏈不不在在上上述述鏈鏈中中若若與與條條件件矛矛盾盾含含圈圈則則在在上上述述鏈鏈中中若若中中的的一一條條邊邊。為為使使得得則則存存在在即即不不是是懸懸掛掛點(diǎn)點(diǎn)設(shè)設(shè)時(shí)時(shí)當(dāng)當(dāng)命命題題成成立立。時(shí)時(shí)即即時(shí)時(shí)當(dāng)當(dāng)中中邊邊數(shù)數(shù)最最多多的的一一條條鏈鏈。為為設(shè)設(shè)反反證證法法k1k21ss1s21s

25、1ss11k21vvvvvvvvvvvGvGvvv2vdv2Gp2Gp2kGvvv.),(,;),(,)(,)(,)(,),(: 證明證明樹(shù)的定義樹(shù)的定義：一個(gè)無(wú)圈的連通圖稱為樹(shù)。一個(gè)無(wú)圈的連通圖稱為樹(shù)。定理定理3 設(shè)圖設(shè)圖G=(V, E) 是一個(gè)樹(shù)，是一個(gè)樹(shù)，p(G)2，則，則G中至少有兩個(gè)懸中至少有兩個(gè)懸掛點(diǎn)。掛點(diǎn)。32定理定理4 圖圖G=(V,E) 是一個(gè)樹(shù)的充分必要條件是是一個(gè)樹(shù)的充分必要條件是G中中不含圈，且恰有不含圈，且恰有p-1條邊條邊 (即：即：q(G)=p(G)-1)。用用數(shù)數(shù)學(xué)學(xué)歸歸納納法法先先證證必必要要性性。即即要要證證明明.)(1pGq 證明證明.,的的連連通通分分圖

26、圖為為不不連連通通，則則存存在在假假設(shè)設(shè)GGGGGS21顯然成立。顯然成立。時(shí)時(shí)當(dāng)當(dāng),2p 條邊。條邊。時(shí)，命題成立，即含有時(shí)，命題成立，即含有設(shè)設(shè)1nnp .,11vGnp記記為為中中含含有有懸懸掛掛點(diǎn)點(diǎn)時(shí)時(shí)，當(dāng)當(dāng) ，個(gè)點(diǎn)的樹(shù)，由假設(shè)知：個(gè)點(diǎn)的樹(shù)，由假設(shè)知：是是因?yàn)橐驗(yàn)閚vGpnvGqnvG )(, 1)(111。，從而，從而，為懸掛點(diǎn)，所以為懸掛點(diǎn)，所以又因?yàn)橛忠驗(yàn)?)(1)()(11 pnGqGqvGqv充分性：充分性：只需證明只需證明G為連通的即可。為連通的即可。為為樹(shù)樹(shù)。所所以以不不含含圈圈因因?yàn)闉閕iGsiG,), 2 , 1( . 1)( iiiipGqpG個(gè)點(diǎn)，則由必要性知個(gè)點(diǎn)

27、，則由必要性知有有假設(shè)假設(shè)., 2)()(1矛矛盾盾則則 pspGqGqsii33 定理定理5 圖圖G=(V, E)是一個(gè)樹(shù)的充分必要條件是是一個(gè)樹(shù)的充分必要條件是G是連是連通圖，并且通圖，并且q(G)=p(G)-1。 首先，首先， G存在懸掛點(diǎn)。否則，因?yàn)榇嬖趹覓禳c(diǎn)。否則，因?yàn)镚連通并且連通并且 ，所以對(duì)于任意點(diǎn)所以對(duì)于任意點(diǎn)vi，都有，都有 。從而。從而 矛矛盾盾。),()(21)()(1GpvdGqGpii . 1)(2)(1)()( iivGpGpGqvGq2Gp )(2vdi )(證明證明：由定理由定理4，必要性顯然。，必要性顯然。充分性：充分性：只需證明只需證明G不含圈即可。不含圈

28、即可。數(shù)學(xué)歸納法：數(shù)學(xué)歸納法：p(G)=1, 2時(shí)，結(jié)論顯然成立。假設(shè)時(shí)，結(jié)論顯然成立。假設(shè)p(G)=n時(shí)，時(shí)，結(jié)論成立。下證結(jié)論成立。下證p(G)=n+1時(shí)結(jié)論成立時(shí)結(jié)論成立。設(shè)設(shè)vi為為G的一個(gè)懸掛點(diǎn)。則的一個(gè)懸掛點(diǎn)。則G-vi仍為連通圖，并且仍為連通圖，并且由歸納假設(shè)：由歸納假設(shè)：G-vi不含圈。所以不含圈。所以G不含圈。不含圈。34定理定理6 圖圖G是樹(shù)的充分必要條件是任意兩個(gè)頂點(diǎn)之間恰有一是樹(shù)的充分必要條件是任意兩個(gè)頂點(diǎn)之間恰有一條鏈。條鏈。證明：證明：由樹(shù)的定義，必要性顯然。由樹(shù)的定義，必要性顯然。 充分性充分性：因?yàn)槿蝺蓚€(gè)頂點(diǎn)間恰有一條鏈，顯然：因?yàn)槿蝺蓚€(gè)頂點(diǎn)間恰有一條鏈，顯然G

29、是連通是連通的。如果的。如果G中含有圈的話，則其中至少有兩個(gè)頂點(diǎn)間有兩條中含有圈的話，則其中至少有兩個(gè)頂點(diǎn)間有兩條鏈，這與題設(shè)矛盾。所以鏈，這與題設(shè)矛盾。所以G是樹(shù)，充分性得證。是樹(shù)，充分性得證。推論：推論： 從一個(gè)樹(shù)中去掉一條邊，則余下的圖是不連通的從一個(gè)樹(shù)中去掉一條邊，則余下的圖是不連通的。由此。由此知，在點(diǎn)集合相同的所有圖中，知，在點(diǎn)集合相同的所有圖中，樹(shù)是含邊數(shù)最少的連通圖樹(shù)是含邊數(shù)最少的連通圖。在在樹(shù)樹(shù)中不相鄰的兩個(gè)點(diǎn)間中不相鄰的兩個(gè)點(diǎn)間添上一條邊，則恰好得到一個(gè)圈添上一條邊，則恰好得到一個(gè)圈。進(jìn)一步地說(shuō)，如果再?gòu)倪@個(gè)進(jìn)一步地說(shuō)，如果再?gòu)倪@個(gè)圈上圈上任意任意去去掉一條掉一條邊邊，可以

30、，可以得得到一個(gè)到一個(gè)樹(shù)樹(shù)。352.2 圖的支撐樹(shù)圖的支撐樹(shù)定義定義：設(shè)圖設(shè)圖T=(V, E) 是是圖圖G的支撐子圖，如果圖的支撐子圖，如果圖T=(V, E) 是一個(gè)樹(shù)，則稱是一個(gè)樹(shù)，則稱T是是G的一個(gè)的一個(gè)支撐樹(shù)。支撐樹(shù)。 定理：圖定理：圖G有支撐樹(shù)的充要條件是圖有支撐樹(shù)的充要條件是圖G是連通的。是連通的。證明：必要性顯然。充分性：設(shè)證明：必要性顯然。充分性：設(shè)G是連通的。分兩種情形。是連通的。分兩種情形。 若若G不含圈，則不含圈，則G本身是一個(gè)樹(shù)，從而本身是一個(gè)樹(shù)，從而G是它自身的一個(gè)是它自身的一個(gè)支撐樹(shù)。支撐樹(shù)。 若若G含圈，任取一個(gè)圈，從圈中任意地去掉一條邊，得含圈，任取一個(gè)圈，從圈中

31、任意地去掉一條邊，得到圖到圖G的一個(gè)支撐子圖的一個(gè)支撐子圖G1。如果。如果G1不含圈，那么不含圈，那么G1是是G的的一個(gè)支撐樹(shù)；如果一個(gè)支撐樹(shù)；如果G1仍含圈，那么從仍含圈，那么從G1中任取一個(gè)圈，從中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖圈中再任意去掉一條邊，得到圖G的一個(gè)支撐子圖的一個(gè)支撐子圖G2，如，如此重復(fù)，最終可以得到此重復(fù)，最終可以得到G的一個(gè)支撐子圖的一個(gè)支撐子圖Gk, 它不含圈，于它不含圈，于是是Gk是是G的一個(gè)支撐樹(shù)。的一個(gè)支撐樹(shù)。36支撐樹(shù)的求解方法支撐樹(shù)的求解方法 破圈法：破圈法：任取一個(gè)圈，從圈中去掉一個(gè)邊，對(duì)剩余任取一個(gè)圈，從圈中去掉一個(gè)邊，對(duì)剩余的圖重復(fù)上述步驟

32、，直到?jīng)]有圈為止。的圖重復(fù)上述步驟，直到?jīng)]有圈為止。例例 用破圈法求解圖的一個(gè)支撐樹(shù)用破圈法求解圖的一個(gè)支撐樹(shù)v1v2v3v4v5e1e2e3e4e5e6e7e8這就得到了該圖的一個(gè)支撐樹(shù)。這就得到了該圖的一個(gè)支撐樹(shù)。37v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9這就得到了該圖的一個(gè)支撐樹(shù)。這就得到了該圖的一個(gè)支撐樹(shù)。 避圈法避圈法：在圖中任取一條邊，找一條與不構(gòu)成圈的在圖中任取一條邊，找一條與不構(gòu)成圈的邊，再找一條與不構(gòu)成圈的邊。一般，設(shè)已邊，再找一條與不構(gòu)成圈的邊。一般，設(shè)已有有 ，找一條與，找一條與 中的任何一條邊不中的任何一條邊不構(gòu)成圈的邊構(gòu)成圈的邊 。重復(fù)上述過(guò)程，

33、直到不能進(jìn)行為止。重復(fù)上述過(guò)程，直到不能進(jìn)行為止。 1e1e2e3e1ke,21ee,21keee,21keee38)(min)(*TwTwT 2.3 最小支撐樹(shù)問(wèn)題最小支撐樹(shù)問(wèn)題定義定義3 給圖給圖G=(V, E) ，若，若G中的每一條邊中的每一條邊vi,vj，相應(yīng)地有一，相應(yīng)地有一個(gè)數(shù)個(gè)數(shù)wij，則稱這樣的圖，則稱這樣的圖G為為賦權(quán)圖賦權(quán)圖，wij稱為邊稱為邊vi,vj上的上的權(quán)權(quán)。定義定義4 如果如果T=(V, E) 是是G的一個(gè)支撐樹(shù)，稱的一個(gè)支撐樹(shù)，稱E中所有邊的中所有邊的權(quán)之和為權(quán)之和為支撐樹(shù)支撐樹(shù)T的權(quán)的權(quán)，記為，記為w(T)，即，即 TvvijjiwTw),()(最小支撐樹(shù)最小

34、支撐樹(shù) 如果支撐樹(shù)如果支撐樹(shù)T*的權(quán)的權(quán)w(T*)是是G的所有支撐樹(shù)的權(quán)中最小者，的所有支撐樹(shù)的權(quán)中最小者，則稱則稱T*是是G的的最小支撐樹(shù)最小支撐樹(shù)(簡(jiǎn)稱最小樹(shù)簡(jiǎn)稱最小樹(shù)),即即39最小支撐樹(shù)的求法最小支撐樹(shù)的求法方法一方法一 避圈法避圈法 開(kāi)始選一條開(kāi)始選一條權(quán)最小權(quán)最小的邊，以后每一步中，總從未被選取的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。v1v2v3v4v5v6651572344這就得到了該圖的一個(gè)最小支撐樹(shù)。這就得到了該圖的一個(gè)最小支撐樹(shù)。40方法二方法二 破圈法破圈法 任取一個(gè)圈，從圈中

35、任取一個(gè)圈，從圈中去掉去掉一條一條權(quán)最大的邊權(quán)最大的邊。在余下的。在余下的圖中，重復(fù)這個(gè)步驟，一直到一個(gè)不含圈的圖為止，這時(shí)圖中，重復(fù)這個(gè)步驟，一直到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹(shù)。的圖便是最小樹(shù)。v1v2v3v4v5v6651572344這就得到了該圖的一個(gè)最小支撐樹(shù)。這就得到了該圖的一個(gè)最小支撐樹(shù)。4177ABCDEST2254143515練習(xí)：用破圈法求解練習(xí)：用破圈法求解42第三節(jié)第三節(jié) 最短路問(wèn)題最短路問(wèn)題43一、最短路問(wèn)題的提出一、最短路問(wèn)題的提出v1v2v3v4v5v6v7v8v9132216610410423236例例左圖為單行線交通左圖為單行線交通網(wǎng)，網(wǎng)，弧旁數(shù)字表示

36、弧旁數(shù)字表示通過(guò)這條單行線所通過(guò)這條單行線所需要的需要的費(fèi)用費(fèi)用。求從。求從v1出發(fā)到出發(fā)到v8總費(fèi)用總費(fèi)用最小最小的路線。的路線。有很多條路線可供選擇。每條路線的費(fèi)用就是相應(yīng)的路中各有很多條路線可供選擇。每條路線的費(fèi)用就是相應(yīng)的路中各條弧的費(fèi)用之和。條弧的費(fèi)用之和。如上圖所示的路線為最短路線。如上圖所示的路線為最短路線。44在圖論中，在圖論中，最短路問(wèn)題最短路問(wèn)題可歸結(jié)為以下幾步：可歸結(jié)為以下幾步：(1)給定一個(gè)賦權(quán)有向圖給定一個(gè)賦權(quán)有向圖D(V, A)及及w(a)= wij；(2)給定給定D中兩個(gè)頂點(diǎn)中兩個(gè)頂點(diǎn)vs、vt，P是是D中從中從vs到到vt的一條路；的一條路；(3)定義路定義路P

37、的權(quán)的權(quán): P中所有弧的權(quán)之和，即中所有弧的權(quán)之和，即 w(P) wij ；(4)求一條權(quán)最小的路求一條權(quán)最小的路P0: w(P0) =min w(P) 上式中對(duì)上式中對(duì)D中所有從中所有從vs到到vt的路的路P取最小，稱取最小，稱P0是從是從vs到到vt的最的最短路。短路。 路路P0的權(quán)稱為從的權(quán)稱為從vs到到vt的距離，記為的距離，記為d(vs，vt)。 顯然，顯然，d(vs，vt)與與d(vt，vs)不一定相等。不一定相等。45最短路問(wèn)題的特性最短路問(wèn)題的特性 若序列若序列 vs , v1, . , vn-1 , vn是從是從vs到到vt間的最短路，則間的最短路，則序列序列 vs , v1

38、 , . , vn-1 必為從必為從vs 到到vn-1的最短路。的最短路。假定假定v1v2 v3 v4是是v1 v4的最短路，則的最短路，則v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的最短路。的最短路。v1v2v3v4v5 若求起點(diǎn)若求起點(diǎn)A到任一點(diǎn)到任一點(diǎn)G的最短路線，可先求的最短路線，可先求A到到G點(diǎn)的相鄰點(diǎn)的相鄰前點(diǎn)的最短距離，在此基礎(chǔ)上求出前點(diǎn)的最短距離，在此基礎(chǔ)上求出A到到G點(diǎn)的最短距離。這樣點(diǎn)的最短距離。這樣最終一定能求出起點(diǎn)到終點(diǎn)的最短距離。最終一定能求出起點(diǎn)到終點(diǎn)的最短距離。46 基本思想基本思想：從始點(diǎn)從始點(diǎn)vs出發(fā)出

39、發(fā)，逐步順序地向外探尋，每向，逐步順序地向外探尋，每向外延伸外延伸一步都要求是最短一步都要求是最短的的執(zhí)行過(guò)程中，與每個(gè)點(diǎn)對(duì)執(zhí)行過(guò)程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄下一個(gè)數(shù)應(yīng)，記錄下一個(gè)數(shù)(稱為稱為這個(gè)點(diǎn)的標(biāo)號(hào)這個(gè)點(diǎn)的標(biāo)號(hào)) 1. 標(biāo)號(hào)標(biāo)號(hào)P（固定標(biāo)號(hào)或永久性標(biāo)號(hào)）（固定標(biāo)號(hào)或永久性標(biāo)號(hào)） 從始點(diǎn)從始點(diǎn)vs到該標(biāo)號(hào)點(diǎn)到該標(biāo)號(hào)點(diǎn)vj的最短路權(quán)記為的最短路權(quán)記為P (vj) 。 2. 標(biāo)號(hào)標(biāo)號(hào)T（臨時(shí)性標(biāo)號(hào)）（臨時(shí)性標(biāo)號(hào)） 從始點(diǎn)從始點(diǎn)vs到該標(biāo)號(hào)點(diǎn)到該標(biāo)號(hào)點(diǎn)vj的最短路權(quán)上界記為的最短路權(quán)上界記為T (vj) 該方法的該方法的每一步每一步就是去就是去修改修改T標(biāo)號(hào)標(biāo)號(hào)，并且把某一個(gè)具，并且把某一個(gè)具T標(biāo)標(biāo)

40、號(hào)號(hào)的點(diǎn)的點(diǎn)改變?yōu)楦淖優(yōu)榫哂芯哂蠵標(biāo)號(hào)標(biāo)號(hào)的點(diǎn)，從而使的點(diǎn)，從而使D中具中具P標(biāo)號(hào)的頂點(diǎn)數(shù)標(biāo)號(hào)的頂點(diǎn)數(shù)多一個(gè)，至多經(jīng)過(guò)多一個(gè)，至多經(jīng)過(guò)n-1步，就可以求出始點(diǎn)步，就可以求出始點(diǎn)vs到各點(diǎn)的最短路到各點(diǎn)的最短路。最短路問(wèn)題求解方法最短路問(wèn)題求解方法-Dijkstra算法算法3. 前點(diǎn)標(biāo)號(hào)前點(diǎn)標(biāo)號(hào) m ： 表示始點(diǎn)表示始點(diǎn)vs到到vj的最短路上的最短路上vj的的前一點(diǎn)是前一點(diǎn)是vm。 m ,P (vj) m, T (vj) vm, T (vj) vm ,P (vj)47Dijkstra算法步驟算法步驟： 第二步：第二步：修改修改T標(biāo)號(hào)。標(biāo)號(hào)。假定假定vi是新產(chǎn)生的是新產(chǎn)生的P標(biāo)號(hào)點(diǎn)，標(biāo)號(hào)點(diǎn)，考察以

41、考察以vi為始點(diǎn)的所有弧段為始點(diǎn)的所有弧段（vi，vj）。）。 如果如果vj是是P標(biāo)號(hào)點(diǎn)，則對(duì)標(biāo)號(hào)點(diǎn)，則對(duì)vj點(diǎn)不再進(jìn)行標(biāo)號(hào)；點(diǎn)不再進(jìn)行標(biāo)號(hào)； 如果如果vj是是T標(biāo)號(hào)點(diǎn)，則將標(biāo)號(hào)點(diǎn)，則將vj的的T標(biāo)號(hào)修改為標(biāo)號(hào)修改為T(vj)=minT(vj),P(vi)+wij其中，方括號(hào)內(nèi)的其中，方括號(hào)內(nèi)的T(vj)代表代表vj點(diǎn)舊的點(diǎn)舊的T標(biāo)號(hào)值；方括號(hào)外的標(biāo)號(hào)值；方括號(hào)外的T(vj)代表代表vj點(diǎn)點(diǎn)新的新的T標(biāo)號(hào)值。標(biāo)號(hào)值。第三步：第三步：產(chǎn)生新的產(chǎn)生新的P標(biāo)號(hào)點(diǎn)。標(biāo)號(hào)點(diǎn)。其原則如下：其原則如下： 在現(xiàn)有的在現(xiàn)有的T標(biāo)號(hào)中將值最小者改為標(biāo)號(hào)中將值最小者改為P標(biāo)號(hào)。標(biāo)號(hào)。重復(fù)以上步驟，直至終點(diǎn)的重復(fù)以上

42、步驟，直至終點(diǎn)的T標(biāo)號(hào)改為標(biāo)號(hào)改為P標(biāo)號(hào)為止。標(biāo)號(hào)為止。第一步：第一步：始點(diǎn)標(biāo)上固定標(biāo)號(hào)始點(diǎn)標(biāo)上固定標(biāo)號(hào)P(vs)=0,其余各點(diǎn)標(biāo)臨時(shí)性標(biāo)號(hào)其余各點(diǎn)標(biāo)臨時(shí)性標(biāo)號(hào) T(vj)= , j 1; 48圖上標(biāo)號(hào)法圖上標(biāo)號(hào)法v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, M, M, M, M, 永久標(biāo)號(hào)永久標(biāo)號(hào)永久標(biāo)號(hào)永久標(biāo)號(hào)臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)v1出發(fā)到出發(fā)到v8去，使總費(fèi)用最小的旅行路線去，使總費(fèi)用最小的旅行路線 j ,P (vj) j, T (vj) M, M, M, 49v1,6圖上標(biāo)號(hào)法圖上標(biāo)號(hào)法v5v223464v3v1v41210 6 1210v8v9v

43、72363v60,0M, M, v1,3M, M, M, v1,1v1,1永久標(biāo)號(hào)永久標(biāo)號(hào)永久標(biāo)號(hào)永久標(biāo)號(hào)臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)v1出發(fā)到出發(fā)到v8去，使總費(fèi)用最小的旅行路線去，使總費(fèi)用最小的旅行路線 j ,P (vj) j, T (vj) 50v1,6圖上標(biāo)號(hào)法圖上標(biāo)號(hào)法v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, M, v1,3M, M, M, 0,0v1,1v4,11v1,3永久標(biāo)號(hào)永久標(biāo)號(hào)臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)v1出發(fā)到出發(fā)到v8去，使總費(fèi)用最小的旅行路線去，使總費(fèi)用最小的旅行路線 j ,P (vj) j, T (vj) 51v5v223464v3v1v4

44、1210 6 1210v8v9v72363v60,0M, v1,1M, M,M, 1,3圖上標(biāo)號(hào)法圖上標(biāo)號(hào)法v4,11v1,3v1,6v3,5v3,5永久標(biāo)號(hào)永久標(biāo)號(hào)臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)v1出發(fā)到出發(fā)到v8去，使總費(fèi)用最小的旅行路線去，使總費(fèi)用最小的旅行路線 j, T (vj) j ,P (vj)52v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, v4,11v1,1M, M, M, v1,3圖上標(biāo)號(hào)法圖上標(biāo)號(hào)法v3,5v2, 6v2, 6永久標(biāo)號(hào)永久標(biāo)號(hào)臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)v1出發(fā)到出發(fā)到v8去，使總費(fèi)用最小的旅行路線去，使總費(fèi)用最小的旅行路線 j, T (vj

45、) j ,P (vj)53v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, v4,11v1,1M, M, v1,3v5,12v5,9v5,9圖上標(biāo)號(hào)法圖上標(biāo)號(hào)法v3,5v2, 6永久標(biāo)號(hào)永久標(biāo)號(hào)臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)v5,10v1出發(fā)到出發(fā)到v8去，使總費(fèi)用最小的旅行路線去，使總費(fèi)用最小的旅行路線 j, T (vj) j ,P (vj)54v5v223464v3v1v41210 6 1210v8v9v72363v60,0v5,10v1,1M, v5, 12 v1,3v5,9v5, 12 v3,5v2, 6圖上標(biāo)號(hào)法圖上標(biāo)號(hào)法永久標(biāo)號(hào)永久標(biāo)號(hào)臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)v5,

46、10v1出發(fā)到出發(fā)到v8去，使總費(fèi)用最小的旅行路線去，使總費(fèi)用最小的旅行路線 j, T (vj) j ,P (vj)55v5v223464v3v1v41210 6 1210v8v9v72363v60,0v5,10v1,1M, v1,3v5, 12 v3,5v2, 6圖上標(biāo)號(hào)法圖上標(biāo)號(hào)法v5,9永久標(biāo)號(hào)永久標(biāo)號(hào)臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)標(biāo)號(hào)結(jié)束標(biāo)號(hào)結(jié)束 反向追蹤反向追蹤v1出發(fā)到出發(fā)到v8去，使總費(fèi)用最小的旅行路線去，使總費(fèi)用最小的旅行路線 j, T (vj) j ,P (vj)56算法適用條件：算法適用條件：Dijkstra算法只適用于全部權(quán)為非負(fù)情況，如果某算法只適用于全部權(quán)為非負(fù)情況，如果某邊上權(quán)為

47、負(fù)的，算法失效。此時(shí)可采用逐次逼近邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近算法。算法。 如右圖所示中按如右圖所示中按dijkstra算算法可得法可得P(v1)=5為從為從vsv1的最短的最短路長(zhǎng)顯然是錯(cuò)誤的，從路長(zhǎng)顯然是錯(cuò)誤的，從vsv2v1路長(zhǎng)只有路長(zhǎng)只有3。v2vsv15-58例例257wij不全不全 0 Dijkstra算法失效，即雖然完整的路線比完整中的片斷距算法失效，即雖然完整的路線比完整中的片斷距離短，但也不能斷定該完整路線一定最短。離短，但也不能斷定該完整路線一定最短。 只能采用最原始的思想，即找出只能采用最原始的思想，即找出vs 到到vj 的所有路線的權(quán)，的所有路線的權(quán)，才能

48、確定才能確定vs 到到vj 的最短距離。具體算法如下：的最短距離。具體算法如下： 設(shè)有向圖中有設(shè)有向圖中有n個(gè)點(diǎn)，從個(gè)點(diǎn)，從vi 到到vj的最短路線不一定從的最短路線不一定從vi直達(dá)直達(dá)vj，也可能經(jīng)過(guò)一個(gè)、兩個(gè)或，也可能經(jīng)過(guò)一個(gè)、兩個(gè)或n2個(gè)中間點(diǎn)才能到達(dá)個(gè)中間點(diǎn)才能到達(dá)vj 。把。把vi直達(dá)直達(dá)vj，稱為走一步，經(jīng)過(guò)一個(gè)中間點(diǎn)稱為走二步，則，稱為走一步，經(jīng)過(guò)一個(gè)中間點(diǎn)稱為走二步，則vi 到到vj的的最短路線最多走最短路線最多走n1 步。步。 58。距距離離。顯顯然然的的最最短短至至?xí)r時(shí)，步步到到達(dá)達(dá)出出發(fā)發(fā)走走為為從從令令sjjsjsjsjstwvvdvvvtvvvd),(),()1()(

49、的的最最短短距距離離。步步到到達(dá)達(dá)出出發(fā)發(fā)走走從從的的最最短短距距離離，可可先先求求出出步步到到達(dá)達(dá)發(fā)發(fā)走走出出求求從從。根根據(jù)據(jù)最最短短路路的的特特性性，步步到到達(dá)達(dá)走走，再再?gòu)膹牡降竭_(dá)達(dá)步步走走的的路路可可分分為為二二段段：先先從從步步到到達(dá)達(dá)出出發(fā)發(fā)走走從從isjsjiisjsvtvvtvvvvtvvtv111 ijistijstwvvdvvd ),(min),()1()(即即的的最最短短距距離離。到到即即為為則則若若jsjstjstjstvvvvdvvdvvd),(),(),()()1()( 592-2-2311v0v2v1v3例例 求下圖所示賦權(quán)有向圖中從求下圖所示賦權(quán)有向圖中從v1

50、到各點(diǎn)的最短路。到各點(diǎn)的最短路。602-2-2311v0v2v1v3基本步驟：基本步驟：(1) 令令t=1,令令d 1(v0，v0)=0, d1(v0，vi)=w(v0 ,vi).解解： d1(v0，v0)=0, d1(v0，v1)=2, d1(v0，v2)=1, d1(v0，v3)=-2. 021-2第一次逼近第一次逼近612-2-2311v0v2v1v3(2) 令令解解： d2(v0，v1)=min d1(v0，v1)+w(v1,v1), d1(v0，v2)+w(v2,v1), d1(v0 , v3)+w(v3, v1) =min2+0,1+, -2+3 =1.021-2當(dāng)當(dāng)vi , vj

51、 為同一個(gè)點(diǎn)時(shí)，有為同一個(gè)點(diǎn)時(shí)，有w(vi ,vj)=0.1d2(v0，v2)=mind1(v0 , v1)+w(v1, v2), d1(v0, v2)+w(v2, v2), d1(v0, v3)+w(v3, v2) =min2-2,1+0, -2+ =0.0d2(v0, v3)=mind1(v0 , v1)+w(v1,v3), d1(v0 , v2)+w(v2,v3), d1(v0 , v3)+w(v3,v3) =min2+,1+1, -2+0 =-2.第二次逼近第二次逼近(3) 若若t+1=p 則停止。否則則停止。否則t=t+1, 轉(zhuǎn)轉(zhuǎn)(2). ijis1tijstwvvdvvd ),(m

52、in),()()(622-2-2311v0v2v1v3解解： d3(v0，v1)=mind2(v0，v1)+w(v1, v1), d2(v0，v2)+w(v2, v1), d2(v0，v3)+w(v3, v1) =min1+0,0+, -2+3 =1.010-2d3(v0，v2)=mind2(v0，v1)+w(v1, v2), d2(v0，v2)+w(v2, v2), d2(v0，v3)+w(v3, v2) =min1+(-2), 1+0, -2+ =-1-1d3(v0，v3)=mind2(v0，v1)+w(v1, v3), d2(v0，v2)+w(v2, v3), d2(v0，v3)+w(v

53、3, v3) =min1+, 0+1, -2+0 =-2.第三次逼近第三次逼近(2) 令令當(dāng)當(dāng)vi , vj 為同一個(gè)點(diǎn)時(shí)，有為同一個(gè)點(diǎn)時(shí)，有w(vi ,vj)=0.(3)若若t+1=p 則停止。否則則停止。否則t=t+1, 轉(zhuǎn)轉(zhuǎn)(2). ijis1tijstwvvdvvd ),(min),()()(632-2-2311v0v2v1v3最后解得最后解得：d3(v0, v1)=1， d3(v0, v2)= -1， d3(v0, v3)= -2.01-1-2即即v0到到v1最短路長(zhǎng)度為最短路長(zhǎng)度為 d3(v0,v1)=1，最短路為，最短路為v0,v3,v1 . 即即v0到到v2最短路長(zhǎng)度為最短路長(zhǎng)

54、度為 d3(v0,v2)= -1,最短路為最短路為v0,v3,v1,v2 . 即即v0到到v3最短路長(zhǎng)度為最短路長(zhǎng)度為 d3(v0,v3)= -2,最短路為最短路為v0,v3 . 64v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57例例: 求求v1 到圖中其他各點(diǎn)的最短路。到圖中其他各點(diǎn)的最短路。65v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1, )(v1, )(v1, )(v1, )走走1步時(shí)步時(shí)66v1v2v3v4v5v6v7v86-1-283-3-5-1211

55、12-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1, )(v1, )(v1, )(v1, )(v3,-5)(v3,-7)(v3,-1)(v2,5)(v4,11)(v4,5)(v2,1)走走2步時(shí)步時(shí)67v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v1, )(v1, )(v3,-5)(v3,-7)(v3,-1)(v2, 1)(v6,0)(v4, 5)(v4,-5)(v6,6)走走3步時(shí)步時(shí)(v5,0)(v2,1)(v4, 1)(v2,-3)(v6,0)(v7,4)68v1v2v3v4v5v6v7v86-1

56、-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v6,6)(v1, )(v3,-5)(v3,-7)(v3,-1)(v2, -3)(v6,0)(v4, -5)走走4步時(shí)步時(shí)(v5,-4)(v2,1)(v4, 1)(v6,0)(v7,-6)(v8,3)(v8, 1)69wijd(t)(vi ,vj ) v1v2v3v4v5v6v7v8t=1 t=2 t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066說(shuō)明：表中空格處為說(shuō)明：表中

57、空格處為+ 。缺點(diǎn)：不能解決負(fù)回路的情況。缺點(diǎn)：不能解決負(fù)回路的情況。70第四節(jié)第四節(jié) 網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流71如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。72不同網(wǎng)絡(luò)中流的意義不同，流本身是一種輸送，可以不同網(wǎng)絡(luò)中流的意義不同，流本身是一種輸送，可以把它們統(tǒng)稱為運(yùn)輸網(wǎng)絡(luò)的流。把它們統(tǒng)稱為運(yùn)輸網(wǎng)絡(luò)的流。許多系統(tǒng)包含了流量問(wèn)題。許多系統(tǒng)包含了流量問(wèn)題。例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(wǎng)例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊

58、系統(tǒng)中有信息絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流，等等流，等等.8 528796653vsv1vtv4v3v273管道網(wǎng)絡(luò)中每邊的最大通過(guò)能力即容量是有限的，實(shí)際流管道網(wǎng)絡(luò)中每邊的最大通過(guò)能力即容量是有限的，實(shí)際流量也并不一定等于容量，上述問(wèn)題就是要討論如何充分利量也并不一定等于容量，上述問(wèn)題就是要討論如何充分利用裝置的能力以取得最好效果用裝置的能力以取得最好效果(流量最大流量最大)，這類問(wèn)題通常，這類問(wèn)題通常稱為稱為最大流問(wèn)題最大流問(wèn)題。50年代福持年代福持(Ford)、富克遜、富克遜(Fulkerson)建立的建立的“網(wǎng)絡(luò)流理網(wǎng)絡(luò)流理論論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。，是網(wǎng)絡(luò)

59、應(yīng)用的重要組成部分。8 528796653vsv1vtv4v3v274st4844122679定義定義 設(shè)賦權(quán)有向圖設(shè)賦權(quán)有向圖D=(V,A), 在在V中指定一個(gè)中指定一個(gè)發(fā)點(diǎn)發(fā)點(diǎn)vs和一個(gè)和一個(gè)收點(diǎn)收點(diǎn)vt , 其他的點(diǎn)叫做其他的點(diǎn)叫做中間點(diǎn)中間點(diǎn)。對(duì)于。對(duì)于D中的每中的每一個(gè)弧一個(gè)弧 (vi ,vj)A, 都有一個(gè)權(quán)都有一個(gè)權(quán) cij 叫做弧的叫做弧的容量容量。我。我們把這樣的圖們把這樣的圖 D 叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)，簡(jiǎn)稱叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)，簡(jiǎn)稱網(wǎng)絡(luò)網(wǎng)絡(luò)，記，記做做D =（V，A，C）。）。4.1 基本概念與基本定理基本概念與基本定理75v3v2v1v4vs（2）（3）（2）（5）（3）（3）（

60、6）（1）（1）（2）fij上圖表示了網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案）弧上的流量上圖表示了網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案）弧上的流量 fij 就是運(yùn)就是運(yùn)輸量例如輸量例如fs1=5, fs2=3, f13=2等等。等等。vt流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧(vi,vj)上的負(fù)載量記為上的負(fù)載量記為fij。若。若fij=0，稱為零流。，稱為零流。76網(wǎng)絡(luò)系統(tǒng)上流的特點(diǎn)：網(wǎng)絡(luò)系統(tǒng)上流的特點(diǎn)：發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必 相等；相等；每一個(gè)中間點(diǎn)的流入量與流出量的代每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零；數(shù)和等于零；1.