圖論及網(wǎng)絡(luò)流

1、 圖的基本概念與基本定理 樹(shù)和最小支撐樹(shù) 最短路問(wèn)題 網(wǎng)絡(luò)系統(tǒng)最大流問(wèn)題 網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題 中國(guó)郵遞員問(wèn)題本章內(nèi)容重點(diǎn)引引 言言 圖論是應(yīng)用非常廣泛的運(yùn)籌學(xué)分支，它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論，信息論，工程技術(shù)，交通運(yùn)輸，經(jīng)濟(jì)管理，電子計(jì)算機(jī)等各項(xiàng)領(lǐng)域。對(duì)于科學(xué)研究，市場(chǎng)和社會(huì)生活中的許多問(wèn)題，可以同圖論的理論和方法來(lái)加以解決。例如，各種通信線(xiàn)路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問(wèn)題，都可以應(yīng)用圖論的方法，簡(jiǎn)便、快捷地加以解決。引引 言言 隨著科學(xué)技術(shù)的進(jìn)步，特別是電子計(jì)算機(jī)技術(shù)的發(fā)展，圖論的理論獲得了更進(jìn)一步的發(fā)展，應(yīng)用更加廣泛。如果將復(fù)雜的工程系統(tǒng)和管理問(wèn)

2、題用圖的理論加以描述，可以解決許多工程項(xiàng)目和管理決策的最優(yōu)問(wèn)題。因此，圖論越來(lái)越受到工程技術(shù)人員和經(jīng)營(yíng)管理人員的重視。引引 言言 1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問(wèn)題。德國(guó)的哥尼斯堡城有一條普雷格爾河，河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接，如圖8.1a所示。引引 言言AB圖8.1 aCD引引 言言 當(dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問(wèn)題，一個(gè)漫步者如何能夠走過(guò)這七座橋，并且每座橋只能走過(guò)一次，最終回到原出發(fā)地。盡管試驗(yàn)者很多，但是都沒(méi)有成功。 為了尋找答案，1736年歐拉將這個(gè)問(wèn)題抽象成圖8.1b所示圖形的一筆畫(huà)問(wèn)題。即能否從某一點(diǎn)開(kāi)始

3、不重復(fù)地一筆畫(huà)出這個(gè)圖形，最終回到原點(diǎn)。歐拉在他的論文中證明了這是不可能的，因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接，不可能將它一筆畫(huà)出，這就是古典圖論中的第一個(gè)著名問(wèn)題。引引 言言圖8.1 bACDB 在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線(xiàn)來(lái)畫(huà)出各式各樣的示意圖。 例8.1:圖8.2是我國(guó)北京、上海、重慶等十四個(gè)城市之間的鐵路交通圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線(xiàn)表示城市之間的鐵路線(xiàn)。諸如此類(lèi)還有城市中的市政管道圖，民用航空線(xiàn)圖等等。1.1.圖的基本概念與基本定理圖的基本概念與基本定理1.1.圖的基本概念與基本定理圖的基本概念與基本定理太原重慶武漢南京徐州

4、連云港上海鄭州石家莊塘沽青島濟(jì)南天津北京圖8.2 例8.2:有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)v1v6表示這六支球隊(duì)，它們之間的比賽情況，也可以用圖反映出來(lái)，已知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.3所示的有向圖反映出來(lái)。1.1.圖的基本概念與基本定理圖的基本概念與基本定理1.1.圖的基本概念與基本定理圖的基本概念與基本定理v3v1v2v4v6v5圖8.3 從以上的幾個(gè)例子可以看出，我們用點(diǎn)和點(diǎn)之間的線(xiàn)所構(gòu)成的圖，反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。一般來(lái)說(shuō)，通常用點(diǎn)表示研究對(duì)象用點(diǎn)與點(diǎn)之間的線(xiàn)表示研究對(duì)象之間的特定關(guān)系。由

5、于在一般情況下，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線(xiàn)的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。1.1.圖的基本概念與基本定理圖的基本概念與基本定理 綜上所述，圖論中的圖是由點(diǎn)和點(diǎn)與點(diǎn)之間的線(xiàn)所組成的。通常，我們把點(diǎn)與點(diǎn)之間不帶箭頭的線(xiàn)叫做邊，帶箭頭的線(xiàn)叫做弧。 如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，那么，稱(chēng)為為無(wú)向圖，記作G =(V，E)，其中V表示圖G的點(diǎn)集合，E表示圖G的邊集合。連接點(diǎn)vi,vjV的邊記作vi,vj，或者vj,vi。 如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱(chēng)為它為有向圖，記作D =(V,A)，其中V 表示有向圖D的點(diǎn)集合，A表示

6、有向圖D的弧集合。一條方向從vi指向vj的弧，記作(vi,vj)。1.1.圖的基本概念與基本定理圖的基本概念與基本定理例如.圖8.4是一個(gè)無(wú)向圖G=（V，E）其中V=v1,v2,v3,v4 E=v1,v2,v2,v1,v2,v3, v3,v4,v1,v4,v2,v4, v3,v31.1.圖的基本概念與基本定理圖的基本概念與基本定理v3v2v1v4圖8.4圖8.5是一個(gè)有向圖D=（V，A）其中V=v1,v2,v3,v4,v5,v6,v7 A=(v1,v2),(v,v3),(v3,v2), (v3,v4),(v2,v4),(v4,v5), (v4,v6),(v,v3),(v5,v4), (v5,v

7、6),(v6,v7)1.1.圖的基本概念與基本定理圖的基本概念與基本定理v7v5v3v4v2v1v6圖8.5 下面介紹一些常用的名詞： 一個(gè)圖G或有向圖D中的點(diǎn)數(shù),記作P(G)或P(D),簡(jiǎn)記作P,邊數(shù)或者弧數(shù),記作q(G)或者q(D),簡(jiǎn)記作q。 如果邊vi,vjE,那么稱(chēng)vi,vj是邊的端點(diǎn)，或者vi,vj是相鄰的。如果一個(gè)圖G中，一條邊的兩個(gè)端點(diǎn)是相同的,那么稱(chēng)為這條邊是環(huán)，如圖8.4中的邊v,v3是環(huán)。如果兩個(gè)端點(diǎn)之間有兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱(chēng)為它們?yōu)槎嘀剡?，如圖8.4中的邊v1,v2 ,v2,v1。一個(gè)無(wú)環(huán)，無(wú)多重邊的圖標(biāo)為簡(jiǎn)單圖，一個(gè)無(wú)環(huán)，有多重邊的圖標(biāo)圖稱(chēng)為多重圖。1.

8、1.圖的基本概念與基本定理圖的基本概念與基本定理 以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱(chēng)為點(diǎn)v的度，記作d(v),如圖84中d(v1)=3， d(v2)=4,d(v3)=4,d(v4)=3。 度為零的點(diǎn)稱(chēng)為弧立點(diǎn)，度為1的點(diǎn)稱(chēng)為懸掛點(diǎn)。懸掛點(diǎn)的邊稱(chēng)為懸掛邊。度為奇數(shù)的點(diǎn)稱(chēng)為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱(chēng)為偶點(diǎn)。1.1.圖的基本概念與基本定理圖的基本概念與基本定理端點(diǎn)的度 d(v)：點(diǎn) v 作為邊端點(diǎn)的個(gè)數(shù)；奇點(diǎn)：d(v)=奇數(shù)； 偶點(diǎn)：d(v)=偶數(shù)；懸掛點(diǎn)：d(v)=1；懸掛邊：與懸掛點(diǎn)連接的邊；孤立點(diǎn)：d(v)=0；空?qǐng)D：E = ，無(wú)邊圖1.1.圖的基本概念與基本定理圖的基本概念與基本定理 定理8.1 所有頂點(diǎn)次

