運籌學第7章圖與網(wǎng)絡優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

12、vj,vi。一條方向從一條方向從vi指向指向vj的弧，記作的弧，記作 (vi, vj)。14例如例如.圖圖8-4是一個無向圖是一個無向圖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是一個有向圖是一個有向圖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 端點端點,關聯(lián)邊關聯(lián)邊,相鄰相鄰若邊若邊e可表示為可表示為e=vi,vj，稱，稱vi和和vj是是邊邊e的的端點端點，稱邊，稱邊e為點為點vi或或vj的的關聯(lián)關聯(lián)邊邊。若點。若點vi，vj與同一條邊關聯(lián)，稱與同一條邊關聯(lián)，稱點點vi和和vj相鄰相鄰；若邊；若邊ei和和ej具有公共具有公共的端點，稱的端點，稱邊邊ei和和ej相鄰相鄰。在一個圖的幾何實現(xiàn)中，在一個圖的幾何實現(xiàn)中，兩條邊的交點可能不是圖的頂點兩條邊的交點可能不是圖的頂點。例如例如4e1e2e3e

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

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

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

17、稱通路；稱通路； 鏈，圈，初等鏈，初等圈，簡單鏈（圈）鏈，圈，初等鏈，初等圈，簡單鏈（圈）20 鏈鏈中間點中間點初等鏈初等鏈圈圈初等圈初等圈簡單圈簡單圈 v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9 在上圖中在上圖中,(v1, v2 , v3 , v4 , v5 , v3 , v6 , v7)是一條簡單鏈是一條簡單鏈, 但不是初等鏈但不是初等鏈在該鏈中在該鏈中, v2, v3, v4, v5, v3, v6是中間點是中間點(v1 , v2 , v3 , v6 , v7)是一條初等鏈是一條初等鏈(v1 , v2 , v3 , v4 , v1)是一個初等圈是一個初等圈(v4 ,

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

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

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

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

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

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

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

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

26、圖為為不不連連通通，則則存存在在假假設設GGGGGS21顯然成立。顯然成立。時時當當,2p 條邊。條邊。時，命題成立，即含有時，命題成立，即含有設設1nnp .,11vGnp記記為為中中含含有有懸懸掛掛點點時時，當當 ，個點的樹，由假設知：個點的樹，由假設知：是是因為因為nvGpnvGqnvG )(, 1)(111。，從而，從而，為懸掛點，所以為懸掛點，所以又因為又因為1)(1)()(11 pnGqGqvGqv充分性：充分性：只需證明只需證明G為連通的即可。為連通的即可。為為樹樹。所所以以不不含含圈圈因因為為iiGsiG,), 2 , 1( . 1)( iiiipGqpG個點，則由必要性知個點

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

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

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

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

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

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

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

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

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

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

37、的權的權: P中所有弧的權之和，即中所有弧的權之和，即 w(P) wij ；(4)求一條權最小的路求一條權最小的路P0: w(P0) =min w(P) 上式中對上式中對D中所有從中所有從vs到到vt的路的路P取最小，稱取最小，稱P0是從是從vs到到vt的最的最短路。短路。 路路P0的權稱為從的權稱為從vs到到vt的距離，記為的距離，記為d(vs，vt)。 顯然，顯然，d(vs，vt)與與d(vt，vs)不一定相等。不一定相等。45最短路問題的特性最短路問題的特性 若序列若序列 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 若求起點若求起點A到任一點到任一點G的最短路線，可先求的最短路線，可先求A到到G點的相鄰點的相鄰前點的最短距離，在此基礎上求出前點的最短距離，在此基礎上求出A到到G點的最短距離。這樣點的最短距離。這樣最終一定能求出起點到終點的最短距離。最終一定能求出起點到終點的最短距離。46 基本思想基本思想：從始點從始點vs出發(fā)出

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

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

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

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

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

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

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

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

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

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

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

50、到各點的最短路。到各點的最短路。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當當vi , vj

51、 為同一個點時，有為同一個點時，有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, 轉轉(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) 令令當當vi , vj 為同一個點時，有為同一個點時，有w(vi ,vj)=0.(3)若若t+1=p 則停止。否則則停止。否則t=t+1, 轉轉(2). ijis1tijstwvvdvvd ),(min),()()(632-2-2311v0v2v1v3最后解得最后解得：d3(v0, v1)=1， d3(v0, v2)= -1， d3(v0, v3)= -2.01-1-2即即v0到到v1最短路長度為最短路長度為 d3(v0,v1)=1，最短路為，最短路為v0,v3,v1 . 即即v0到到v2最短路長度為最短路長

54、度為 d3(v0,v2)= -1,最短路為最短路為v0,v3,v1,v2 . 即即v0到到v3最短路長度為最短路長度為 d3(v0,v3)= -2,最短路為最短路為v0,v3 . 64v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57例例: 求求v1 到圖中其他各點的最短路。到圖中其他各點的最短路。65v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1, )(v1, )(v1, )(v1, )走走1步時步時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步時步時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步時步時(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步時步時(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說明：表中空格處為說明：表中

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

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

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

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