2022-6-291運(yùn)籌學(xué)運(yùn)籌學(xué)OPERATIONS RESEARCH2022-6-292第六章第六章 圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析n圖的基本概念與模型圖的基本概念與模型 n樹(shù)圖和圖的最小部分樹(shù)樹(shù)圖和圖的最小部分樹(shù) n最短路問(wèn)題最短路問(wèn)題 n網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流n最小費(fèi)用最大流最小費(fèi)用最大流 2022-6-293BACD 當(dāng)?shù)氐木用駸嶂杂诋?dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問(wèn)題：這樣一個(gè)問(wèn)題：一個(gè)漫步者如何能夠一個(gè)漫步者如何能夠走過(guò)這七座橋，并且走過(guò)這七座橋，并且每座橋只能走過(guò)一次，每座橋只能走過(guò)一次，最終回到原出發(fā)地。最終回到原出發(fā)地。盡管試驗(yàn)者很多，盡管試驗(yàn)者很多，但是都沒(méi)有成功。但是都沒(méi)有成功。哥尼斯堡的七橋問(wèn)題哥尼斯堡的七橋問(wèn)題2022-6-294 為了尋找答案，為了尋找答案，17361736年歐年歐拉把陸地縮為一點(diǎn)，把橋作為拉把陸地縮為一點(diǎn)，把橋作為連接點(diǎn)的邊，將這個(gè)問(wèn)題抽象連接點(diǎn)的邊，將這個(gè)問(wèn)題抽象成圖形的一筆畫(huà)問(wèn)題。即成圖形的一筆畫(huà)問(wèn)題。即能否能否從某一點(diǎn)開(kāi)始不重復(fù)地一筆畫(huà)從某一點(diǎn)開(kāi)始不重復(fù)地一筆畫(huà)出這個(gè)圖形，最終回到原點(diǎn)。出這個(gè)圖形，最終回到原點(diǎn)。歐拉在他的論文中證明了這是歐拉在他的論文中證明了這是不可能的，因?yàn)檫@個(gè)圖形中每不可能的，因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接，不可能將它一筆畫(huà)出，這就，不可能將它一筆畫(huà)出，這就是古典圖論中的第一個(gè)著名問(wèn)是古典圖論中的第一個(gè)著名問(wèn)題。題。ABCDBACD2022-6-295 在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏趯?shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線(xiàn)來(lái)畫(huà)出各式各樣間的關(guān)系，常常在紙上用點(diǎn)和線(xiàn)來(lái)畫(huà)出各式各樣的示意圖。的示意圖。例例 有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)有六支球隊(duì)進(jìn)行足球比賽，我們分別用點(diǎn)v v1 1vv6 6 表示這六支球隊(duì)，它們之間的比賽情況表示這六支球隊(duì)，它們之間的比賽情況，也可以用圖反映出來(lái)，已知，也可以用圖反映出來(lái)，已知v v1 1 隊(duì)?wèi)?zhàn)勝隊(duì)?wèi)?zhàn)勝v v2 2 隊(duì)，隊(duì)，v v2 2 隊(duì)?wèi)?zhàn)勝隊(duì)?wèi)?zhàn)勝v v3 3隊(duì)，隊(duì)，v v3 3 隊(duì)?wèi)?zhàn)勝隊(duì)?wèi)?zhàn)勝v v5 5 隊(duì)，如此等等。這隊(duì)，如此等等。這個(gè)勝負(fù)情況，可以用下圖所示的有向圖反映出個(gè)勝負(fù)情況，可以用下圖所示的有向圖反映出來(lái)。來(lái)。2022-6-2961 1 圖的基本概念與模型圖的基本概念與模型 圖（圖（graphgraph）是由一些結(jié)點(diǎn)或頂點(diǎn)（是由一些結(jié)點(diǎn)或頂點(diǎn)（ nodes or nodes or vertices vertices ）以及連接點(diǎn)的邊（以及連接點(diǎn)的邊（edgesedges）構(gòu)成。記做構(gòu)成。記做G G = V,E = V,E ，其中其中 V V 是頂點(diǎn)的集合，是頂點(diǎn)的集合，E E 是邊的集合。是邊的集合。 給圖中的點(diǎn)和邊賦以具體的含義和權(quán)值，我們稱(chēng)給圖中的點(diǎn)和邊賦以具體的含義和權(quán)值，我們稱(chēng)這樣的圖為這樣的圖為網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖（賦權(quán)圖）（賦權(quán)圖）1.1 1.1 基本概念基本概念2022-6-297圖中的點(diǎn)用圖中的點(diǎn)用 v v 表示，邊用表示，邊用 e e 表示，對(duì)每條邊可用表示，對(duì)每條邊可用它所聯(lián)結(jié)的點(diǎn)表示，如圖，則有：它所聯(lián)結(jié)的點(diǎn)表示，如圖，則有：e1 = v1 , v1，e2 = v1 , v2或或e2= v2 , v12022-6-298 用點(diǎn)和點(diǎn)之間的線(xiàn)所構(gòu)成的圖，反映實(shí)際生產(chǎn)和用點(diǎn)和點(diǎn)之間的線(xiàn)所構(gòu)成的圖，反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。生活中的某些特定對(duì)象之間的特定關(guān)系。 通常用通常用點(diǎn)點(diǎn)表示研究對(duì)象表示研究對(duì)象, ,用用點(diǎn)與點(diǎn)之間的線(xiàn)點(diǎn)與點(diǎn)之間的線(xiàn)表示表示研究對(duì)象之間的特定關(guān)系。研究對(duì)象之間的特定關(guān)系。 一般情況下，圖中點(diǎn)的相對(duì)位置如何，點(diǎn)與點(diǎn)之一般情況下，圖中點(diǎn)的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線(xiàn)的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯間線(xiàn)的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯的并不重要，因此，的并不重要，因此，圖論中的圖與幾何圖，工程圖等圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。本質(zhì)上是不同的。2022-6-299端點(diǎn)，關(guān)聯(lián)邊，相鄰端點(diǎn)，關(guān)聯(lián)邊，相鄰 若邊若邊 e e 可表示為可表示為e e = = v vi i , , v vj j ，稱(chēng)稱(chēng) v vi i 和和 v vj j 是邊是邊 e e 的的端端點(diǎn)點(diǎn)，同時(shí)稱(chēng)邊，同時(shí)稱(chēng)邊 e e 為點(diǎn)為點(diǎn) v vi i 和和 v vj j 的的關(guān)聯(lián)邊關(guān)聯(lián)邊，若點(diǎn)，若點(diǎn) v vi i , , v vj j 與與同一條邊關(guān)聯(lián)，稱(chēng)點(diǎn)同一條邊關(guān)聯(lián)，稱(chēng)點(diǎn) v vi i 和和 v vj j 相鄰相鄰；若邊；若邊 e ei i 與與 e ej j 有公共端有公共端點(diǎn)，稱(chēng)邊點(diǎn)，稱(chēng)邊 e ei i 和和 e ej j 相鄰相鄰. .2022-6-2910 如果邊如果邊 e e 的兩個(gè)端點(diǎn)相重，的兩個(gè)端點(diǎn)相重，稱(chēng)該邊為稱(chēng)該邊為環(huán)環(huán)，如果兩個(gè)點(diǎn)之間，如果兩個(gè)點(diǎn)之間的邊多于一條，稱(chēng)為具有的邊多于一條，稱(chēng)為具有多重多重邊邊，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱(chēng)，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱(chēng)為為簡(jiǎn)單圖簡(jiǎn)單圖。環(huán)，多重邊，簡(jiǎn)單圖環(huán)，多重邊，簡(jiǎn)單圖2022-6-2911次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn) 與某個(gè)點(diǎn)相關(guān)聯(lián)的邊與某個(gè)點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，稱(chēng)為該點(diǎn)的的數(shù)目，稱(chēng)為該點(diǎn)的次次（或（或度、線(xiàn)度度、線(xiàn)度），記作），記作 d d( (v v) )。次為奇數(shù)的點(diǎn)稱(chēng)為次為奇數(shù)的點(diǎn)稱(chēng)為奇點(diǎn)奇點(diǎn)，次為偶數(shù)的點(diǎn)稱(chēng)為，次為偶數(shù)的點(diǎn)稱(chēng)為偶點(diǎn)偶點(diǎn)，次為零的點(diǎn)稱(chēng)為，次為零的點(diǎn)稱(chēng)為孤孤立點(diǎn)。立點(diǎn)。如圖：如圖： 奇點(diǎn)為奇點(diǎn)為 v v5 5 ， v v3 3偶點(diǎn)為偶點(diǎn)為 v v1 1 , , v v2 2 , , v v4 4 , , v v6 6孤立點(diǎn)為孤立點(diǎn)為 v v6 62022-6-2912鏈，圈，路，回路，連通圖鏈，圈，路，回路，連通圖 圖中有些點(diǎn)和邊的交替序列圖中有些點(diǎn)和邊的交替序列 =v v0 0 , , e e1 1 , , v v1 1 , , e e2 2 , , , , e ek k , , v vk k ，若其各邊若其各邊 e e1 1 , ,e e2 2 , , , , e ek k 各不相同，且任意各不相同，且任意 v vi,ti,t-1-1 , , v vitit (2 (2 t t k k) )都都相鄰，稱(chēng)相鄰，稱(chēng) 為為鏈鏈，如果鏈中所有的頂點(diǎn)，如果鏈中所有的頂點(diǎn) v v0 0 , , v v1 1 , , , , v vk k也不相同，這樣的鏈成為也不相同，這樣的鏈成為路路，起點(diǎn)和，起點(diǎn)和終點(diǎn)重合的鏈稱(chēng)為終點(diǎn)重合的鏈稱(chēng)為圈，圈，起點(diǎn)和終點(diǎn)重合的路稱(chēng)為起點(diǎn)和終點(diǎn)重合的路稱(chēng)為回回路路，若在一個(gè)圖中，每一對(duì)頂點(diǎn)之間至少存在一條，若在一個(gè)圖中，每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱(chēng)這樣的圖為鏈，稱(chēng)這樣的圖為連通圖連通圖，否則稱(chēng)該圖為，否則稱(chēng)該圖為不連通不連通的。的。2022-6-291335264734221,vevevevevev鏈鏈4734221,vevevev路路,1335264734221vevevevevevev圈圈2022-6-2914完全圖完全圖 一個(gè)簡(jiǎn)單圖中若任意兩點(diǎn)之間均有邊相連，稱(chēng)這樣一個(gè)簡(jiǎn)單圖中若任意兩點(diǎn)之間均有邊相連，稱(chēng)這樣的圖為的圖為完全圖。完全圖。含有含有 n n 個(gè)頂點(diǎn)的完全圖，其邊數(shù)有個(gè)頂點(diǎn)的完全圖，其邊數(shù)有 條。條。 2) 1( nn2022-6-2915偶圖偶圖 如果圖的頂點(diǎn)能分成兩個(gè)互不相交的非空集合如果圖的頂點(diǎn)能分成兩個(gè)互不相交的非空集合 V V1 1 和和V V2 2 , , 使在同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，稱(chēng)使在同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，稱(chēng)這樣的圖為這樣的圖為偶圖偶圖（也稱(chēng)（也稱(chēng)二分圖二分圖），如果偶圖的頂點(diǎn)集），如果偶圖的頂點(diǎn)集合合V V1 1 和和V V2 2 之間的每一對(duì)頂點(diǎn)都有一條邊相連，稱(chēng)這之間的每一對(duì)頂點(diǎn)都有一條邊相連，稱(chēng)這樣的圖為樣的圖為完全偶圖完全偶圖，完全偶圖中，完全偶圖中V V1 1 含含m m 個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，V V2 2 含有含有 n n 個(gè)頂點(diǎn)，則其邊數(shù)共個(gè)頂點(diǎn)，則其邊數(shù)共 m n m n 條。條。2022-6-2916子圖，部分圖子圖，部分圖 圖圖 G G1 1=V V1 1 , , E E1 1 和和 G G2 2=V V2 2 , , E E2 2 ，若有若有 和和 ，稱(chēng)，稱(chēng) G G1 1 是是 G G2 2 的一個(gè)的一個(gè)子圖子圖；若有若有 ，則稱(chēng)，則稱(chēng) G G1 1 是是 G G2 2 的一個(gè)的一個(gè)部分圖部分圖。注意：注意：部分圖也是子圖，但子圖不一定是部分圖。部分圖也是子圖，但子圖不一定是部分圖。21VV 21EE 2121,EEVV子圖：子圖：部分圖部分圖2022-6-29172 2樹(shù)圖和最小部分樹(shù)樹(shù)圖和最小部分樹(shù) 樹(shù)圖樹(shù)圖（簡(jiǎn)稱(chēng)（簡(jiǎn)稱(chēng)樹(shù)樹(shù)，記作，記作 T(V, E)T(V, E)）是無(wú)圈的連通圖。是無(wú)圈的連通圖。（無(wú)圈，無(wú)多重邊）（無(wú)圈，無(wú)多重邊）性質(zhì)性質(zhì)1.1. 任何樹(shù)中必存在次為任何樹(shù)中必存在次為1 1 的點(diǎn)。的點(diǎn)。 次為次為1 1的點(diǎn)稱(chēng)為的點(diǎn)稱(chēng)為懸掛點(diǎn)懸掛點(diǎn)，與之關(guān)聯(lián)的邊，與之關(guān)聯(lián)的邊 稱(chēng)為稱(chēng)為懸掛邊。懸掛邊。2.1 2.1 樹(shù)的性質(zhì)樹(shù)的性質(zhì)2022-6-2918性質(zhì)性質(zhì)2.2. 具有具有 n n 個(gè)頂點(diǎn)的樹(shù)恰有（個(gè)頂點(diǎn)的樹(shù)恰有（n n-1-1）條邊。條邊。性質(zhì)性質(zhì)3.3. 任何具有任何具有n n 個(gè)點(diǎn)、個(gè)點(diǎn)、( (n n - 1)- 1)條邊連通圖是條邊連通圖是 樹(shù)。樹(shù)。說(shuō)明：說(shuō)明：1. 1. 樹(shù)中只要任意再加樹(shù)中只要任意再加 一條邊，必出現(xiàn)圈。一條邊，必出現(xiàn)圈。 2. 2. 樹(shù)中任意兩點(diǎn)之間有且只有樹(shù)中任意兩點(diǎn)之間有且只有 一條通路，從樹(shù)中任意刪掉一條通路，從樹(shù)中任意刪掉 一條邊，就不再連通。一條邊，就不再連通。 （樹(shù)是最脆弱的連通圖）（樹(shù)是最脆弱的連通圖）2022-6-29192.2 2.2 圖的最小部分樹(shù)圖的最小部分樹(shù)如果如果 G G1 1 是是 G G2 2 的部分圖，又是樹(shù)圖，則稱(chēng)的部分圖，又是樹(shù)圖，則稱(chēng) G G1 1 是是 G G2 2 的的部分樹(shù)部分樹(shù)（或（或支撐樹(shù)支撐樹(shù)）；）；樹(shù)圖的各條邊稱(chēng)為樹(shù)枝樹(shù)圖的各條邊稱(chēng)為樹(shù)枝( (假定各邊均有權(quán)重假定各邊均有權(quán)重) )；樹(shù)枝總長(zhǎng)最小的部分樹(shù)，稱(chēng)為該圖的樹(shù)枝總長(zhǎng)最小的部分樹(shù)，稱(chēng)為該圖的最小部分樹(shù)最小部分樹(shù)( (也也稱(chēng)稱(chēng)最小支撐樹(shù)最小支撐樹(shù)) )。定理定理1.1. 圖中任一個(gè)點(diǎn)圖中任一個(gè)點(diǎn) i i ，若若j j 是與是與i i 相鄰點(diǎn)中距相鄰點(diǎn)中距離最近的，則邊離最近的，則邊 i i , ,j j 一定包含在該圖的最小部一定包含在該圖的最小部分樹(shù)中。分樹(shù)中。推論推論. . 把圖的所有點(diǎn)分成把圖的所有點(diǎn)分成 V V 和和 兩個(gè)集合，則兩個(gè)集合，則兩集合之間連線(xiàn)的最短邊一定包含在最小部分樹(shù)內(nèi)。兩集合之間連線(xiàn)的最短邊一定包含在最小部分樹(shù)內(nèi)。V2022-6-29202.3 2.3 避圈法和破圈法避圈法和破圈法尋找最小部分樹(shù)的方法主要有尋找最小部分樹(shù)的方法主要有避圈法避圈法和和破圈法破圈法兩種。兩種。避圈法步驟：避圈法步驟：1.1.從圖中任選一點(diǎn)從圖中任選一點(diǎn) v vi i ，讓讓 v vi i V V ，圖中其余點(diǎn)均圖中其余點(diǎn)均包含在包含在 中；中；V2. 2. 從從 V V 與與 的連線(xiàn)中找出最小邊，這條邊一的連線(xiàn)中找出最小邊，這條邊一定包含在最小部分樹(shù)中，不妨設(shè)這條邊為定包含在最小部分樹(shù)中，不妨設(shè)這條邊為 v vi i , , v vj j 將其加粗，標(biāo)記為最小部分樹(shù)中的邊。將其加粗，標(biāo)記為最小部分樹(shù)中的邊。V3. 3. 令令 ， ；jvV -V4. 4. 重復(fù)重復(fù)2 2、3 3兩步，一直到圖中所有點(diǎn)均包含在兩步，一直到圖中所有點(diǎn)均包含在 V V 中。中。jvVV2022-6-2921避圈法另一種做法避圈法另一種做法： 1.1.在所有各邊中找到邊權(quán)最小的一條，將其作為最小部分樹(shù)中在所有各邊中找到邊權(quán)最小的一條，將其作為最小部分樹(shù)中的第一邊；在剩余的邊中，仍然找到邊權(quán)最小的作為最小部的第一邊；在剩余的邊中，仍然找到邊權(quán)最小的作為最小部分樹(shù)的第二條邊；分樹(shù)的第二條邊；2.2.在剩余的邊中，找到邊權(quán)最小的邊，查看其是否與在剩余的邊中，找到邊權(quán)最小的邊，查看其是否與前面的邊形成圈，如果沒(méi)有，則在最小部分樹(shù)中添加前面的邊形成圈，如果沒(méi)有，則在最小部分樹(shù)中添加該邊，如果形成了圈，則不再考慮該邊；該邊，如果形成了圈，則不再考慮該邊；3.3.重復(fù)進(jìn)行第二步，直到找到第重復(fù)進(jìn)行第二步，直到找到第 n n-1 -1 條邊為止。條邊為止。（因?yàn)橛校ㄒ驗(yàn)橛?n n 個(gè)頂點(diǎn)的樹(shù)中一定有個(gè)頂點(diǎn)的樹(shù)中一定有 n n-1 -1 條邊）條邊）2022-6-2922例例：分別用兩種避圈法構(gòu)造下圖的最小部分樹(shù)。：分別用兩種避圈法構(gòu)造下圖的最小部分樹(shù)。第一種解法：第一種解法：1. 1. 在點(diǎn)集中任選一點(diǎn)，不妨取在點(diǎn)集中任選一點(diǎn)，不妨取 S S，令令 V V=S S 2. 2. 找到和找到和 S S 相鄰的邊中，權(quán)值最小的相鄰的邊中，權(quán)值最小的 S S , , A A 。2022-6-29233.3.V V=S S , , A A 4. 4. 重復(fù)第重復(fù)第2 2，3 3步，找到下一個(gè)點(diǎn)。步，找到下一個(gè)點(diǎn)。2022-6-2924 第二種做法求解過(guò)程：第二種做法求解過(guò)程：2022-6-2925破圈法求解步驟：破圈法求解步驟：1.1. 從圖從圖 N N 中任取一回路，去掉這個(gè)回路中邊中任取一回路，去掉這個(gè)回路中邊權(quán)最大的邊，得到原圖的一個(gè)子圖權(quán)最大的邊，得到原圖的一個(gè)子圖 N N1 1。2. 2. 從剩余的子圖中任找一回路，同樣去掉回路中從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；邊權(quán)最大的一條邊，得一新的子圖；3. 3. 重復(fù)第重復(fù)第 2 2 步，直到圖中不再含有回路為止。步，直到圖中不再含有回路為止。2022-6-2926用破圈法求解上例：用破圈法求解上例：1. 1. 任意找到一回路，不妨取任意找到一回路，不妨取 DETDDETD，去掉邊權(quán)最大去掉邊權(quán)最大的邊的邊 T T , ,E E ;2. 2. 從剩余的子圖中任找一回路，同樣去掉回路從剩余的子圖中任找一回路，同樣去掉回路中邊權(quán)最大的一條邊，得一新的子圖；依次類(lèi)推。中邊權(quán)最大的一條邊，得一新的子圖；依次類(lèi)推。2022-6-29272022-6-2928破圈法的另一種解法：破圈法的另一種解法：1.1.從剩余圖中找到邊權(quán)最大一條邊，如果將其刪除后從剩余圖中找到邊權(quán)最大一條邊，如果將其刪除后圖仍然是連通的，則刪除此邊，否則不再考慮此邊；圖仍然是連通的，則刪除此邊，否則不再考慮此邊；2.2.重復(fù)上述步驟，直到剩余邊數(shù)為重復(fù)上述步驟，直到剩余邊數(shù)為 n n-1 -1 為止。為止。2022-6-2929注意：注意：1. 1. 一個(gè)圖的最小部分樹(shù)不唯一，該題中用幾種解一個(gè)圖的最小部分樹(shù)不唯一，該題中用幾種解法得到的結(jié)果都是相同的，是特殊情況；法得到的結(jié)果都是相同的，是特殊情況；2.2.不同解法得到的最小部分樹(shù)所包含的邊雖然可不同解法得到的最小部分樹(shù)所包含的邊雖然可能不相同，但是，每個(gè)最小部分樹(shù)中所有邊權(quán)的能不相同，但是，每個(gè)最小部分樹(shù)中所有邊權(quán)的總和一定都是相同的，即都達(dá)到了最小?？偤鸵欢ǘ际窍嗤?，即都達(dá)到了最小。2022-6-29303 3最短路問(wèn)題最短路問(wèn)題最短路問(wèn)題最短路問(wèn)題是指從給定的網(wǎng)絡(luò)圖中找出任意兩點(diǎn)之是指從給定的網(wǎng)絡(luò)圖中找出任意兩點(diǎn)之間距離最短（權(quán)值和最?。┑囊粭l路。間距離最短（權(quán)值和最?。┑囊粭l路。某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃問(wèn)題可以歸結(jié)為求最短路某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃問(wèn)題可以歸結(jié)為求最短路的問(wèn)題。如選址問(wèn)題、管道鋪設(shè)選線(xiàn)問(wèn)題、設(shè)備更的問(wèn)題。如選址問(wèn)題、管道鋪設(shè)選線(xiàn)問(wèn)題、設(shè)備更新、投資等問(wèn)題。新、投資等問(wèn)題。 最短路的求法：最短路的求法：1.1.從某一點(diǎn)至其它各點(diǎn)之間最短距離的狄克斯屈拉從某一點(diǎn)至其它各點(diǎn)之間最短距離的狄克斯屈拉( ( DijkstraDijkstra ) )算法算法; ;2.2.求網(wǎng)絡(luò)圖中任意兩點(diǎn)之間的最短距離的矩陣算法。求網(wǎng)絡(luò)圖中任意兩點(diǎn)之間的最短距離的矩陣算法。2022-6-2931 3.1 3.1 DijkstraDijkstra 算法算法1.1.設(shè)設(shè) d dijij 表示圖中兩相鄰點(diǎn)表示圖中兩相鄰點(diǎn) i i 與與 j j 的距離，若的距離，若 i i 與與 j j 不相鄰，令不相鄰，令 d dijij =，顯然，顯然 d diiii =0=0。 DijkstraDijkstra 算法假設(shè)：算法假設(shè)：基本思路：基本思路：如果如果 v v1 1 v v2 2 v v3 3 v v4 4 是是 v v1 1 v v4 4 的的最短路徑，則最短路徑，則 v v1 1 v v2 2 v v3 3 一定是一定是 v v1 1 v v3 3 的最的最短路徑。短路徑。 v v2 2 v v3 3 v v4 4 一定是一定是 v v2 2 v v4 4 的最短路徑。的最短路徑。2. 2. 設(shè)設(shè) L Lsisi 表示從表示從 s s 點(diǎn)到點(diǎn)到 i i 點(diǎn)的最短距離。點(diǎn)的最短距離。2022-6-2932DijkstraDijkstra 算法步驟：算法步驟：1.1.對(duì)起始點(diǎn)對(duì)起始點(diǎn) s s ，因，因 L Lssss =0 =0 ，將，將 0 0 標(biāo)注在標(biāo)注在 s s 旁的小旁的小方框內(nèi)，表示方框內(nèi)，表示 s s 點(diǎn)已標(biāo)號(hào)；點(diǎn)已標(biāo)號(hào)；2.2.從點(diǎn)從點(diǎn) s s 出發(fā)，找出與出發(fā)，找出與 s s 相鄰的點(diǎn)中距離最小的一相鄰的點(diǎn)中距離最小的一個(gè)，設(shè)為個(gè)，設(shè)為 r r ，將將 L Lsrsr = = L Lssss+ + d dsrsr 的值標(biāo)注在的值標(biāo)注在 r r 旁的小旁的小方框內(nèi)，表明點(diǎn)方框內(nèi)，表明點(diǎn) r r 也已標(biāo)號(hào)；也已標(biāo)號(hào)；3.3.從已標(biāo)號(hào)的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號(hào)從已標(biāo)號(hào)的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)點(diǎn) p p ，若有若有 L Lspsp = =min min L Lssss+ + d dspsp , , L Lsrsr+ + d drprp ，則對(duì)，則對(duì) p p 點(diǎn)標(biāo)號(hào)，并將點(diǎn)標(biāo)號(hào)，并將 L Lspsp 的值標(biāo)注在的值標(biāo)注在 p p 點(diǎn)旁的小方框內(nèi)；點(diǎn)旁的小方框內(nèi)；4.4.重復(fù)第重復(fù)第 3 3 步，直到步，直到 t t 點(diǎn)得到標(biāo)號(hào)為止。點(diǎn)得到標(biāo)號(hào)為止。求從起始點(diǎn)求從起始點(diǎn) s s 到終止點(diǎn)到終止點(diǎn) t t 的最短路徑。的最短路徑。2022-6-2933例例. . 求下圖中從求下圖中從 v v1 1 到到 v v7 7 的最短路。的最短路。解解： (1) (1) 從從 v v1 1 點(diǎn)出發(fā)，對(duì)點(diǎn)出發(fā)，對(duì) v v1 1 點(diǎn)標(biāo)號(hào)，將點(diǎn)標(biāo)號(hào)，將 L L1111=0 =0 標(biāo)注在標(biāo)注在 旁的小方框內(nèi)，令旁的小方框內(nèi)，令 v v1 1V V，其余點(diǎn)其余點(diǎn)屬于屬于 ；V2022-6-2934L1r = min 0+d12 , 0+ d13 =min5,2=2= L13(2)(2) 同同 v v1 1 相鄰的未標(biāo)號(hào)點(diǎn)有相鄰的未標(biāo)號(hào)點(diǎn)有v v2 2 、 v v3 3 ，2022-6-2935對(duì)對(duì) v v3 3 標(biāo)號(hào)，將標(biāo)號(hào)，將 L L13 13 的值標(biāo)注在的值標(biāo)注在v v3 3 旁的小方框內(nèi)；旁的小方框內(nèi)；將將( ( v v1 1, , v v3 3) ) 加粗，并令加粗，并令 V Vv v3 3 V V，VvV3。2022-6-2936L1p = min L11+d12 , L13+d34, L13+d36 =min0+5,2+7,2+4 = 5 = L12(3)(3) 同同 v v1 1 , ,v v3 3 相鄰的未標(biāo)號(hào)點(diǎn)有相鄰的未標(biāo)號(hào)點(diǎn)有v v2 2 、v v4 4 、v v6 6 ，2022-6-2937對(duì)對(duì) v v2 2 標(biāo)號(hào)，將標(biāo)號(hào)，將 L L12 12 的值標(biāo)注在的值標(biāo)注在 v v2 2 旁的小方框內(nèi)；旁的小方框內(nèi)；將將( ( v v1 1, , v v2 2) ) 加粗，并令加粗，并令 V Vv v2 2 V V，VvV22022-6-2938L1p = min L12+d25 , L12+d24, L13+d34 ,L13+d36 =min5+7,5+2,2+7,2+4 = 6 = L16。(4)(4) 同同 v v1 1 , ,v v2 2 , ,v v3 3 相鄰的未標(biāo)號(hào)點(diǎn)有相鄰的未標(biāo)號(hào)點(diǎn)有v v4 4 、v v5 5、v v6 6 ，2022-6-2939對(duì)對(duì) v v6 6 標(biāo)號(hào)，將標(biāo)號(hào)，將 L L16 16 的值標(biāo)注在的值標(biāo)注在 v v6 6 旁的小方框內(nèi)；旁的小方框內(nèi)；將將( ( v v3 3, , v v6 6) ) 加粗，并令加粗，并令 V Vv v6 6 V V，VvV62022-6-2940L1p = min L12+d25 , L12+d24, L13+d34 , L16+d64 , L16+d65 , L16+d67 =min5+7, 5+2, 2+7, 6+2, 6+1, 6+6 = 7 = L14 = L15(5)(5) 同同 v v1 1 , ,v v2 2 , ,v v3 3 , ,v v6 6 相鄰未標(biāo)號(hào)點(diǎn)有相鄰未標(biāo)號(hào)點(diǎn)有v v4 4 、v v5 5、 v v7 7，2022-6-2941對(duì)對(duì) v v4 4 , v , v5 5 同時(shí)標(biāo)號(hào)，將同時(shí)標(biāo)號(hào)，將 L L14 14 = = L L15 15 的值標(biāo)注在的值標(biāo)注在 v v4 4, , v v5 5 旁的小方框內(nèi)；將旁的小方框內(nèi)；將( ( v v2 2, , v v4 4), ( ), ( v v6 6, , v v5 5) ) 加粗，加粗，并令并令V Vv v4 4v v5 5V V，VvvV54,2022-6-2942L1p = min L15+d57 , L16+d67 =min7+3,6+6=10= L17(6)(6) 同同 v v1 1 , , v v2 2 , ,v v3 3 , , v v4 4, , v v5 5, , v v6 6 相鄰的未標(biāo)號(hào)點(diǎn)只相鄰的未標(biāo)號(hào)點(diǎn)只有有 v v7 7 ，2022-6-2943 對(duì)對(duì) v v7 7 標(biāo)號(hào)，將標(biāo)號(hào)，將 L L17 17 的值標(biāo)注在的值標(biāo)注在 v v7 7 旁的小方旁的小方框內(nèi)；將框內(nèi)；將( ( v v5 5, , v v7 7) ) 加粗。圖中粗線(xiàn)表明從點(diǎn)加粗。圖中粗線(xiàn)表明從點(diǎn) v v1 1 到到網(wǎng)絡(luò)中其它各點(diǎn)的最短路，各點(diǎn)旁的數(shù)字就是點(diǎn)網(wǎng)絡(luò)中其它各點(diǎn)的最短路，各點(diǎn)旁的數(shù)字就是點(diǎn) v v1 1 到各點(diǎn)的最短距離。到各點(diǎn)的最短距離。2022-6-29443.2 3.2 求任意兩點(diǎn)間最短距離的矩陣算法求任意兩點(diǎn)間最短距離的矩陣算法用用 DijkstraDijkstra 算法只能計(jì)算從圖中某一點(diǎn)到其他點(diǎn)算法只能計(jì)算從圖中某一點(diǎn)到其他點(diǎn)的最短距離，如果要計(jì)算各點(diǎn)之間的最短距離就需的最短距離，如果要計(jì)算各點(diǎn)之間的最短距離就需要對(duì)每個(gè)點(diǎn)分別計(jì)算，而用矩陣算法則可以同時(shí)求要對(duì)每個(gè)點(diǎn)分別計(jì)算，而用矩陣算法則可以同時(shí)求出所有各點(diǎn)間的最短距離。出所有各點(diǎn)間的最短距離。例例. . 利用矩陣算法求上述網(wǎng)絡(luò)圖中各點(diǎn)間的最短利用矩陣算法求上述網(wǎng)絡(luò)圖中各點(diǎn)間的最短距離。距離。解解. . 設(shè)設(shè) d dijij 表示圖中兩相鄰點(diǎn)表示圖中兩相鄰點(diǎn) i i 與與 j j 的距離，的距離，若若 i i 與與 j j 不相鄰，令不相鄰，令 d dijij =，顯然，顯然 d diiii =0=0。建立距離矩陣：建立距離矩陣：2022-6-29450636012431067260724702720525077767574737271676665646362615756555453525147464544434241373635343332312726252423222117161514131211ddddddddddddddddddddddddddddddddddddddddddddddddd2022-6-2946從上述距離矩陣可以看出從從上述距離矩陣可以看出從 i i 點(diǎn)到點(diǎn)到 j j 點(diǎn)的直接距點(diǎn)的直接距離，但從離，但從 i i 到到 j j 的最段距離不一定就是從的最段距離不一定就是從 i i 點(diǎn)點(diǎn)直接到直接到 j j 點(diǎn)。點(diǎn)。如上述問(wèn)題中，從如上述問(wèn)題中，從 v v1 1 v v2 2 的最短距離應(yīng)該是的最短距離應(yīng)該是minmind d1111+ +d d12 12 , , d d1212+ +d d22 22 , , d d1313+ +d d32 32 , , d d1414+ +d d42 42 , , d d1515+ +d d52 52 , , d d1616+ +d d62 62 , , d d1717+ +d d72 72 即即 minmind d1 1r r+ +d dr r2 2 。因此可以構(gòu)造一個(gè)新的矩陣因此可以構(gòu)造一個(gè)新的矩陣 D D(1)(1) ，令令 D D(1) (1) 中每一中每一個(gè)元素為：個(gè)元素為： d dijij(1)(1) = =minmind dirir+ +d drjrj ，則矩陣則矩陣 D D(1)(1) 給給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)及經(jīng)由一個(gè)中間出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)及經(jīng)由一個(gè)中間點(diǎn)時(shí)的最短距離點(diǎn)時(shí)的最短距離。2022-6-2947再構(gòu)造矩陣再構(gòu)造矩陣 D D(2)(2) ， d dijij(2)(2) = =minmind dir ir (1)(1) + +d drjrj (1)(1) 。依次類(lèi)推構(gòu)造矩陣依次類(lèi)推構(gòu)造矩陣 D D( (k k) ) ， d dijij( (k k) ) = =minmind dir ir ( (k k -1)-1) + +d drjrj ( (k k - -1) 計(jì)算停止的控制：計(jì)算停止的控制： p p是圖中頂點(diǎn)數(shù)。是圖中頂點(diǎn)數(shù)。kpk2lg) 1lg(12022-6-2948該例中該例中 k k = 3= 304381010401244631035712823062710456072104727056127250)1(D043688104012446310355762306278456072845270510677250)2(D)2()3(DD2022-6-2949 上述上述 D D(2)(2) 中的元素給出了各點(diǎn)間的最短距離，中的元素給出了各點(diǎn)間的最短距離，但是并沒(méi)有給出具體是經(jīng)過(guò)了哪些中間點(diǎn)才得到但是并沒(méi)有給出具體是經(jīng)過(guò)了哪些中間點(diǎn)才得到的這個(gè)最短距離，如果要知道中間點(diǎn)具體是什么，的這個(gè)最短距離，如果要知道中間點(diǎn)具體是什么，需要在計(jì)算過(guò)程中進(jìn)行記錄。需要在計(jì)算過(guò)程中進(jìn)行記錄。教材教材160頁(yè)例頁(yè)例52022-6-29504 4網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流4.1 4.1 網(wǎng)絡(luò)最大流的有關(guān)概念網(wǎng)絡(luò)最大流的有關(guān)概念 1.1.有向圖與容量網(wǎng)絡(luò)有向圖與容量網(wǎng)絡(luò)圖中每條邊有規(guī)定指向的圖稱(chēng)為圖中每條邊有規(guī)定指向的圖稱(chēng)為有向圖有向圖，有向圖的，有向圖的邊稱(chēng)為邊稱(chēng)為弧弧，記作，記作( (v vi i , , v vj j ) )，表示方向從點(diǎn)表示方向從點(diǎn) v vi i 指向指向點(diǎn)點(diǎn) v vj j ，有向圖是點(diǎn)與弧的集合，記作，有向圖是點(diǎn)與弧的集合，記作 D D( (V V, , A A ) )。弧弧( (v vi i , , v vj j ) )的最大通過(guò)能力，稱(chēng)為該的最大通過(guò)能力，稱(chēng)為該弧的容量弧的容量，記為記為c c( (v vi i , , v vj j ) ) ，或簡(jiǎn)記為，或簡(jiǎn)記為 c cijij 。定義了弧容量的網(wǎng)絡(luò)稱(chēng)為定義了弧容量的網(wǎng)絡(luò)稱(chēng)為容量網(wǎng)絡(luò)容量網(wǎng)絡(luò)。2022-6-2951容量網(wǎng)絡(luò)通常規(guī)定一個(gè)容量網(wǎng)絡(luò)通常規(guī)定一個(gè)發(fā)點(diǎn)發(fā)點(diǎn)( (源點(diǎn)，記為源點(diǎn)，記為s s) )一個(gè)一個(gè)收收點(diǎn)點(diǎn)( (匯點(diǎn)，記為匯點(diǎn)，記為t t) )，網(wǎng)絡(luò)中其余的點(diǎn)稱(chēng)為網(wǎng)絡(luò)中其余的點(diǎn)稱(chēng)為中間點(diǎn)。中間點(diǎn)。從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量稱(chēng)為從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量稱(chēng)為最大流最大流。多個(gè)收多個(gè)收( (發(fā)發(fā)) )點(diǎn)的網(wǎng)絡(luò)可以轉(zhuǎn)換為只含一個(gè)收點(diǎn)的網(wǎng)絡(luò)可以轉(zhuǎn)換為只含一個(gè)收( (發(fā)發(fā)) )點(diǎn)。點(diǎn)。2. 2. 流與可行流流與可行流流流是指加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量，對(duì)加在弧是指加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量，對(duì)加在弧( (v vi i , ,v vj j ) )上的負(fù)載量記作上的負(fù)載量記作 f f ( (v vi i , , v vj j ) ) ，或簡(jiǎn)記作或簡(jiǎn)記作 f fijij ，若網(wǎng)絡(luò)上所有的若網(wǎng)絡(luò)上所有的 f fijij =0=0，這個(gè)流稱(chēng)為，這個(gè)流稱(chēng)為零流。零流。2022-6-2952以以 v v( ( f f ) )表示網(wǎng)絡(luò)中從表示網(wǎng)絡(luò)中從 s st t 的的流量流量，則，則jtjjjsvvfvvffv),(),()(零流是可行流，求最大流就是求零流是可行流，求最大流就是求v v( ( f f ) )的最大值。的最大值。稱(chēng)網(wǎng)絡(luò)上滿(mǎn)足下述條件稱(chēng)網(wǎng)絡(luò)上滿(mǎn)足下述條件(1)(1)、(2)(2)的流為的流為可行流可行流：(1) (1) 容量限制條件容量限制條件: : 對(duì)所有弧有對(duì)所有弧有00f f ( (v vi i , ,v vj j ) ) c c ( (v vi i , ,v vj j ) )(2) (2) 中間點(diǎn)平衡條件：中間點(diǎn)平衡條件：f f ( (v vi i , ,v vj j ) ) - - f f( (v vj j , ,v vi i ) ) =0 (=0 (i is s , ,t t) )2022-6-29534.2 4.2 割和流量割和流量割割( (集）集）是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開(kāi)，是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開(kāi)，并使并使s st t 的流中斷的一組弧的集合的流中斷的一組弧的集合（截集）（截集）弧旁數(shù)字為弧旁數(shù)字為 c cijij ( ( f fijij ) ) 有不同的割見(jiàn)教材有不同的割見(jiàn)教材上圖中上圖中 KKKK 將網(wǎng)絡(luò)上的將網(wǎng)絡(luò)上的點(diǎn)分割成點(diǎn)分割成 V V 和和 兩個(gè)兩個(gè)集合，并有集合，并有 s sV V , , t t ，V稱(chēng)弧的集合稱(chēng)弧的集合( (V V, )=(, )=(v v1 1 , , v v3 3) , () , (v v2 2 , , v v4 4)是一個(gè)是一個(gè)割割。注意，這里不包含。注意，這里不包含( (v v3 3 , , v v2 2) ) 。VV2022-6-2954割的容量割的容量是組成割的集合中各弧容量之和，用是組成割的集合中各弧容量之和，用c c( (V V, , ) )表示，表示，V),(),(),(),(VVjijivvcVVc f f ( (V, V, ) ) 表示通過(guò)割表示通過(guò)割 ( (V V, ) , ) 中所有中所有V V 方向弧的流量的總和方向弧的流量的總和; ; f f ( ( ,V ,V ) ) 表示通過(guò)割表示通過(guò)割 中所有中所有 V V方向弧的方向弧的流量的總和，則有：流量的總和，則有：VVVVV),(),(),(),(),(),( , ),(),(VVijijVVjijivvfVVfvvfVVf2022-6-2955從從 s st t 的流量的流量等于通過(guò)割的從等于通過(guò)割的從V V 的流量減的流量減 V V的流量，有：的流量，有：VV),(),()(VVfVVffv用用 v v* *( ( f f ) ) 表示網(wǎng)絡(luò)中從表示網(wǎng)絡(luò)中從 s st t 的最大流，則有的最大流，則有),(),()(*VVfVVffvV),(),(),()(*VVcVVfVVffv因此，上例中最大流不會(huì)超過(guò)因此，上例中最大流不會(huì)超過(guò)1414（所有割集中最小者（所有割集中最小者) )最大流最大流 v v* *( (f f ) ) 應(yīng)應(yīng) 最小割的容量最小割的容量( (用用 c c* *( (V V, ), )表示表示) )2022-6-29564.3 4.3 最大流最小割定理最大流最小割定理增廣鏈：增廣鏈：如果在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在這條如果在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在這條鏈上：鏈上：所有指向?yàn)樗兄赶驗(yàn)?s st t 的?。ǚQ(chēng)的弧（稱(chēng)前向弧前向弧，記作，記作+ +），），存存在在f c f f 0(0(非零非零) )，（，（反向弧非零流反向弧非零流）這樣的鏈稱(chēng)這樣的鏈稱(chēng)增廣鏈增廣鏈。2022-6-2957當(dāng)有增廣鏈存在時(shí)，找出當(dāng)有增廣鏈存在時(shí)，找出 0 , , min對(duì)對(duì)iiiffc再令再令對(duì)非增廣鏈上的弧對(duì)所有對(duì)所有 , , , iiiffff顯然，經(jīng)過(guò)計(jì)算后顯然，經(jīng)過(guò)計(jì)算后 f f 仍然為可行流，但較原來(lái)仍然為可行流，但較原來(lái)的可行流的可行流 f f 流量增大了流量增大了 。因此，只有當(dāng)網(wǎng)絡(luò)因此，只有當(dāng)網(wǎng)絡(luò)圖中找不到增廣鏈時(shí)，圖中找不到增廣鏈時(shí)，s st t 流才不可能進(jìn)一步增流才不可能進(jìn)一步增大。大。2022-6-2958定理定理2.2. 在網(wǎng)絡(luò)中在網(wǎng)絡(luò)中 s st t 的最大流量等于它的最小的最大流量等于它的最小割集的容量，即割集的容量，即 VVcfv,*證明：證明：略略. .4.4 4.4 求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法 FordFord- -FulkersonFulkerson 標(biāo)號(hào)算法標(biāo)號(hào)算法，其本質(zhì)是判斷是否存，其本質(zhì)是判斷是否存在增廣鏈，如果存在，則找出增廣鏈，調(diào)整流量；在增廣鏈，如果存在，則找出增廣鏈，調(diào)整流量；若不存在，則說(shuō)明已達(dá)到最大流。若不存在，則說(shuō)明已達(dá)到最大流。2022-6-2959第一步：首先給發(fā)點(diǎn)第一步：首先給發(fā)點(diǎn) s s 標(biāo)號(hào)標(biāo)號(hào)(0 , (0 , ( (s s) ) ) )。第一個(gè)數(shù)字第一個(gè)數(shù)字是使這個(gè)點(diǎn)得到標(biāo)號(hào)的前一個(gè)點(diǎn)的代號(hào)，是使這個(gè)點(diǎn)得到標(biāo)號(hào)的前一個(gè)點(diǎn)的代號(hào)，因因 s s 是發(fā)點(diǎn)，因此記為是發(fā)點(diǎn)，因此記為0 0。第二個(gè)數(shù)字第二個(gè)數(shù)字( (s s) ) 表示從上一個(gè)標(biāo)號(hào)到這個(gè)標(biāo)號(hào)點(diǎn)表示從上一個(gè)標(biāo)號(hào)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值，的流量的最大允許調(diào)整值，s s 為發(fā)點(diǎn)，不限允許調(diào)為發(fā)點(diǎn)，不限允許調(diào)整容量，故整容量，故 ( (s s)=)=。第二步：列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)：第二步：列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)：2022-6-29602.2. 考慮所有指向標(biāo)號(hào)點(diǎn)考慮所有指向標(biāo)號(hào)點(diǎn) i i 的弧的弧 ( (h h , ,i i ) ) （即反向（即反向弧弧) ) ，如果有如果有 f fhihi=0=0，對(duì)對(duì) h h 不標(biāo)號(hào)，不標(biāo)號(hào)， 若若 f fhihi00，則對(duì)則對(duì) h h 點(diǎn)標(biāo)號(hào)，記為點(diǎn)標(biāo)號(hào)，記為( (i , i , ( ( h h ) ) )，其中其中( ( h h ) = min) = min( ( i i ) , ) , f fhihi).). 3.3. 如果某未標(biāo)號(hào)點(diǎn)如果某未標(biāo)號(hào)點(diǎn) k k 有兩個(gè)以上相鄰的標(biāo)號(hào)點(diǎn)，有兩個(gè)以上相鄰的標(biāo)號(hào)點(diǎn)，可按可按(1) ,(2) (1) ,(2) 中所述規(guī)則分別計(jì)算出中所述規(guī)則分別計(jì)算出 ( ( k k ) )的值，并取其中的最大的一個(gè)標(biāo)記。的值，并取其中的最大的一個(gè)標(biāo)記。1.1. 考慮從標(biāo)號(hào)點(diǎn)考慮從標(biāo)號(hào)點(diǎn) i i 出發(fā)的弧出發(fā)的弧 ( (i ,j i ,j ) )（即正向弧（即正向弧) )，如果有如果有 f fijij= =c cijij，不給點(diǎn)不給點(diǎn) j j 標(biāo)號(hào)；若標(biāo)號(hào)；若f fijij c cijij ，則則對(duì)對(duì) j j 標(biāo)號(hào)，記為標(biāo)號(hào)，記為( (i , i , ( ( j j ) ) )，其中其中( ( j j ) = ) = minmin( ( i i ) ,() ,(c cijij - -f fijij)2022-6-2961第三步：重復(fù)第二步可能出現(xiàn)如下兩種結(jié)果：第三步：重復(fù)第二步可能出現(xiàn)如下兩種結(jié)果： 1. 1. 標(biāo)號(hào)過(guò)程中斷，標(biāo)號(hào)過(guò)程中斷，t t 得不到標(biāo)號(hào)，說(shuō)明該網(wǎng)絡(luò)中不得不到標(biāo)號(hào)，說(shuō)明該網(wǎng)絡(luò)中不存在增廣鏈，給定流量即為最大流量。記已標(biāo)號(hào)存在增廣鏈，給定流量即為最大流量。記已標(biāo)號(hào)點(diǎn)集為點(diǎn)集為V V，未標(biāo)號(hào)點(diǎn)集為未標(biāo)號(hào)點(diǎn)集為 ，( (V V , ) , ) 為網(wǎng)絡(luò)為網(wǎng)絡(luò)的最小割。的最小割。VV2.2. t t 得到標(biāo)號(hào)，這時(shí)可用反向追蹤法在網(wǎng)絡(luò)中找到得到標(biāo)號(hào)，這時(shí)可用反向追蹤法在網(wǎng)絡(luò)中找到一條從一條從 stst 的有標(biāo)號(hào)點(diǎn)以及相應(yīng)的弧連接而的有標(biāo)號(hào)點(diǎn)以及相應(yīng)的弧連接而成的增廣鏈。成的增廣鏈。2022-6-2962第四步：修改流量。第四步：修改流量。設(shè)原圖中可行流為設(shè)原圖中可行流為 f f ，令令所有非增廣鏈上的弧對(duì)增廣鏈上所有后向弧對(duì)增廣鏈上所有前向弧 , , )( , )(ftftff這樣得到網(wǎng)絡(luò)上的一個(gè)新的可行流這樣得到網(wǎng)絡(luò)上的一個(gè)新的可行流 f f 。第五步：抹掉圖上所有標(biāo)號(hào)，重復(fù)第一到第四步。第五步：抹掉圖上所有標(biāo)號(hào)，重復(fù)第一到第四步。注意：注意：在求解步驟中，第三步起到控制運(yùn)算停止在求解步驟中，第三步起到控制運(yùn)算停止的作用，而不是第五步。的作用，而不是第五步。2022-6-2963例例：用標(biāo)號(hào)法求下述網(wǎng)絡(luò)圖用標(biāo)號(hào)法求下述網(wǎng)絡(luò)圖 s t 的最大流量，并的最大流量，并找出該網(wǎng)絡(luò)圖的最小割。找出該網(wǎng)絡(luò)圖的最小割。2022-6-2964解解：(1) 先給先給 s 點(diǎn)標(biāo)號(hào)點(diǎn)標(biāo)號(hào) (0 , )；2022-6-2965 (2) 從從 s 點(diǎn)出發(fā)的弧點(diǎn)出發(fā)的弧 (s , v2)，因有因有 fs20 ，且且(v1)=min(v2) , f12)=2 故對(duì)故對(duì) v1 點(diǎn)標(biāo)號(hào)點(diǎn)標(biāo)號(hào)(v2 , 2)。 (v2 , v4)飽和，不標(biāo)號(hào)。飽和，不標(biāo)號(hào)。2022-6-2967 (4) 弧弧 (v1 , v3)，因有因有 f130 ，且且(v4)=min(v3) , f43)=1 故對(duì)故對(duì) v4 點(diǎn)標(biāo)號(hào)點(diǎn)標(biāo)號(hào)(v3 , 1)。 (v3 , t)飽和，不標(biāo)號(hào)飽和，不標(biāo)號(hào), v2 已標(biāo)號(hào)。已標(biāo)號(hào)。2022-6-2969(6) 弧弧 (v4 , t)，因有因有 f4tc4t ，且且(t)=min(v4) , (c4t - f4t)=1 故對(duì)故對(duì) t 點(diǎn)標(biāo)號(hào)點(diǎn)標(biāo)號(hào)(v4 , 1)。2022-6-2970(7) 由于收點(diǎn)由于收點(diǎn) t 得到標(biāo)號(hào)，用反追蹤法找出網(wǎng)絡(luò)圖得到標(biāo)號(hào)，用反追蹤法找出網(wǎng)絡(luò)圖 上的一條增廣鏈。上的一條增廣鏈。2022-6-2971(8) 修改增廣鏈上各弧的流量：修改增廣鏈上各弧的流量：918)(011)(514)(314)(615)(4443431313121222tfftfftfftfftffttss非增廣鏈上的所有弧流量不變，這樣得到網(wǎng)絡(luò)圖上非增廣鏈上的所有弧流量不變，這樣得到網(wǎng)絡(luò)圖上的一個(gè)新的可行流。的一個(gè)新的可行流。2022-6-2972重復(fù)上述標(biāo)號(hào)過(guò)程，由于對(duì)點(diǎn)重復(fù)上述標(biāo)號(hào)過(guò)程，由于對(duì)點(diǎn) s s 、v v1 1 、v v2 2 、v v3 3 標(biāo)號(hào)后，標(biāo)號(hào)后，標(biāo)號(hào)中斷，故圖中的可行流即為最大流，標(biāo)號(hào)中斷，故圖中的可行流即為最大流，v v* *( ( f f )=14)=14已標(biāo)號(hào)點(diǎn)集為已標(biāo)號(hào)點(diǎn)集為V V =s s , , v v1 1 , , v v2 2 , , v v3 3 ，未標(biāo)號(hào)點(diǎn)集未標(biāo)號(hào)點(diǎn)集 ，( (V V , ) =(3 , , ) =(3 , t t) , (2 , 4) , (2 , 4)為網(wǎng)絡(luò)的最小割。為網(wǎng)絡(luò)的最小割。VV2022-6-29734.5 4.5 應(yīng)用舉例應(yīng)用舉例例例1：P166，例，例7ADECBF2321211111 1、方向含義、方向含義2 2、E E、D D之間之間3 3、數(shù)字含義、數(shù)字含義切斷切斷A A、F F之間的通路，相當(dāng)于求最小割集。之間的通路，相當(dāng)于求最小割集。2022-6-2974例例2：P167，例，例81 1、匹配關(guān)系、匹配關(guān)系1234562 2、匹配限制、匹配限制145f=1 f14 f152022-6-2975134f=1 f34 f14 3 3、等價(jià)網(wǎng)絡(luò)圖、等價(jià)網(wǎng)絡(luò)圖123456st1111111111112022-6-29765 5最小費(fèi)用流最小費(fèi)用流 在產(chǎn)銷(xiāo)平衡問(wèn)題中，研究的是使費(fèi)用最小的物資調(diào)在產(chǎn)銷(xiāo)平衡問(wèn)題中，研究的是使費(fèi)用最小的物資調(diào)運(yùn)方案；運(yùn)方案； 最大流問(wèn)題中考慮了聯(lián)結(jié)兩個(gè)點(diǎn)之間的弧的容量限最大流問(wèn)題中考慮了聯(lián)結(jié)兩個(gè)點(diǎn)之間的弧的容量限制，但是沒(méi)考慮流量通過(guò)各條弧時(shí)發(fā)生的費(fèi)用。制，但是沒(méi)考慮流量通過(guò)各條弧時(shí)發(fā)生的費(fèi)用。 實(shí)際物資調(diào)運(yùn)中，既要考慮弧的容量又要考慮調(diào)實(shí)際物資調(diào)運(yùn)中，既要考慮弧的容量又要考慮調(diào)運(yùn)費(fèi)用的節(jié)省，這就是運(yùn)費(fèi)用的節(jié)省，這就是最小費(fèi)用流最小費(fèi)用流要研究的問(wèn)題。要研究的問(wèn)題。 即要尋求一個(gè)最大流即要尋求一個(gè)最大流 f f，使得總的運(yùn)輸費(fèi)用，使得總的運(yùn)輸費(fèi)用 b(fb(f) ) 最小。最小。ijijfbfb)(min2022-6-2977尋求最大流尋求最大流 f f 的方法：的方法：從某可行流出發(fā)尋找增廣鏈，從某可行流出發(fā)尋找增廣鏈，然后沿著該鏈調(diào)整流量，直至達(dá)到最大流量。然后沿著該鏈調(diào)整流量，直至達(dá)到最大流量。附加附加”費(fèi)用費(fèi)用”的因素：的因素：希望沿增廣鏈增加流量后，希望沿增廣鏈增加流量后，增加的費(fèi)用是最小的。增加的費(fèi)用是最小的。這樣在前一個(gè)最小費(fèi)用流的基礎(chǔ)上（這樣在前一個(gè)最小費(fèi)用流的基礎(chǔ)上（ ）調(diào)整流量后，新的流量下的費(fèi)用也是最小的。調(diào)整流量后，新的流量下的費(fèi)用也是最小的。)(),(kkfbfv如何做到如何做到沿增廣鏈增加流量后，增加的費(fèi)用最小沿增廣鏈增加流量后，增加的費(fèi)用最??？ 假設(shè)假設(shè) 是流是流 f f 的一條增廣鏈，沿此增廣鏈調(diào)的一條增廣鏈，沿此增廣鏈調(diào)整整 1 1 個(gè)單位流量，引起的費(fèi)用增加量如下：個(gè)單位流量，引起的費(fèi)用增加量如下： 2022-6-2978ijijijijijijijijbbffbffbfbfbfb)()()()()(尋找尋找費(fèi)用增加最小的增廣鏈費(fèi)用增加最小的增廣鏈就相當(dāng)于：在由就相當(dāng)于：在由 b bijij 作作為弧權(quán)的為弧權(quán)的有向圖有向圖中尋找從發(fā)點(diǎn)到收點(diǎn)的最短路。中尋找從發(fā)點(diǎn)到收點(diǎn)的最短路。 （增廣鏈的費(fèi)用）（增廣鏈的費(fèi)用）2022-6-2979尋找最小費(fèi)用最大流的步驟：尋找最小費(fèi)用最大流的步驟： 1 1、從零流、從零流f f0 0 開(kāi)始，其費(fèi)用就是最小。開(kāi)始，其費(fèi)用就是最小。2 2、尋找費(fèi)用最小的增廣鏈：對(duì)上一個(gè)可行流、尋找費(fèi)用最小的增廣鏈：對(duì)上一個(gè)可行流 f fk k 構(gòu)造賦權(quán)有向圖構(gòu)造賦權(quán)有向圖W(fW(fk k),),，每對(duì)結(jié)點(diǎn)間有正向和反向，每對(duì)結(jié)點(diǎn)間有正向和反向弧。方法如下：弧。方法如下：ijijijijijijcfcfbw正向弧正向弧反向弧反向弧00jijijijiffbw在此圖中找到從發(fā)點(diǎn)到收點(diǎn)的最短路。在此圖中找到從發(fā)點(diǎn)到收點(diǎn)的最短路。2022-6-29803 3、沿此最短路（費(fèi)用最小的增廣鏈）調(diào)整流量，調(diào)、沿此最短路（費(fèi)用最小的增廣鏈）調(diào)整流量，調(diào)整量為整量為: :得到新的可行流得到新的可行流 f fk+1 k+1 。4 4、重復(fù)上述、重復(fù)上述2 2、3 3步，直至不存在從發(fā)點(diǎn)到收點(diǎn)的最步，直至不存在從發(fā)點(diǎn)到收點(diǎn)的最短路。短路。( (即不再存在增廣鏈）即不再存在增廣鏈）0 , , min對(duì)對(duì)ijijijffc2022-6-2981 例：例：如圖，圖中弧旁數(shù)字如圖，圖中弧旁數(shù)字( (c cijij , , b bijij) )中，中，c cijij 表示弧表示弧容量，容量， b bijij 表示單位費(fèi)用，求從表示單位費(fèi)用，求從 s s t t 的最小費(fèi)用的最小費(fèi)用的最大流。的最大流。2022-6-2982解：解：1. 1. 先不考慮弧容量，尋找最短路：先不考慮弧容量，尋找最短路：該圖中路徑旁數(shù)字該圖中路徑旁數(shù)字為單位費(fèi)用。為單位費(fèi)用。2. 2. 根據(jù)各弧容量，將路徑上的流量調(diào)整到最大可根據(jù)各弧容量，將路徑上的流量調(diào)整到最大可 能：能：2022-6-29833. 3. 構(gòu)建新的網(wǎng)絡(luò)圖：構(gòu)建新的網(wǎng)絡(luò)圖：(1)(1)對(duì)于非飽和且非零的弧對(duì)于非飽和且非零的弧( (i i , , j j) ) ，在兩點(diǎn)間分在兩點(diǎn)間分 別給出弧別給出弧( (i i , ,j j) ) 和和( ( j ,ij ,i) , ) , 其權(quán)值其權(quán)值分別為分別為 b bijij 和和 - - b bijij； ( (2) 2) 對(duì)于飽和弧對(duì)于飽和弧( (i i, ,j j) ) ，只畫(huà)出只畫(huà)出弧弧( (j,ij,i) ) ，其權(quán)值其權(quán)值 為為 - -b bijij；(3) (3) 對(duì)于零弧對(duì)于零弧( (i i, ,j j) ) ，只給出弧只給出弧( (i i, ,j j), ), 其權(quán)其權(quán)值為值為 b bijij 。2022-6-29844. 4. 重復(fù)第重復(fù)第 1 1 步，構(gòu)造最短路步，構(gòu)造最短路( (即費(fèi)用最小增廣鏈即費(fèi)用最小增廣鏈) )：5. 5. 重復(fù)第重復(fù)第 2 2 步，在原流量不減少的前提下調(diào)整流步，在原流量不減少的前提下調(diào)整流量；量；2022-6-2985 6.6.重復(fù)第重復(fù)第 3 3 步，重新構(gòu)造網(wǎng)絡(luò)圖，原則與第步，重新構(gòu)造網(wǎng)絡(luò)圖，原則與第 3 3 步步 相同：相同：7. 7. 重復(fù)第重復(fù)第 4 4 步，步， 尋找最短路：尋找最短路：2022-6-29868.8.重復(fù)第重復(fù)第 5 5 步，在原流量不減少的前提下調(diào)整流步，在原流量不減少的前提下調(diào)整流 量；量；9.9.重復(fù)第重復(fù)第 6 6 步，重新構(gòu)造步，重新構(gòu)造 網(wǎng)絡(luò)圖，原則與第網(wǎng)絡(luò)圖，原則與第 3 3 步步 相同：相同：2022-6-298710. 10. 重復(fù)第重復(fù)第 7 7 步，構(gòu)造最短路：步，構(gòu)造最短路：11.11.重復(fù)第重復(fù)第 8 8 步；步；2022-6-298812.12.重復(fù)第重復(fù)第 9 9 步，重新構(gòu)造網(wǎng)絡(luò)圖：步，重新構(gòu)造網(wǎng)絡(luò)圖：13.13.由于無(wú)法再找到最短路，因此計(jì)算停止，第由于無(wú)法再找到最短路，因此計(jì)算停止，第 11 11步所得流量即為最小費(fèi)用的最大流。步所得流量即為最小費(fèi)用的最大流。