9、數(shù)之和等于所有邊數(shù)的2倍。 定理8.2 在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。 1.1.圖的基本概念與基本定理圖的基本概念與基本定理 圖的連通性： 鏈： 由兩兩相鄰的點(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)； 簡(jiǎn)單鏈：鏈中所含的邊均不相同； 初等鏈：鏈中所含的點(diǎn)均不相同,也稱(chēng)通路；1.1.圖的基本概念與基本定理圖的基本概念與基本定理圈： 除起點(diǎn)和終點(diǎn)外鏈中所含的點(diǎn) 均不相同的閉鏈；回路： 若 v0 vn 分稱(chēng)該鏈為開(kāi)鏈， 否則稱(chēng)為閉鏈或回路；連通圖：圖中任意兩點(diǎn)之間均至少有一 條通路

10、，否則稱(chēng)作不連通圖。1.1.圖的基本概念與基本定理圖的基本概念與基本定理 子圖 設(shè) G1= V1 , E1 ,G2= V2 ,E2 子圖定義：如果 V2 V1 , E2 E1 稱(chēng) G2 是 G1 的子圖； 真子圖：如果 V2 V1 , E2 E1 稱(chēng) G2 是 G1 的真子圖； 部分圖（支撐子圖）：如果 V2 = V1 , E2 E1 稱(chēng) G2 是 G1 的部分圖； 導(dǎo)出子圖： 如果V2 V1, E2=vi,vjvi,vjV2,稱(chēng) G2 是 G1 中由V2 導(dǎo)出的導(dǎo)出子圖。1.1.圖的基本概念與基本定理圖的基本概念與基本定理G G1 11.1.圖的基本概念與基本定理圖的基本概念與基本定理G G

11、1 1= = V V1 1 , E , E1 1 G G2 2真子圖真子圖G G2 2真子圖真子圖1.1.圖的基本概念與基本定理圖的基本概念與基本定理G G2 2= = V V2 2 ,E ,E2 2 子圖、真子圖G G3 3子圖子圖部分圖部分圖（支撐子圖）（支撐子圖）1.1.圖的基本概念與基本定理圖的基本概念與基本定理部分圖：V3 = V1 , E3 E1 稱(chēng) G3 是 G1 的部分圖；G G4 4導(dǎo)出子圖導(dǎo)出子圖G G4 4導(dǎo)出子圖導(dǎo)出子圖1.1.圖的基本概念與基本定理圖的基本概念與基本定理導(dǎo)出子圖：V4 V1,E4=vi,vjvi,vjV4,稱(chēng) G4 是 G1 中由V4 導(dǎo)出的導(dǎo)出子圖。

12、 G G5 5生成樹(shù)生成樹(shù)（部分圖）（部分圖）1.1.圖的基本概念與基本定理圖的基本概念與基本定理 G G6 6G G5 5余樹(shù)余樹(shù)（部分圖）（部分圖）1.1.圖的基本概念與基本定理圖的基本概念與基本定理有向圖：關(guān)聯(lián)邊有方向?。河邢驁D的邊a=(u ,v),起點(diǎn)u,終點(diǎn)v；路：若有從 u 到 v 不考慮方向的鏈,且 各方向一致,則稱(chēng)之為從u到v的路；初等路: 各頂點(diǎn)都不相同的路； 初等回路:u = v 的初等 路; 連通圖： 若不考慮方向 是無(wú)向連通圖; 強(qiáng)連通圖：任兩點(diǎn)有路;1.1.圖的基本概念與基本定理圖的基本概念與基本定理2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 一、樹(shù)及其性質(zhì) 在各種各樣的圖

13、中，有一類(lèi)圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖，這就是樹(shù)。 例8.3：已知有六個(gè)城市，它們之間 要架設(shè)電話(huà)線(xiàn)，要求任意兩個(gè)城市均可以互相通話(huà)，并且電話(huà)線(xiàn)的總長(zhǎng)度最短。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 如果用六個(gè)點(diǎn)v1v6代表這六個(gè)城市，在任意兩個(gè)城市之間架設(shè)電話(huà)線(xiàn)，即在相應(yīng)的兩個(gè)點(diǎn)之間連一條邊。這樣，六個(gè)城市的一個(gè)電話(huà)網(wǎng)就作成一個(gè)圖。由于任意兩個(gè)城市之間均可以通話(huà)，這個(gè)圖必須是連通圖。并且，這個(gè)圖必須是無(wú)圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是六個(gè)城市的一個(gè)電話(huà)網(wǎng)。圖8.8是一個(gè)不含圈的連通圖，代表了一個(gè)電話(huà)線(xiàn)網(wǎng)。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù)圖8.8v6v3v4v2v5v12

14、.2.樹(shù)和最小支撐樹(shù)和最小支撐樹(shù)樹(shù) 定義8.1 一個(gè)無(wú)圈的連通圖叫做樹(shù)。 下面介紹樹(shù)的一些重要性質(zhì)： 定理8.3 設(shè)圖G=（V，E）是一個(gè)樹(shù)P(G) 2，那么圖G中至少有兩個(gè)懸掛點(diǎn)。 定理8.4 圖G=（V，E）是一個(gè)樹(shù)的充要條件是G不含圈，并且有且僅有P-1條邊。 定理8.5 圖G=（V，E）是一個(gè)樹(shù)的充要條件是G是連通圖，并且有且僅有P-1條邊。 定理8.6 圖G是一個(gè)樹(shù)的充分必要條件是任意兩個(gè)頂點(diǎn)之間有且僅有一條鏈。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 從以上定理，不難得出以下結(jié)論： （1）從一個(gè)樹(shù)中任意去掉一條邊，那么剩下的圖不是連通圖，亦即，在點(diǎn)集合相同的圖中，樹(shù)是含邊數(shù)最少的連通圖

15、。 （2）在樹(shù)中不相鄰的兩個(gè)點(diǎn)之間加上一條邊，那么恰好得到一個(gè)圈。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 二.支撐樹(shù) 定義8.2 設(shè)圖K=(V,E)是圖G=(V,E)的一支撐子圖,如果圖K=(V,E)是一個(gè)樹(shù),那么稱(chēng)K是G的一個(gè)支撐樹(shù)。 例如,圖8.10b 是圖8.10a 的一個(gè)支撐樹(shù)。 v6v5v2v3v4v1v6v5v2v3v4v1圖8.10ab2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 顯然,如果圖K=( V, E )是圖G=(V, E)的一個(gè)支撐樹(shù),那么K 的邊數(shù)是p(G)-1，G中不屬于支撐樹(shù)K的邊數(shù)是q(G)-p(G)+1。 定理8.7 一個(gè)圖G有支撐樹(shù)的充要條件是G是連通圖。2.2.樹(shù)和

