運(yùn)籌學(xué)8圖與網(wǎng)絡(luò)分析.ppt
《運(yùn)籌學(xué)8圖與網(wǎng)絡(luò)分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《運(yùn)籌學(xué)8圖與網(wǎng)絡(luò)分析.ppt（167頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第八章圖與網(wǎng)絡(luò)分析,主要內(nèi)容：8.1圖的基本概念與基本定理8.2樹和最小支撐樹8.3最短路問題8.4最小費(fèi)用流問題8.5最大流問題8.6網(wǎng)絡(luò)計(jì)劃8.7中國(guó)郵遞員問題8.7指派問題,8.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é)研究，市場(chǎng)和社會(huì)生活中的許多問題，可以同圖論的理論和方法來加以解決。例如，各種通信線路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問題，都可以應(yīng)用圖論的方法，簡(jiǎn)便、快捷地加以解決。,隨著科學(xué)技術(shù)的進(jìn)步，特別是電子計(jì)算機(jī)技術(shù)的發(fā)展，圖論的理論獲得了更進(jìn)一步的發(fā)展，應(yīng)用更加廣泛。如果將復(fù)雜的工程系統(tǒng)和管理問題用圖的理論加以描述，可以解決許多工程項(xiàng)目和管理決策的最優(yōu)問題。因此，圖論越來越受到工程技術(shù)人員和經(jīng)營(yíng)管理人員的重視。,關(guān)于圖的第一篇論文是瑞士數(shù)學(xué)家歐拉（E.Euler）在1736年發(fā)表的解決“哥尼,斯堡”七橋難題的論文；,德國(guó)的哥尼斯堡城有一條普雷格爾河，河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接，（見圖8.1a）當(dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問題，一個(gè)漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。盡管試驗(yàn)者很多，但是都沒有成功。為了尋找答案，1736年歐拉將這個(gè)問題抽象成圖8.1b所示圖形的一筆畫問題。,,,哥尼斯堡七橋問題,圖8.1a,A,B,C,D,,哥尼斯堡七橋問題可簡(jiǎn)化為以下圖形其中的四個(gè)頂點(diǎn)都是奇頂點(diǎn),,,,,,,,A,B,C,D,圖8.1b,,即能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)。歐拉在他的論文中證明了這是不可能的，因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個(gè)著名問題。,在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的示意圖。,例8.1圖8.2是我國(guó)北京、上海、重慶等十四個(gè)城市之間的鐵路交通圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。,圖8.2,例8.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.3所示的有向圖反映出來,,圖8.3,,從以上的幾個(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)之間線的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。,綜上所述，圖論中的圖是由點(diǎn)和點(diǎn)與點(diǎn)之間的線所組成的。通常，我們把點(diǎn)與點(diǎn)之間不帶箭頭的線叫做邊，帶箭頭的線叫做弧。如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，那么，稱為無向圖，記作G=(V，E)，其中V表示圖G的點(diǎn)集合，E表示圖G的邊集合。連接點(diǎn)vi,vj?V的邊記作[vi,vj]，或者[vj,vi]。如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱為它為有向圖，記作D=(V,A)，其中V表示有向圖D的點(diǎn)集合，A表示有向圖D的弧集合。一條方向從vi指向vj的弧，記作(vi,vj)。,例如.圖8.4是一個(gè)無向圖G=（V，E），其中V={v1,v2,v3,v4}E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]},圖8.4,,圖8.5是一個(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,v4),(v5,v6),(v6,v7)},圖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,vj]?E,那么稱vi,vj是邊的端點(diǎn)，或者vi,vj是相鄰的。如果一個(gè)圖G中，一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán)，如圖8.4中的邊[v3,v3]是環(huán)。如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叄鐖D8.4中的邊[v1,v2],[v2,v1]。一個(gè)無環(huán)，無多重邊的圖稱為簡(jiǎn)單圖，一個(gè)無環(huán)，有多重邊的圖稱為多重圖。,,,以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的度，記作d(v),如圖8—4中d(v1)=3，d(v2)=4,d(v3)=4,d(v4)=3。度為零的點(diǎn)稱為弧立點(diǎn)，度為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。端點(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=?，無邊圖,V={v1,v2,v3,v4,v5,v6,v7},d(v1)=3;d(v2)=5;,d(v3)=4;d(v4)=4;,d(v5)=1;d(v6)=3;,d(v7)=0,其中v5為懸掛點(diǎn)，v7為孤立點(diǎn)。,,定理8.1所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。證明：因?yàn)樵谟?jì)算各個(gè)點(diǎn)的度時(shí)，每條邊被它的兩個(gè)端點(diǎn)個(gè)用了一次。,,,定理8.2在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。證明：設(shè)V1，V2分別是圖G中奇點(diǎn)和偶點(diǎn)的集合，由定理8.1，有,因?yàn)槭桥紨?shù)，也是偶數(shù)，因此,也必是偶數(shù)，從而V1中的點(diǎn)數(shù)是偶數(shù)。,,圖的連通性：鏈：由兩兩相鄰的點(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)。記作（v0,v1,v2，,v3,…,vn-1,vn）簡(jiǎn)單鏈：鏈中所含的邊均不相同；初等鏈：鏈中所含的點(diǎn)均不相同,也稱通路；,圈：若v0≠vn則稱該鏈為開鏈，否則稱為閉鏈或回路或圈；,簡(jiǎn)單圈：如果在一個(gè)圈中所含的邊均不相同初等圈：除起點(diǎn)和終點(diǎn)外鏈中所含的點(diǎn)均不相同的圈；連通圖：圖中任意兩點(diǎn)之間均至少有一條通路，否則稱為不連通圖。,初等鏈:(v1,v2,v3,v6,v7,v5),初等圈：(v1,v2,v3,v5,v4,v1),,簡(jiǎn)單圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4),簡(jiǎn)單鏈：(v1,v2,v3,v4,v5,v3),以后除特別聲明，均指初等鏈和初等圈。,連通圖,,子圖定義：如果V2?V1,E2?E1稱G2是G1的子圖；真子圖：如果V2?V1,E2?E1稱G2是G1的真子圖；部分圖：如果V2=V1,E2?E1稱G2是G1的部分圖或支撐子圖；導(dǎo)出子圖：如果V2?V1,E2={[vi,vj]∣vi,vj?V2},稱G2是G1中由V2導(dǎo)出的導(dǎo)出子圖。,設(shè)G1=[V1,E1],G2=[V2,E2],,,,,,,,,,,G1,,,,,,,,,,,,,,,G2真子圖,,,,,,,,,,,G3子圖部分圖,,,,,,,,,,,G4導(dǎo)出子圖,,,,,,,,,,,G5生成樹,,,,,,,,,,,,,,G6G5余樹,,有向圖：關(guān)聯(lián)邊有方向?。河邢驁D的邊a=(u,v),起點(diǎn)u,終點(diǎn)v；路：若有從u到v不考慮方向的鏈,且各方向一致,則稱之為從u到v的路；初等路:各頂點(diǎn)都不相同的路；初等回路:u=v的初等路;連通圖：若不考慮方向是無向連通圖;強(qiáng)連通圖：任兩點(diǎn)有路;,8.2樹和最小支撐樹,一、樹及其性質(zhì)在各種各樣的圖中，有一類圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖，這就是樹。例8.3已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長(zhǎng)度最短。,如果用六個(gè)點(diǎn)v1…v6代表這六個(gè)城市，在任意兩個(gè)城市之間架設(shè)電話線，即在相應(yīng)的兩個(gè)點(diǎn)之間連一條邊。這樣，六個(gè)城市的一個(gè)電話網(wǎng)就作成一個(gè)圖。表示任意兩個(gè)城市之間均可以通話，這個(gè)圖必須是連通圖。并且，這個(gè)圖必須是無圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是六個(gè)城市的一個(gè)電話網(wǎng)。圖8.8是一個(gè)不含圈的連通圖，代表了一個(gè)電話線網(wǎng)。,,圖8.8,,,,,,v6,v3,v4,v2,v5,v1,,定義8.1一個(gè)無圈的連通圖叫做樹。下面介紹樹的一些重要性質(zhì)：定理8.3設(shè)圖G=（V，E）是一個(gè)樹P(G)≥2，那么圖G中至少有兩個(gè)懸掛點(diǎn)。定理8.4圖G=（V，E）是一個(gè)樹的充要條件是G不含圈，并且有且僅有P-1條邊。定理8.5圖G=（V，E）是一個(gè)樹的充要條件是G是連通圖，并且有且僅有p–1條邊。定理8.6圖G是一個(gè)樹的充分必要條件是任意兩個(gè)頂點(diǎn)之間有且僅有一條鏈。,,從以上定理，不難得出以下結(jié)論：（1）從一個(gè)樹中任意去掉一條邊，那么剩下的圖不是連通圖，亦即，在點(diǎn)集合相同的圖中，樹是含邊數(shù)最少的連通圖。（2）在樹中不相鄰的兩個(gè)點(diǎn)之間加上一條邊，那么恰好得到一個(gè)圈。,二.支撐樹,定義8.2設(shè)圖K=(V,EI)是圖G=(V,E)的,一支撐子圖，如果圖K=(V,EI)是一個(gè)樹,那么稱K是G的一個(gè)支撐樹。例如,圖8.10b是圖8.10a的一個(gè)支撐樹,圖8.10,顯然,如果圖K=(V,EI)是圖G=(V,E)的一個(gè)支撐樹,那么K的邊數(shù)是p(G)-1，G中不屬于支撐樹K的邊數(shù)是q(G)-p(G)+1。定理8.7一個(gè)圖G有支撐樹的充要條件是G是連通圖。證明：充分性:設(shè)圖G是連通的，若G不含圈，則按照定義，G是一個(gè)樹，從而G是自身的一個(gè)支撐樹。若G含圈，則任取G的,一個(gè)圈，從該圈中任意去掉一條邊，得到圖G的一支撐子圖G1。若G1不含圈，則G1是G的一個(gè)支撐樹。若G1仍然含圈，則任取G1的一個(gè)圈，再?gòu)娜χ腥我馊サ粢粭l邊，得到圖G的一支撐子圖G2。依此類推，可以得到圖G的一個(gè)支撐子圖GK，且不含圈，從而GK是一個(gè)支撐樹。,定理8.7充分性的證明，提供了一個(gè)尋找連通圖支撐樹的方法叫做“破圈法”。就是從圖中任取一個(gè)圈，去掉一條邊。再對(duì)剩下的圖重復(fù)以上步驟，直到不含圈時(shí)為止，這樣就得到一個(gè)支撐樹。例8.4用破圈法求出圖8-11的一個(gè)支撐樹。,,圖8-11,取一個(gè)圈(v1,v2,v3,v1)，在一個(gè)圈中去掉邊e3。在剩下的圖中，再取一個(gè)圈（v1,v2,v4,v3,v1），去掉邊e4。再?gòu)娜Γ╲3,v4v5,v3）中去掉邊e6。再?gòu)娜?v1,v2,v5,v4,v3,v1）中去掉邊e7，這樣，剩下的圖不含圈，于是得到一個(gè)支撐樹，如圖8.12所示。,,圖8.12,三.最小支撐樹問題定義8.3如果圖G=（V，E），對(duì)于G中的每一條邊[vi,vj]，相應(yīng)地有一個(gè)數(shù)Wij，那么稱這樣的圖G為賦權(quán)圖，Wij稱為邊[vi,vj]的權(quán)。這里所指的權(quán)，是具有廣義的數(shù)量值。根據(jù)實(shí)際研究問題的不同，可以具有不同的含義。例如長(zhǎng)度，費(fèi)用、流量等等。賦權(quán)圖在圖論及實(shí)際應(yīng)用方面有著重要的地位，被廣泛應(yīng)用于現(xiàn)代科學(xué)管理和工程技術(shù)等領(lǐng)域，最小支撐樹問題就是賦權(quán)圖的最優(yōu)化問題之一。,設(shè)G=（V，E）是一個(gè)連通圖，G的每一條[vi,vj]對(duì)應(yīng)一個(gè)非負(fù)的權(quán)Wij。定義8.4如果圖T=（V，EI）是圖G的一個(gè)支撐樹，那么稱EI上所有邊的權(quán)的和為支撐樹T的權(quán)，記作S(T)。如果圖G的支撐樹T*的權(quán)S(T*)，在G的所有支撐樹T中的權(quán)最小，即S(T*)=minTS(T)，那么稱T*是G的最小支撐樹。,如前所述，在已知的幾個(gè)城市之間聯(lián)結(jié)電話線網(wǎng)，要求總長(zhǎng)度最短和總建設(shè)費(fèi)用最少，一個(gè)問題的解決可以歸結(jié)為最小支撐樹問題。再如，城市間交通線的建造等，都可以歸結(jié)為這一類問題。,下面介紹尋求最小支撐樹的方法--破圈法。在給定的連通圖中任取一個(gè)圈，去掉權(quán)最大的一條邊，如果有兩條以上權(quán)最大的邊，則任意,去掉一條。在剩下的圖中，重復(fù)以上步驟，直到得到一個(gè)不含圈的連通圖為止，這個(gè)圖便是最小支撐樹。例8.5某六個(gè)城市之間的道路網(wǎng)如圖8.13a所示，要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使得電話線的總長(zhǎng)度最短。,圖8.13a,圖8.13b,解：這個(gè)問題的解決就是要求所示賦權(quán)圖8.13a中的最小支撐樹。用破圈法求解。任取一個(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所示，即是最小支撐樹。關(guān)于破圈法正確性的證明略去。,例用破圈法求出下圖中的最小支撐樹,破圈法和生長(zhǎng)法兩個(gè)方法：,（1）在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈，則已經(jīng)得到最短樹或網(wǎng)絡(luò)不存在最短樹；,（2）去掉該圈中權(quán)數(shù)最大的邊；,反復(fù)重復(fù)①②兩步，直到最短樹。,1.破圈法,從網(wǎng)絡(luò)圖中任意節(jié)點(diǎn)開始尋找與該節(jié)點(diǎn)關(guān)聯(lián)的權(quán)數(shù)最小的邊，得到另一節(jié)點(diǎn)后，再?gòu)倪@個(gè)新節(jié)點(diǎn)開始尋找與該節(jié)點(diǎn)關(guān)聯(lián)的權(quán)數(shù)最小的另一邊……。注意尋找過程中，節(jié)點(diǎn)不得重復(fù)，即在找最小權(quán)數(shù)邊時(shí)不考慮已選過的邊,反復(fù)進(jìn)行，直到得到最短樹或證明網(wǎng)絡(luò)不存在最短樹。,2.成長(zhǎng)法,例用成長(zhǎng)法求出下圖中的最小支撐樹（最短樹）,一.引言最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問題。,8.3最短路問題,例8．6如圖8.14所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線的長(zhǎng)度?，F(xiàn)在有一個(gè)人要從v1出發(fā)，經(jīng)過這個(gè)交通網(wǎng)到達(dá)v8，要尋求是總路程最短的線路。,圖8.14,1,從v1到v8的路線是很多的。比如從v1出發(fā)，經(jīng)過v2,v5到達(dá)v8或者從v1出發(fā)，經(jīng)過v4，v6，v7到達(dá)v8等等。但不同的路線，經(jīng)過的總長(zhǎng)度是不同的。例如，按照第一個(gè)線路，總長(zhǎng)度是6+1+6=13單位，按照第二個(gè)路線，總長(zhǎng)度是1+10+2+4=17單位。從這個(gè)例子中，可以給出一般意義下的最短路問題。設(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)。最短路問題就是要在所有從vs到vt的路P0中，尋找一個(gè)權(quán)最小的路P0，亦即S(P0)=minS(p)。P0叫做從vs到vs的最短路。P0的權(quán)S(P0)叫做從vs到vt的距離，記作d（vs，vt）。由于D是有向圖，很明顯d（vs，vt）與d（vt，vs）一般不相等。,二.Dijkstra算法下面介紹在一個(gè)賦權(quán)有向圖中尋求最短路的方法——Dijkstra算法，它是在1959年提出來的。目前公認(rèn)，在所有的權(quán)wij≥0時(shí)，這個(gè)算法是尋求最短路問題最好的算法。并且，這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。,Dijkstra算法的基本思想是從vs出發(fā)，逐步向外尋找最短路。在運(yùn)算過程中，與每個(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)最短路權(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)過P-1步，就可求出從vs到各點(diǎn)vj的最短路。,以例1為例說明這個(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ā)的三條弧（v1,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單位。同理，沿（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單位。由于所有的權(quán)wij≥0，因此，不論他如何再?gòu)膙2或者v3到達(dá)v4，所經(jīng)過的總路程都不會(huì)比1少，于是就有d（v1,v4）=1。這樣就使v4變成具有P標(biāo)號(hào)的點(diǎn)。現(xiàn)在看從v1和v4指向其余點(diǎn)的弧。如上所述，從v1出發(fā)，分別沿（v1,v2），（v1,v3）到達(dá)v2，v3，經(jīng)過,的路程是6或者3單位。從v4出發(fā)沿（v4,v6）到達(dá)v6，經(jīng)過的路程是d（v1,v4）+w46=1+10=11單位。而min{d（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。這樣，又使點(diǎn)v3變?yōu)榫哂蠵標(biāo)號(hào)的點(diǎn)，不斷重復(fù)以上過程，就可以求出從vs到達(dá)任一點(diǎn)vj的最短路。,(0,0),(6,1),(3,1),(1,1),(0,0),(3,1),(1,1),(6,1),(11,4),(0,0),(3,1),(1,1),(5,3),(11,4),(0,0),(3,1),(1,1),(5,3),(11,4),(6,2),(0,0),(3,1),(1,1),(5,3),(10,5),(6,2),(9,5),(12,5),(0,0),(3,1),(1,1),(5,2),(10,5),(6,2),(9,5),(12,5),(0,0),(3,1),(1,1),(5,2),(10,5),(6,2),(9,5),(12,5),從v1到v8的最短路的長(zhǎng)度為：12從v1到v8的最短路線為：,v8,v5,,v2,,v1,,步驟：,1、給起點(diǎn)一個(gè)永久標(biāo)號(hào)（0，0）。永久標(biāo)號(hào)用下劃線表示；標(biāo)號(hào)中的第一個(gè)數(shù)表示從起點(diǎn)到該點(diǎn)的距離；第二個(gè)數(shù)表示該點(diǎn)的前面沒有點(diǎn)了。,2、修改非永久標(biāo)號(hào)點(diǎn)vi的臨時(shí)標(biāo)號(hào)為(a,b),其中a為以vi為終點(diǎn)的弧，如果其起點(diǎn)為永久標(biāo)號(hào)，則求其永久標(biāo)號(hào)的第一個(gè)數(shù)與弧長(zhǎng)的和，如果這樣的和有多個(gè)，則取最小值。b為前一個(gè)點(diǎn)的下標(biāo)。,3、在臨時(shí)標(biāo)號(hào)中取第一個(gè)標(biāo)號(hào)的最小值，將該標(biāo)號(hào)該為永久標(biāo)號(hào)，再返回到2步,三、含有負(fù)權(quán)的最短路的求法,例：求從v1到v8的最短路,0,-1,-2,3,0,-5,-2,-7,1,-1,5,0,-5,-2,-7,-3,-1,-5,6,0,-5,-2,-7,-3,-1,-5,6,從v1到v8的最短路的長(zhǎng)度為：6從v1到v8的最短路線為：,v8,v6,,v3,,v1,,8.4最小費(fèi)用流問題,一引言在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等等。而網(wǎng)絡(luò)系統(tǒng)流最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對(duì)于解決生產(chǎn)實(shí)際問題起著十分重要的作用。,圖8.19是聯(lián)結(jié)某個(gè)起始地vs和目的地vt的交通運(yùn)輸網(wǎng)，每一條弧vi旁邊的權(quán)cij表示這段運(yùn)輸線的最大通過能力，貨物經(jīng)過交通崗從vs運(yùn)送到vt.要求指定一個(gè)運(yùn)輸方案，使得從vs到vt的貨運(yùn)量最大，這個(gè)問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。,問題描述連通網(wǎng)絡(luò)G(V,A)有m個(gè)節(jié)點(diǎn),n條弧,弧eij上的流量上界為cij,求從起始節(jié)點(diǎn)vs到終點(diǎn)vt的最大流量。,,圖8.19,,,二基本概念定義8.5設(shè)一個(gè)賦權(quán)有向圖D=（V,A）,在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)弧（vi,vj）∈A,都有一個(gè)權(quán)叫做弧的容量。我們把這樣的圖D叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)，簡(jiǎn)稱網(wǎng)絡(luò)，記做D=（V，A，C）。網(wǎng)絡(luò)D上的流，是指定義在弧集合A上的一個(gè)函數(shù)f={f(vi,vj)}={fjj}f(vi,vj)=fij叫做弧(vi,vj)上的流量。,,,例如圖8.19就是一個(gè)網(wǎng)絡(luò)。每一個(gè)弧旁邊的權(quán)就是對(duì)應(yīng)的容量（最大通過能力）cij.圖8.20表示的就是這個(gè)網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案），每一個(gè)弧上的流量fij就是運(yùn)輸量。例如fs1=5,fs2=3,f13=2等等。對(duì)于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流，有幾個(gè)顯著的特點(diǎn)：(1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等。(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零。(3)每一個(gè)弧上的流量,,不能超過它的最大通過能力（即容量）于是有：,圖8.20,定義8.6網(wǎng)絡(luò)上的一個(gè)流f叫做可行流，如果f滿足以下條件（1）容量條件：對(duì)于每一個(gè)?。╲i,vj）∈A,有0?fij?cij.（2）平衡條件：,對(duì)于發(fā)點(diǎn)vs,有,對(duì)于收點(diǎn)vt,有,對(duì)于中間點(diǎn)，有,任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流f,其流量v(f)達(dá)到最大值。設(shè)流f={fij}是網(wǎng)絡(luò)D上的一個(gè)可行流。我們把D中fij=cij的弧叫做飽和弧，fij0的弧為非零流弧，fij=0的弧叫做零流弧.,在圖8.20中，(v4,v3)是飽和弧，其他的弧是非飽和弧，并且都是非零流弧。設(shè)μ是網(wǎng)絡(luò)D中連接發(fā)點(diǎn)νs和收點(diǎn)vt的一條鏈。定義鏈的方向是從νs到vt，于是鏈μ上的弧被分為兩類：一類是弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做μ+。二類是弧的方向與鏈的方向相反，叫做后向弧，,后向弧的集合記做μ–。例如在圖8.19中，在鏈（vs,v1,v2,v3,v4,vt)中，μ+={vs,v1,(v1,v2),(v2,v3),(v4,vt)},μ–={(v4,v3)}.,增廣鏈：如果鏈μ滿足以下條件：1．在弧（vi,vj）∈μ+上，有0?fij下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
14.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 運(yùn)籌學(xué) 網(wǎng)絡(luò)分析
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請(qǐng)勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://m.italysoccerbets.com/p-3257496.html