16、最小支撐樹(shù)樹(shù)和最小支撐樹(shù)證明證明: : 必要性顯然； 充分性: 設(shè)圖G是連通的，若G不含圈，則按照定義，G是一個(gè)樹(shù)，從而G是自身的一個(gè)支撐樹(shù)。若G含圈，則任取G的一個(gè)圈，從該圈中任意去掉一條邊，得到圖G的一支撐子圖G1。若G1不含圈，則G1是G的一個(gè)支撐樹(shù)。若G1仍然含圈，則任取G1的一個(gè)圈，再?gòu)娜χ腥我馊サ粢粭l邊，得到圖G的一支撐子圖G2。依此類(lèi)推，可以得到圖G的一個(gè)支撐子圖GK，且不含圈，從而GK是一個(gè)支撐樹(shù)。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 定理8.7充分性的證明，提供了一個(gè)尋找連通圖支撐樹(shù)的方法叫做“破圈法”。就是從圖中任取一個(gè)圈，去掉一條邊。再對(duì)剩下的圖重復(fù)以上步驟，直到不含圈時(shí)

17、為止，這樣就得到一個(gè)支撐樹(shù)。 例8.4:用破圈法求出圖8-11的一個(gè)支撐樹(shù)。V5V4V2V3V1e6e5e4e3e2e1e7e82.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 取一個(gè)圈(v1,v2,v3,v1)，在一個(gè)圈中去 掉邊e3 。在剩下的圖中，再取一個(gè)圈（v1,v2,v4,v3,v1），去掉邊e4 。再?gòu)娜Γ╲3,v4 v5,v3）中去掉邊e6 。再?gòu)娜?(v1,v2,v5,v4,v3,v1 ）中去掉邊e7， 這樣，剩下的圖不含圈，于是得到一個(gè) 支撐樹(shù)，如圖8.12所示。v2e1e2e5e8v1v3v42.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 三.最小支撐樹(shù)問(wèn)題 定義8.3 如果圖G =（V，E），

18、對(duì)于G中的每一條邊vi,vj，相應(yīng)地有一個(gè)數(shù)Wij，那么稱(chēng)這樣的圖G為賦權(quán)圖，Wij稱(chēng)為邊vi,vj的權(quán)。這里所指的權(quán)，是具有廣義的數(shù)量值。根據(jù)實(shí)際研究問(wèn)題的不同，可以具有不同的含義。例如長(zhǎng)度，費(fèi)用、流量等等。 賦權(quán)圖在圖論及實(shí)際應(yīng)用方面有著重要的地位，被廣泛應(yīng)用于現(xiàn)代科學(xué)管理和工程技術(shù)等領(lǐng)域，最小支撐樹(shù)問(wèn)題就是賦權(quán)圖的最優(yōu)化問(wèn)題之一。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 定義8.4 如果圖T =（V，E）是圖G 的一個(gè)支撐樹(shù)，那么稱(chēng)E上所有邊的權(quán)的和為支撐樹(shù)T 的權(quán)，記作S(T)。 如果圖G 的支撐樹(shù)T* 的權(quán)S(T*)，在G 的所有支撐樹(shù)T 中的權(quán)最小，即S(T*) = minS(T)，那

19、么稱(chēng)T*是G 的最小支撐樹(shù)。 如前所述，在已知的幾個(gè)城市之間聯(lián)結(jié)電話(huà)線(xiàn)網(wǎng)，要求總長(zhǎng)度最短和總建設(shè)費(fèi)用最少，一個(gè)問(wèn)題的 解決可以歸結(jié)為最小支撐樹(shù)問(wèn)題。 再如，城市間交通線(xiàn)的建造等，都可以歸結(jié)為這一類(lèi)問(wèn)題。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù)常用的有破圈法和生長(zhǎng)法（避圈法）兩個(gè)方法： 在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈，則已經(jīng)得到最短樹(shù)或網(wǎng)絡(luò)不存在最短樹(shù)； 去掉該圈中權(quán)數(shù)最大的邊； 反復(fù)重復(fù) 兩步，直到最短樹(shù)。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù)例8.5 某六個(gè)城市之間的道路網(wǎng)如圖8.13a所示，要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話(huà)線(xiàn)網(wǎng)，使得電話(huà)線(xiàn)的總長(zhǎng)度最短。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐

20、樹(shù)v6v5v2v3v4圖8.13av162753544v3v2v1v4v6v5513142圖8.13b2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 解：這個(gè)問(wèn)題的解決就是要求所示賦權(quán)圖8.13a中的最小支撐樹(shù)。用破圈法求解。任取一個(gè)圈，例如（ v1,v2,v3,v1 ），去掉這個(gè)圈中權(quán)最大的邊v1,v3。再取一個(gè)圈（ v3,v5,v2,v3），去掉邊v2,v5。再取一個(gè)圈（ v3,v5,v4,v2,v3），去掉邊v3,v5。再取一個(gè)圈（v5,v6,v4,v5），這個(gè)圈中，有兩條權(quán)最大的邊v5,v6和v4,v6。任意去掉其中的一條，例如v5,v6。這時(shí)得到一個(gè)不含圈的圖，如圖8.13b所示，即是最小支撐

21、樹(shù)。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù) 從網(wǎng)絡(luò)圖中依次尋找權(quán)數(shù)較小的邊，尋找過(guò)程中，節(jié)點(diǎn)不得重復(fù)，即不得構(gòu)成圈。注意在找較小權(quán)數(shù)邊時(shí)不考慮已選過(guò)的邊和可能造成圈的邊。如此反復(fù)進(jìn)行，直到得到最短樹(shù)或證明網(wǎng)絡(luò)不存在最短樹(shù)。2.2.樹(shù)和最小支撐樹(shù)樹(shù)和最小支撐樹(shù)再用“生長(zhǎng)法”求解例8.5解：考慮賦權(quán)圖8.13a，用生長(zhǎng)法求解。任取一點(diǎn)，例如 從v1 取權(quán)較小的邊（v1 ,v2 ）， 再?gòu)膙2 取權(quán)較小的邊（v2 ,v3 ）， 再?gòu)膙3 取權(quán)較小的邊（v3 ,v4 ）， 同理依次?。╲4 ,v5）， （v4 ,v6 ）。這時(shí)也得到了如圖8.13b所示的最小支撐樹(shù)。3.3.最短路徑問(wèn)題最短路徑問(wèn)題一.引

22、言 最短路徑問(wèn)題是圖論中十分重要的最優(yōu)化問(wèn)題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問(wèn)題，比如城市中的管道鋪設(shè)，線(xiàn)路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問(wèn)題。 3.3.最短路徑問(wèn)題最短路徑問(wèn)題例86: 如圖8.14所示的單行線(xiàn)交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線(xiàn)的長(zhǎng)度。現(xiàn)在有一個(gè)人要從v1出發(fā)，經(jīng)過(guò)這個(gè)交通網(wǎng)到達(dá)v8，要尋求是總路程最短的線(xiàn)路。圖8.14v1v4v2v8v7v6v5v96362341023126241013.3.最短路徑問(wèn)題最短路徑問(wèn)題 從v1到v8的路線(xiàn)是很多的。比如從v1出發(fā)，經(jīng)過(guò)v2,v5到達(dá)v8或者從v1出發(fā)，經(jīng)過(guò)v4，v6，

23、v7到達(dá)v8等等。但不同的路線(xiàn)，經(jīng)過(guò)的總長(zhǎng)度是不同的。例如，按照第一個(gè)線(xiàn)路，總長(zhǎng)度是6+1+6=13單位，按照第二個(gè)路線(xiàn)，總長(zhǎng)度是1+10+2+4=17單位。3.3.最短路徑問(wèn)題最短路徑問(wèn)題 一般意義下的最短路問(wèn)題：設(shè)一個(gè)賦權(quán)有向圖D =（V，A），對(duì)于每一個(gè)弧a =（vi,vj），相應(yīng)地有一個(gè)權(quán)wij。vs,vt是D中的兩個(gè)頂點(diǎn)，P是D中從vs到vt的任意一條路，定義路的權(quán)是P 中所有弧的權(quán)的和，記作S(p)。最短路問(wèn)題就是要在所有從vs到vt的路P 中，尋找一個(gè)權(quán)最小的路P0，亦即S(P0)=minS(p)。P0叫做從vs到vs的最短路。P0的權(quán)S(P0)叫做從vs到vt的距離，記作d（v

24、s，vt）。由于D是有向圖，很明顯d（vs，vt）與d（vt，vs）一般不相等。3.3.最短路徑問(wèn)題最短路徑問(wèn)題 二.Dijkstra算法 下面介紹在一個(gè)賦權(quán)有向圖中尋求最短路的方法Dijkstra算法，它是在1959年提出來(lái)的。目前公認(rèn)，在所有的權(quán)wij 0時(shí)，這個(gè)算法是尋求最短路問(wèn)題最好的算法。并且，這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。3.3.最短路徑問(wèn)題最短路徑問(wèn)題Dijkstra算法的基本思想是從vs出發(fā)，逐步向外尋找最短路。在運(yùn)算過(guò)程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄一個(gè)數(shù)，叫做一個(gè)點(diǎn)的標(biāo)號(hào)。它或者表示從vs到該點(diǎn)的最短路權(quán)（叫做P 標(biāo)號(hào)），或者表示從vs到該點(diǎn)最

25、短路權(quán)的上界（叫做T 標(biāo)號(hào)）。算法的每一步是去修改T 標(biāo)號(hào)，把某一個(gè)具有T 標(biāo)號(hào)的點(diǎn)改變?yōu)榫哂蠵 標(biāo)號(hào)的點(diǎn)，使圖D 中具有P 標(biāo)號(hào)的頂點(diǎn)多一個(gè)。這樣，至多經(jīng)過(guò)P -1步，就可求出從vs到各點(diǎn)vj的最短路。 3.3.最短路徑問(wèn)題最短路徑問(wèn)題 以例1為例說(shuō)明這個(gè)基本思想。在例1中，S=1。因?yàn)閃ij 0，d（v1,v1）=0。這時(shí)，v1是具有P標(biāo)號(hào)的點(diǎn)?，F(xiàn)在看從v1出發(fā)的三條?。╲1,v2），（v1,v3）和（v1,v4）。如果一個(gè)人從v1出發(fā)沿（v1,v2）到達(dá)v2，這時(shí)的路程是d（v1,v1）+w12=6單位。如果從v1出發(fā)，沿（v1,v3）到達(dá)v3，則是d（v1,v1）+w13=3單位。同理

26、，沿（v1,v4）到達(dá)v4，是d（v1,v1）+w14=1單位。因此，他從v1出發(fā)到達(dá)v4的最短路必是（v1,v4），d（v1,v4）=1。這是因?yàn)閺膙1到達(dá)v4的任一條路P，假如不是（v1,v4），則必先沿（v1,v2）到達(dá)v2，或者沿（v1,v3）到達(dá)v3，而這時(shí)的路程已是6或者3單位。例1說(shuō)明： 看從v1出發(fā)的三條弧（v1,v2），（v1,v3）和（v1,v4），mind(v1,v1)+w12 ,d(v1,v1)+w13 , d(v1,v1)+w14 = d（v1,v4）=1。P(V4)v2v8v7v6v5v963623410231262410P(V1)13.3.最短路徑問(wèn)題最短路徑問(wèn)題

27、 由于所有的權(quán)wij 0，因此，不論他如何再?gòu)膙2或者v3到達(dá)v4，所經(jīng)過(guò)的總路程都不會(huì)比1少，于是就有d（v1,v4）=1。這樣就使V4變成具有P標(biāo)號(hào)的點(diǎn)?，F(xiàn)在看從v1和v4指向其余點(diǎn)的弧。如上所述，從V1出發(fā)，分別沿（v1,v2），（v1,v3）到達(dá)v2，v3，經(jīng)過(guò)的路程是6或者3單位。從v4出發(fā)沿（v4,v6）到達(dá)v6，經(jīng)過(guò)的路程是d（v1,v4）+w46=1+10=11單位。而mind（v1,v1）+w12，d（v1,v1）+w13，d（v1,v4）+w46=d（v1,v1）+w13=3單位。根據(jù)同樣的理由，可以斷定，從V1到達(dá)V3的最短路是（v1,v3），d（v1,v3）=3。這樣，

28、又使點(diǎn)v3變?yōu)榫哂蠵 標(biāo)號(hào)的點(diǎn)，不斷重復(fù)以上過(guò)程，就可以求出從vs到達(dá)任一點(diǎn)vj的最短路。例1說(shuō)明： 再看從v1和v4指向其余點(diǎn)的弧, mind（v1,v1）+w12，d（v1,v1）+w13，d（v1,v4）+w46=d（v1,v1）+w13=3 。P(V4)v2v8v7v6v5v963623410231262410P(V1)P(V3)13.3.最短路徑問(wèn)題最短路徑問(wèn)題 在下述的Dijkstra算法中，以P，T 分別表示某一個(gè)點(diǎn)的P 標(biāo)號(hào)，T 標(biāo)號(hào)。Si表示在第i步時(shí)，具有P 標(biāo)號(hào)點(diǎn)的集合，為了在算出從vs到各點(diǎn)的距離的同時(shí)，也找出從vs到各點(diǎn)的最短路，于是，給每一個(gè)點(diǎn)v一個(gè)值。當(dāng)算法結(jié)束時(shí)

29、，如果(v)= m，則表示在從vs到v 的最短路上，v 的前一個(gè)點(diǎn)是vm。如果(v)=M，則表示在圖D 中不含有從vs 到達(dá)v 的路。(v)=0，表示v=vs。 Dijkstra算法的步驟如下：3.3.最短路徑問(wèn)題最短路徑問(wèn)題 開(kāi)始（開(kāi)始（i i=0=0） 令令S S0 0=v vs s ，P P（v vs s）=0=0，( (v vs s)=0)=0，對(duì)每，對(duì)每一個(gè)一個(gè)v v v vs s，令，令T T（v v）=+=+，( (v v)=)=M M ，令令k k= =s s； （1 1）如果如果S Si i= =V V，則算法結(jié)束，對(duì)每一個(gè)，則算法結(jié)束，對(duì)每一個(gè)v S Si i，d d（vs

30、,v）= =P P（v）。否則轉(zhuǎn)入）。否則轉(zhuǎn)入（2 2）；）； （2 2）考察每一個(gè)使（考察每一個(gè)使（v vi i,v,vj j） A A，且，且v vj j不不屬于屬于S Si i的點(diǎn)的點(diǎn)v vj j，如果，如果T T( (v vj j)P(vP(vk k)+)+w wkjkj ，則把則把T T(v(vj j) )改變?yōu)楦淖優(yōu)镻 P( (v vk k)+)+w wkjkj，把，把( (v vj j) )改改變?yōu)樽優(yōu)閗 k，否則轉(zhuǎn)入（，否則轉(zhuǎn)入（3 3）；）；3.3.最短路徑問(wèn)題最短路徑問(wèn)題 （3）令(vji)=minT(vj)vjSi，如果T(vji)+，則把vji的T 標(biāo)號(hào)改變?yōu)镻 標(biāo)號(hào)P

31、(vji)=T(vji)，令Si+1=Sivji，k=ji，把i換成i+1，轉(zhuǎn)入（1）；否則結(jié)束。 這時(shí)，對(duì)每一個(gè)vSi，d(vs,v)=P(v)。對(duì)每一個(gè)v不屬于Si，d（vs,v）=T（v）。3.3.最短路徑問(wèn)題最短路徑問(wèn)題 現(xiàn)在用Dijkstra算法求例1中從vs到各個(gè) 點(diǎn) 的 最 短 路 ， 此 時(shí)S= 1 .i= 0 ：S0=v1,P(v1)=0,(v1)=0,T(vi)=+, (vi)=m,i=2,3,9,k=1。 （2）因?yàn)椋╲1,v2）A，v2不屬于S0，P(v1)+w12w32+P(v3)，將T(v2)改變?yōu)?P(v3)+w32=5，(v2)改變?yōu)?。 （3）在所有的T標(biāo)號(hào)中

32、，T(v2)=5最小， 于 是令P(v2)=5，S3=v1,v4,v3，k=2。 i=3： （2）將T(v5)改變?yōu)镻(v2)+w25=6，(v5) 改變?yōu)?。 （3）在所有的T標(biāo)號(hào)中，T(v5)=6最小，于 是令P(v5)=6，S4=v1,v4,v3，k=5。 i=4:3.3.最短路徑問(wèn)題最短路徑問(wèn)題 （2）將T(v6)，T(v7)，T(v8)分別改變?yōu)?0， 9，12，將(v0)，(v7)，(v8)改變?yōu)?。 （3）在所有的T標(biāo)號(hào)中，T(v7)=9最小，于 是令P(v7)=9，S5=v1,v4,v3,v2,v5,v7，v=7。 i=5： （2）（v7,v8）A，v8不屬于S5， 但T(v8

33、)=0,只要將Dijkstra算法中的“（2）看作每一個(gè)使（vk,vj）A，且vjSj的點(diǎn)vj”改變?yōu)椤埃?）看作每一個(gè)使vk,vjE，且vjSj的點(diǎn)vj”而其他的條件不變，同樣可以求出從vs到各點(diǎn)的最短路（對(duì)于無(wú)向圖叫做最短鏈）。 作為習(xí)題，將例8.6中所示的賦權(quán)有向圖的箭頭去掉，然后求出無(wú)向圖中從vs到各點(diǎn)的最短路。3.3.最短路徑問(wèn)題最短路徑問(wèn)題 下面證明Dijkstra算法的正確性。只要證明每一個(gè)點(diǎn)vSi,P()是從vs到v的最短路權(quán)，即P()=d(vs.v). 證:用數(shù)學(xué)歸納法。當(dāng)i=0時(shí)，結(jié)論顯然成立。假設(shè)i=n時(shí)，結(jié)論成立。看i=n+1的情形，由于Sn+1=Snvjn,所以只要證

34、明P(vjn)=d(vs,vj)根據(jù)算法，vj m是最具有最小T標(biāo)號(hào)的點(diǎn)，即Tn(vjn)=minTn(vj)，其中vjSm.這里，用Tn()表示當(dāng)i=n時(shí)，執(zhí)行步驟（3）時(shí)點(diǎn)的T標(biāo)號(hào)。設(shè)H是圖D中任意一條從vs到vjn的路。 3.3.最短路徑問(wèn)題最短路徑問(wèn)題 因?yàn)関sSn,而vjn Sn,所以從vs出發(fā)，沿H必存在一條弧，其始點(diǎn)屬于Sn，而終點(diǎn)不屬于Sn。令 （vr, vl） 是 第 一 條 這 樣 的 弧 ， 于 是H= (vsvr, vlvj n) ,s(H) =S( (vs, vr)+wrl+S(vlvjn)。由歸納假設(shè)，P(vr)是從v s到v r的 最 短 路 權(quán) ， 于 是 ，

35、有S（H）=P(vr)+wrl+S(vlvjn).根據(jù)算法中的T標(biāo)號(hào)修改規(guī)則，因?yàn)関rSn,vl Sn,故P（vr）+wrl=Tn(vjn),且S（vlvjn）=所以S（H）=Tn(vjn)+S(vl,vjn)=Tn(vjn).這樣，就證明了Tn(vjn)是從vs到vjn的最短權(quán)。根據(jù)算法，P(vjn)=Tn(vjn),于是就有P(vjn)=d(vs,vjn).3.3.最短路徑問(wèn)題最短路徑問(wèn)題 Dijkstra算法僅適合于所有的權(quán)wij=0的情形。如果當(dāng)賦權(quán)有向圖中存在有負(fù)權(quán)弧時(shí)，則該算法失效。例如圖8.16中，根據(jù)Dijkstra算法，可以得出從v1到v2最短路權(quán)是2，但是這顯然不對(duì)，因?yàn)閺?/p>

36、v1到v2的最短路是（v1,v3,v2）,權(quán)是-1。v1v3v222-3圖8.163.3.最短路徑問(wèn)題最短路徑問(wèn)題 下面介紹當(dāng)賦權(quán)有向圖中，存在負(fù)權(quán)弧時(shí)，尋求最短路的方法: 首先，設(shè)從任一點(diǎn)首先，設(shè)從任一點(diǎn)v vi i到任一點(diǎn)到任一點(diǎn)v vj j都有一條弧，如果在圖都有一條弧，如果在圖 D D 中，（中，（v vi i,v,vj j）不屬于）不屬于A A, ,則添加弧則添加弧( (v vi i,v,vj j),),并且令并且令w wijij=+.=+. 很明顯，從vs到vj的最短路是從vs點(diǎn)出發(fā)，沿著這條路到某個(gè)點(diǎn)vi的再沿弧(vi,vj)到點(diǎn)vj。顯然，從vs到vi的這條路必定是從vs到vi

37、的最短路。否則從vs到vj的這條路將不是最短路。于是，從從v vs s到到v vj j的距離的距離d d( (v vs s,v,vj j) )滿(mǎn)足以下條件滿(mǎn)足以下條件， d(vs,vj)=mind(vs,vi)+wij, i i=1,p, p=p(D). 3.3.最短路徑問(wèn)題最短路徑問(wèn)題 這個(gè)關(guān)系式的解這個(gè)關(guān)系式的解d d( (v vs s,v,v1 1) )d d( (v vs s,v,vp p).).可利用如可利用如下的下的 遞推公式遞推公式 求解求解 d d(1)(1)( (v vs s,v,vj j)=)=w wsjsj, ,j j=1=1p.p. d d(t)(t)( (v vs s

38、,v,vj j)=min)=mind d(t-1)(t-1)( (v vs s,v,vi i)+ )+ w wijij, , t t=2,3=2,3 i i 當(dāng)計(jì)算到第當(dāng)計(jì)算到第K K步時(shí)步時(shí), ,對(duì)一切的對(duì)一切的j j=1=1p p, ,有有 d d(k)(k)( (v vs s,v,vj j)=)=d d(k-1)(k-1)( (v vs s,v,vj j) ) 則則d d(k)(k)( (v vs s,v,vj j),),j j=1=1p p, ,就是從就是從v vs s到各點(diǎn)到各點(diǎn)v vj j的的最短路徑的權(quán)最短路徑的權(quán)。 設(shè)C是賦權(quán)函數(shù)有向圖D中的一個(gè)回路。如果回路C的權(quán)S（C）是負(fù)

39、數(shù)那么稱(chēng)C是D中的一個(gè)負(fù)回路。 可以證明以下的結(jié)論： 1.如果賦權(quán)有向圖D不含有負(fù)回路，那么從vs到任一點(diǎn)的最短路至多包含P-2個(gè)中間點(diǎn)，并且必可取為初等路。 2.如果賦權(quán)有向圖D不含有負(fù)回路，那么上述遞推算法至多經(jīng)過(guò)P-1次迭代必收斂，可以求出從vs到各個(gè)點(diǎn)的最短路權(quán)。 3.如果上述算法經(jīng)過(guò)P-1次迭代，還存在在著某個(gè)j，使得d(p)(vs,vj)d(p-1)(vs,vj),那么D中含有負(fù)回路。這時(shí)，不存在從vs到vj的路（權(quán)無(wú)界）。結(jié)論3.3.最短路徑問(wèn)題最短路徑問(wèn)題例例8 87: 7: 在如圖在如圖8.178.17所示的賦權(quán)有向圖中求所示的賦權(quán)有向圖中求從從v v1 1到各點(diǎn)的最短路。到

40、各點(diǎn)的最短路。 解解: :利用上述遞推公式，將求解結(jié)果列出利用上述遞推公式，將求解結(jié)果列出如表如表8.188.18所示。所示。 可以看出，當(dāng)可以看出，當(dāng)t t=4=4時(shí)，有時(shí)，有 d d(t)(t)( (v vs s,v,vj j)=)=d d(t-1)(t-1)( (v vs s,v,vj j) ) j j=1=18.8.因此，表因此，表中的最后一列，就是從中的最后一列，就是從v v1 1到到v v1 1,v,v2,.,2,.,v v8 8的最的最短路權(quán)短路權(quán)。3.3.最短路徑問(wèn)題最短路徑問(wèn)題v8v2v4v7v5v1v3v6圖8.1711111123355223678終點(diǎn) 起點(diǎn)V1V2V3V

41、4V5V6V7V8t=1t=2t=3t=4V10-1-23 0000V2602-1-5-5-5V3 -30-51-2-2-2-2V4802 3-7-7-7V5 -101-3-3V61017-1-1-1V7-105-5-5V8-3-5066wij d(t)(vs,vj) 3.3.最短路徑問(wèn)題最短路徑問(wèn)題 為了求出從v1到各個(gè)點(diǎn)的最短路，一般采用反向追蹤的方法：如果已知d(vi,vj),那么尋求一個(gè)點(diǎn)vk,使得d(vs,vk)+wkj=d(vs,vj),然后記錄下(vk,vj).在看d(vs,vk),尋求一個(gè)點(diǎn)vi,使得d(vs,vi)+wij=d(vs,vk)依次類(lèi)推，一直到達(dá)為止。這樣，從vs

42、到vj的最短路是（vs,vi,vk,vj） 在本例中，有表8.18知，d(v1,v8)=6,由于)d(v1,v6)+w6 8=(-1)+7記錄下v6.由于d(v1,v3)+w3 6=d(v1,v6),j記錄下v3.由于d(v1,v1)+w13=d(v1,v3),于是，從v1到v8的最短路是(v1,v3,v6,v8)。 1.狄克斯拉方法 適用于滿(mǎn)足所有權(quán)系數(shù)大于等于0（lij0）的網(wǎng)絡(luò)最短路問(wèn)題，能求出起點(diǎn) v1 到所有其他點(diǎn) vj 的最短距離； 2.海斯方法 基本思想是在最短路線(xiàn)上任意兩點(diǎn)間路線(xiàn)也是最短路線(xiàn)。利用 vi 到vj 的一步距離求出 vi 到 vj 的兩步距離再求出 vi 到 vj

43、的四步距離經(jīng)有限次迭代可求出 vi 到vj 的最短距離；3.3.最短路徑問(wèn)題最短路徑問(wèn)題 3.福德方法 適用于有負(fù)權(quán)系數(shù)，但無(wú)負(fù)回路的有向或無(wú)向網(wǎng)絡(luò)的最短路問(wèn)題，能求出起點(diǎn) v1 到所有其它點(diǎn) vj 的最短距離。 4 .4 .網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 一 引言 在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問(wèn)題。例如鐵路運(yùn)輸系統(tǒng)中的車(chē)輛流，城市給排水系統(tǒng)的水流問(wèn)題等等。而網(wǎng)絡(luò)系統(tǒng)流最大流問(wèn)題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問(wèn)題，它對(duì)于解決生產(chǎn)實(shí)際問(wèn)題起著十分重要的作用。4 .4 .網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題圖8.19vtv3v2v1v4vs1735108611453

44、C Cijij圖圖8.198.19是一個(gè)網(wǎng)絡(luò)。每一個(gè)弧旁邊的權(quán)就是對(duì)應(yīng)的容量是一個(gè)網(wǎng)絡(luò)。每一個(gè)弧旁邊的權(quán)就是對(duì)應(yīng)的容量（最大通過(guò)能力）（最大通過(guò)能力）。要求指定一個(gè)運(yùn)輸方案，使得從要求指定一個(gè)運(yùn)輸方案，使得從v vs s到到v vt t的貨運(yùn)量最大，這是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題的貨運(yùn)量最大，這是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題二二 基本概念基本概念 定義定義8.5 8.5 設(shè)一個(gè)賦權(quán)有向圖設(shè)一個(gè)賦權(quán)有向圖D D = =（V,AV,A）, ,在在v v中指定一個(gè)中指定一個(gè)發(fā)點(diǎn)發(fā)點(diǎn)v vs s和一個(gè)和一個(gè)收點(diǎn)收點(diǎn)v vt t, ,其他的其他的點(diǎn)叫做中間

45、點(diǎn)。對(duì)于點(diǎn)叫做中間點(diǎn)。對(duì)于D D中的每一個(gè)?。ㄖ械拿恳粋€(gè)?。╲ vi i,v,vj j）A A, ,都有一個(gè)權(quán)都有一個(gè)權(quán) c cijij 叫做叫做弧的容量弧的容量。我們把。我們把這樣的圖這樣的圖 D D 叫做一個(gè)叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)網(wǎng)絡(luò)系統(tǒng)，簡(jiǎn)稱(chēng)網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)網(wǎng)絡(luò)，記做記做D D = =（V V，A A，C C）。）。 網(wǎng)絡(luò)網(wǎng)絡(luò)D D上的流上的流，是指定義在弧集合，是指定義在弧集合A A上的一個(gè)上的一個(gè)函數(shù)函數(shù)f f=f f( (v vi i,v,vj j)=)=f fijij f f( (v vi i,v,vj j)=)=f fijij叫做叫做弧在弧在( (v vi i,v,vj j) )上的流量上

46、的流量。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）f fijij圖8.20網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案）每一個(gè)弧上的流量fij就是運(yùn)輸量例如fs1=5,fs2=3,f13=2等等vt 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)上流流的特點(diǎn)：(1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等；(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零；(3)每一個(gè)弧上的流量不能超過(guò)它的最大通過(guò)能力（即容量）。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 定義定義8.6 8.6 網(wǎng)絡(luò)上的一個(gè)流f叫做可行流，

47、如果f滿(mǎn)足以下條件 （1）容量條件容量條件：對(duì)于每一個(gè)?。╲i,vj）A,有 0 0 f fijij c cijij. . （2）平衡條件平衡條件： 對(duì)于發(fā)點(diǎn)vs，有fsj-fjs=v(f) 對(duì)于收點(diǎn)vt，有ftj-fjt=-v(f) 對(duì)于中間點(diǎn)，有fij-fji=0 其中發(fā)點(diǎn)的總流量（或收點(diǎn)的總流量） v v( (f f) )叫做這個(gè)可行流的流量叫做這個(gè)可行流的流量。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0,就是滿(mǎn)足以上條件的可行流。 網(wǎng)絡(luò)系統(tǒng)中最大流問(wèn)題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流f,其流量v(f)達(dá)到最大值。 設(shè)流f

48、=fij是網(wǎng)絡(luò)D上的一個(gè)可行流。我們把D中fij=cij的弧叫做飽和弧飽和弧，fij0的弧為非零流非零流弧弧，fij=0的弧叫做零流弧零流弧。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 設(shè)是網(wǎng)絡(luò)D中連接發(fā)點(diǎn)s和收點(diǎn)vt的一條鏈。定義鏈的方向是從vs到vt，于是鏈上的弧被分為兩類(lèi)：一是弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做+。二是弧的方向與鏈的方向相反，叫做后向弧，后向弧的集合記做-。在下圖（圖8.19與8.20合并圖）中，(v4,v3)是飽和弧，其他的弧是非飽和弧，并且都是非零流弧。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6,3）（1

49、1,6）（4,1）（5,1）（3,2）f fijij如圖，在鏈（v vs s,v,v1 1,v,v2 2,v,v3 3,v,v4 4,v,vt t) )中， + +=(=(v vs s,v,v1 1),(),(v v1 1,v,v2 2),(),(v v2 2,v,v3 3),(),(v v4 4,v,vt t),), - -=(=(v v4 4,v,v3 3).).vt 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題增廣鏈增廣鏈，如果鏈滿(mǎn)足以下條件： 1在?。╲i,vj）+上，有0=fijcij,即+中的每一條弧是非飽和弧。 2在?。╲i,vj）-上，有0fij=cij,即-中的每一條弧

50、是非零流弧。 例如在圖8.20中，鏈=（vs,v1,v2,v3,v4,vt）就是一條增廣鏈。 設(shè)圖D=(V，A，C)，點(diǎn)集S,TV,ST=中。將起點(diǎn)在S，終點(diǎn)在T 的所有弧作成集合，記做（S，T）。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 定義8.8 設(shè)一個(gè)網(wǎng)絡(luò)D=（V，A，C）。如果點(diǎn)集V被剖分為兩個(gè)非空集合V1和V1，發(fā)點(diǎn)vsV1,收點(diǎn)vtV1,那么將弧集（V1,V1）叫做是分離vs和vt的截集。 定義8.9 設(shè)一個(gè)截集（V1, V1）.將截集（V1,V1）中所有的弧的容量的和叫做截集的截量，記做s(V1,V1),亦即s(V1,V1)=cij。 (vi,vj)(V1,V1) 4

51、. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 下面的事實(shí)是顯然的：一個(gè)網(wǎng)絡(luò)D中，任何一個(gè)可行流f的流量v(f)都小于或等于這個(gè)網(wǎng)絡(luò)中任何一個(gè)截集(V1,V1)的截量。并且，如果網(wǎng)絡(luò)上的一個(gè)可行流f*和網(wǎng)絡(luò)中的一個(gè)截集（V1*,V1*），滿(mǎn)足條件v*(f*)=c(V1*,V1*),那么f*一定是D上的最大流，而（V1*,V1*）一定是D的所有的截集中截量最小的一個(gè)（即最小截集）。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 定理8.8網(wǎng)絡(luò)中的一個(gè)可行流f*是最大流的充分必要條件是，不存在關(guān)于f*的增廣鏈。 定理8.9在一個(gè)網(wǎng)絡(luò)D中，最大流的流量等于分離vs和vt的最小截集的截量。 定

52、理定理8.88.8實(shí)際上提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最實(shí)際上提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法：如果網(wǎng)絡(luò)大流的方法：如果網(wǎng)絡(luò)D D中有一個(gè)可行流中有一個(gè)可行流f f，只要，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f f的增廣鏈的增廣鏈 。如果。如果沒(méi)有增廣鏈，那么沒(méi)有增廣鏈，那么f f一定是最大流。如有增廣鏈，一定是最大流。如有增廣鏈，那么可以按照定理那么可以按照定理8.98.9，不斷改進(jìn)和增大可行流，不斷改進(jìn)和增大可行流f f的流量，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。的流量，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。4.4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 三標(biāo)號(hào)法 從網(wǎng)絡(luò)中的一個(gè)可行

53、流f出發(fā)（如果D中沒(méi)有f，可以令f是零流），運(yùn)用標(biāo)號(hào)法，經(jīng)過(guò)標(biāo)號(hào)過(guò)程和調(diào)整過(guò)程，可以得到網(wǎng)絡(luò)中的一個(gè)最大流。 用給頂點(diǎn)標(biāo)號(hào)的方法來(lái)定義V1*.在標(biāo)號(hào)過(guò)程中，有標(biāo)號(hào)的頂點(diǎn)是V1*中的點(diǎn)，沒(méi)有標(biāo)號(hào)的點(diǎn)不是V1*中的點(diǎn)。如果vt有了標(biāo)號(hào)，表示存在一條關(guān)于f的增廣鏈。如果標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，并且vt未被標(biāo)號(hào)，則表示不存在關(guān)于f的增廣鏈。這樣，就得到了網(wǎng)絡(luò)中的一個(gè)最大流和最小截集。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 1 標(biāo)號(hào)過(guò)程 在標(biāo)號(hào)過(guò)程中，網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號(hào)點(diǎn)（分為已檢查和未檢查兩種）?；蛘呤俏礃?biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的。以便找出

54、增廣鏈。第二個(gè)標(biāo)號(hào)是為了用來(lái)確定增廣鏈上的調(diào)整量。 標(biāo)號(hào)過(guò)程開(kāi)始，先給vs標(biāo)號(hào)（0，+）。這時(shí)，vs是標(biāo)號(hào)未檢查的點(diǎn)，其他都是未標(biāo)號(hào)點(diǎn)。一般地，取一個(gè)標(biāo)號(hào)未檢查點(diǎn)vi，對(duì)一切未標(biāo)號(hào)點(diǎn)vj： 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 1）如果在?。╲i,vj）上，fij0,那么給vj標(biāo)號(hào)（-vi, l(vj)）.其中l(wèi)(vj)=minl(vi),cij-fij.這時(shí)，vj成為標(biāo)號(hào)未檢查點(diǎn)。 于是vi成為標(biāo)號(hào)已檢查的點(diǎn)。重復(fù)以上步驟，如果所有的標(biāo)號(hào)都已經(jīng)檢查過(guò)，而標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，則標(biāo)號(hào)法結(jié)束。這時(shí)的可行流就是最大流。但是，如果vt被標(biāo)上號(hào)，表示得到一條增廣鏈，轉(zhuǎn)入下一步調(diào)整過(guò)程。

55、2.調(diào)整過(guò)程 首先按照vt和其他的點(diǎn)的第一個(gè)標(biāo)號(hào)，反向追蹤，找出增廣鏈。例如，令vt的第一個(gè)標(biāo)號(hào)是vk，則?。╲k,vt）在上。再看vk的第一個(gè)標(biāo)號(hào)，若是vi，則弧(vi,vk)都在上。依次類(lèi)推，直到vs為止。這時(shí)，所找出的弧就成為網(wǎng)絡(luò)D的一條增廣鏈。取調(diào)整量= l(vt),即vt的第二個(gè)標(biāo)號(hào)， 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 fij+，當(dāng)(vi,vj)+ 令fij= fij-，當(dāng)(vi,vj)- 其他不變 再去掉所有的標(biāo)號(hào)，對(duì)新的可行流f=fij,重新進(jìn)行標(biāo)號(hào)過(guò)程，直到找到網(wǎng)絡(luò)D的最大流為止。 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題4.4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題

56、網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt圖8.21 例8.8: 求圖8.21的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù)表示（cij,fij）。 解.用標(biāo)號(hào)法。 1.標(biāo)號(hào)過(guò)程。 （1）首先給vs標(biāo)號(hào)（0，+） （2）看vs:在弧(vs,v2)上,fs2=cs3=3,不具備標(biāo)號(hào)條件。在弧(vs,v1)上,fs1=10,故給v2標(biāo)號(hào)（-v1, l(v2)）,其中l(wèi)(v2)=minl(v1),f21=min4,1=1. 4. 4.網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題 （4）看v2:在弧（v2,v4）上，f

57、24=30,故給v3標(biāo)號(hào)（-v2，l(v3),其中l(wèi)(l(v3)=minl(v2),f32=min1,1=1。 （5）在v3,v4中任意選一個(gè)，比如v3,在?。╲3,vt）上，f3 t= 1 =0，網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題，是指要尋求一個(gè)最大流f，并且流的總費(fèi)用b(f)=bijfij達(dá)到最小。 （Vi,Vj）A5.5.網(wǎng)絡(luò)系統(tǒng)的網(wǎng)絡(luò)系統(tǒng)的 最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題 在一個(gè)網(wǎng)絡(luò)D中，當(dāng)沿可行流f的一條增廣鏈，以調(diào)整量=1改進(jìn)f，得到的新可行流f的流量，有v(f)=v(f)+1，而此時(shí)總費(fèi)用b(f)比b(f)增加了b(f)-b(f)=bij(fij-fij)- bij(fij-fi

58、j)= bij-bij + - + - 將bij-bij叫做這條增廣鏈的費(fèi)用。5.5.網(wǎng)絡(luò)系統(tǒng)的網(wǎng)絡(luò)系統(tǒng)的 最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題5.5.網(wǎng)絡(luò)系統(tǒng)的網(wǎng)絡(luò)系統(tǒng)的 最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題 如果可行流在流量為v(f)的所有可行流中的費(fèi)用最小，并且是關(guān)于f的所有增廣鏈中的費(fèi)用最小的增廣鏈。那么沿增廣鏈調(diào)整可行流f，得到的新可行流f，也是流量為v(f)的所有可行流中的最小費(fèi)用流。 依次類(lèi)推，當(dāng)f是最大流時(shí)，就是所要求的最小費(fèi)用最大流。 顯然，零流f=0是流量為0的最小費(fèi)用流。一般地，尋求最小費(fèi)用流，總可以從零流f=0開(kāi)始。下面的問(wèn)題是：如果已知f是流量為v(f)的最小費(fèi)用流，

59、那么就要去尋找關(guān)于f的最小費(fèi)用增廣鏈。 對(duì)此，重新構(gòu)造一個(gè)賦權(quán)有向圖M(f)，其頂點(diǎn)是原網(wǎng)絡(luò)D的頂點(diǎn)，而將D中的每一條弧(vi,vj)變成兩個(gè)相反方向的?。╲i,vj）和(vj,vi)，并且定義M(f)中弧的權(quán)wij為：5.5.網(wǎng)絡(luò)系統(tǒng)的網(wǎng)絡(luò)系統(tǒng)的 最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題 bij,當(dāng)fij0wij= +,當(dāng)fij=0 并且將權(quán)為+的弧從M(f)中略去。 即當(dāng) 0 fij =3。 當(dāng)q=3時(shí)，顯然G是歐拉圖。假設(shè)q=n時(shí)成立，看q=m+1的情形：由于G是無(wú)奇點(diǎn)的連通圖，并且G的點(diǎn)數(shù)p=3，因此存在三個(gè)點(diǎn)，v,w,使得，v,w,vE。從G中去掉邊，v,w,v，增加新的邊，w，得到一個(gè)

60、新的多重圖G1，G1有q-1條邊，且仍不含奇點(diǎn)，G1至多有兩個(gè)分圖。6.6.中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題 若G1是連通的，則由歸納假設(shè)，G1有歐拉圈C1。把C1中的邊w,換成,v,w,v，即是G中的歐拉圈。若G1有兩個(gè)分圖G1，G1，令v在G1中。由歸納假設(shè)，G1，G1分別有歐拉圈C1，C1，把C1”中的邊,w換成,v,C1及v,w即是G中的歐拉圈。 推論 一個(gè)多重連通圖G有歐拉鏈的充分必要條件是G有且僅有兩個(gè)奇點(diǎn)。 這個(gè)推論的證明留給讀者作為習(xí)題。 從這個(gè)定理的證明可以看出，識(shí)別一個(gè)連通圖能否一筆畫(huà)出的條件是它是否有奇點(diǎn)。若有奇點(diǎn)，就不能一筆畫(huà)出。若沒(méi)有奇點(diǎn)，就能夠一筆畫(huà)出，并回到原出發(fā)地。