1、2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-1-第六章 圖與網(wǎng)絡(luò)分析 圖是一種模型，如公路、鐵路交通圖， 通訊網(wǎng)絡(luò)圖等。 圖示對現(xiàn)實的抽象，以點和線段的連接組合表示。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-2- 1圖的基本概念與模型圖的基本概念與模型 2樹圖和圖的最小部分樹樹圖和圖的最小部分樹 3最短路問題最短路問題 4網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流 5最小費用流最小費用流2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-3-BACD 當(dāng)?shù)氐木用駸嶂杂谶@當(dāng)?shù)氐木用駸嶂杂谶@樣一個問題：樣一個問題：一個漫步者如何能夠走過一個漫步者如何能夠走過這七座橋，并且每座橋只這七座橋，并且每座橋只能走過一次，最終回到原能走

2、過一次，最終回到原出發(fā)地。出發(fā)地。盡管試驗者很多，盡管試驗者很多，但是都沒有成功。但是都沒有成功。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-4-4歐拉用歐拉用A A、B B、C C、D D四點表示四點表示河的兩岸和小島，用兩點間的聯(lián)河的兩岸和小島，用兩點間的聯(lián)線表示橋，如右下圖所示，該問線表示橋，如右下圖所示，該問題可歸結(jié)為：題可歸結(jié)為：能否從某一點出發(fā)，一筆畫能否從某一點出發(fā)，一筆畫出這個圖形，最后回到出發(fā)點而出這個圖形，最后回到出發(fā)點而不重復(fù)？即一筆畫問題。不重復(fù)？即一筆畫問題。ACBDBCDA歐拉在歐拉在17861786年發(fā)表了年發(fā)表了題為題為“依據(jù)幾何位置依據(jù)幾何位置的解題方法的解題方

3、法”的的論文，解決了著名的哥尼斯堡論文，解決了著名的哥尼斯堡七橋問題七橋問題歐拉證明了上述圖形一筆劃是不可能的，歐拉證明了上述圖形一筆劃是不可能的，因為圖中每一個點都只和奇數(shù)條線相關(guān)聯(lián)因為圖中每一個點都只和奇數(shù)條線相關(guān)聯(lián)他的結(jié)論是：圖形能一筆畫的充要條件是圖形的奇頂點（連接他的結(jié)論是：圖形能一筆畫的充要條件是圖形的奇頂點（連接奇數(shù)條線的頂點）的個數(shù)為零奇數(shù)條線的頂點）的個數(shù)為零2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-5- 在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點和線來畫出各式各樣的示意圖。常常在紙上用點和線來畫出各式各

4、樣的示意圖。例例 有六支球隊進行足球比賽，我們分別用點有六支球隊進行足球比賽，我們分別用點v v1 1v v6 6 表表示這六支球隊，它們之間的比賽情況，也可以用圖反示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知映出來，已知v v1 1 隊?wèi)?zhàn)勝隊?wèi)?zhàn)勝v v2 2 隊，隊，v v2 2 隊?wèi)?zhàn)勝隊?wèi)?zhàn)勝v v3 3隊，隊，v v3 3 隊?wèi)?zhàn)隊?wèi)?zhàn)勝勝v v5 5 隊，如此等等。這個勝負情況，可以用下圖所示隊，如此等等。這個勝負情況，可以用下圖所示的有向圖反映出來。的有向圖反映出來。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-6-6在自然界和人類的實際生活中，常用點和點與點之間的在自然界和人類

5、的實際生活中，常用點和點與點之間的聯(lián)線所構(gòu)成的圖，來反映某些研究對象和對象之間的某種聯(lián)線所構(gòu)成的圖，來反映某些研究對象和對象之間的某種特定的關(guān)系。如：特定的關(guān)系。如：為了反映城市之間有沒有航為了反映城市之間有沒有航班，我們可用右圖表示。甲城與班，我們可用右圖表示。甲城與乙城，乙城與丙城有飛機到達，乙城，乙城與丙城有飛機到達，而甲、丙兩城沒有直飛航班。而甲、丙兩城沒有直飛航班。甲甲乙乙丙丙甲甲乙乙丙丙工人工人ABC工作工作6.1 圖的基本概念和模型 對于工作分配問題，我們可能對于工作分配問題，我們可能用點表示工人與需要完成的工作，用點表示工人與需要完成的工作，點間連線表示每個工人可以勝任哪點間連

6、線表示每個工人可以勝任哪些工作如右圖所示。些工作如右圖所示。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-7-(v1)趙(v2)錢孫(v3) 李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來表示。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-8-一、概念（1）圖：點V和邊E的集合，用以表示對某種現(xiàn)實事物的抽象。記作 G=V,E,V=v1,v2,vn, E=e1,e2,

7、em點：表示所研究的事物對象； 邊：表示事物之間的聯(lián)系。v1v2v3v4v0e1e2e3e4e5e6e7e0（2）若邊e的兩個端點重合，則稱e為環(huán)。（3）多重邊：若某兩端點之間多于一條邊，則稱為多重邊。 給圖中的點和邊賦以具體的含義和權(quán)值，我們稱這樣的給圖中的點和邊賦以具體的含義和權(quán)值，我們稱這樣的圖為圖為網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖（賦權(quán)圖）（賦權(quán)圖）2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-9-9 無向圖：無向圖：G= V,E1 14 43 32 2e e1 1e e5 5e e6 6e e4 4e e3 3e e2 2e e7 71234V =v ,v,v,v1234567E= e ,e ,e ,e ,

8、e ,e ,e112212323434514613744e= v,v,e = v,v,e = v ,v,e = v,v,e = v,v,e = v,v,e = v ,v2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-10-10有向圖：有向圖：D= V,A111221333243452464574685395410561167a = v,v,a = v,v,a = v,v,a = v,v,a = v ,v,a = v ,v,a = v ,v,a = v ,v , a = v ,v,a = v ,va = v ,v1234567V= v ,v ,v ,v ,v ,v ,v12311A= a ,a ,a

9、,a324567a1a2a3a4a6a5a7a8a9a10a112022-3-23-第6章 圖與網(wǎng)絡(luò)分析-11-（4）簡單圖：無環(huán)、無多重邊的圖稱為簡單圖。（5）鏈：點和邊的交替序列，其中點可重復(fù)，但邊不能重復(fù)。（6）路：點和邊的交替序列，但點和邊均不能重復(fù)。（7）圈：始點和終點重合的鏈。（8）回路：始點和終點重合的路。（9）連通圖：若一個圖中，任意兩點之間至少存在一條鏈，稱這樣的圖為連通圖。（10）子圖，部分圖：設(shè)圖G1=V1,E1, G2=V2,E2, 如果有V1V2，E1E2，則稱G1是G2的一個子圖；若V1=V2，E1E2，則稱G1是G2的一個部分圖。（11）次：某點的關(guān)聯(lián)邊的個數(shù)稱為

10、該點的次，以d(vi)表示。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-12-次，奇點，偶點，孤立點次，奇點，偶點，孤立點 某點的某點的次次也稱為也稱為度、線度度、線度。次為奇數(shù)的點稱為。次為奇數(shù)的點稱為奇點奇點，次，次為偶數(shù)的點稱為為偶數(shù)的點稱為偶點偶點，次為零的點稱為，次為零的點稱為孤立點，孤立點，次為次為1的點的點稱為稱為懸掛點懸掛點。如圖：如圖：奇點為奇點為 v v5 5 ， v v3 3偶點為偶點為 v v1 1 , , v v2 2 , , v v4 4 , , v v6 6孤立點為孤立點為 v6懸掛點為懸掛點為 v52022-3-23-第6章 圖與網(wǎng)絡(luò)分析-13- 有向圖中，以vi

11、為始點的邊數(shù)稱為點vi的出次，用d+(vi)表示；以vi為終點的邊數(shù)稱為點vi 的入次，用表示d-(vi) ；vi 點的出次和入次之和就是該點的次。 有向圖中，所有頂點的入次之和等于所有頂點的出次之和。圖的次: 一個圖的次等于各點的次之和。定理定理 圖圖 中，所有頂點的次之和等于所有邊數(shù)的中，所有頂點的次之和等于所有邊數(shù)的2 2倍，倍， 即即G= V,Ev Vd(v)=2q2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-14-鏈，圈，路，回路，連通圖鏈，圈，路，回路，連通圖35264734221,vevevevevev鏈鏈4734221,vevevev路路,1335264734221veveveve

12、vevev圈圈子圖：子圖：部分圖部分圖注意：注意：部分圖也是子圖，但子圖部分圖也是子圖，但子圖不一定是部分圖。不一定是部分圖?；芈坊芈?224331,v e v e v e v15（1 1）開鏈和閉鏈：如果）開鏈和閉鏈：如果 ，則該鏈稱為開鏈；如果，則該鏈稱為開鏈；如果 ，則該鏈稱為閉鏈（或稱為圈）。則該鏈稱為閉鏈（或稱為圈）。（2 2）簡單鏈和初等鏈：如鏈內(nèi)所含的邊均不相同，稱之為簡單鏈；如）簡單鏈和初等鏈：如鏈內(nèi)所含的邊均不相同，稱之為簡單鏈；如鏈內(nèi)所含的點均不相同，稱之為初等鏈。鏈內(nèi)所含的點均不相同，稱之為初等鏈。 如：如：1niivv1niiv = v12345367v ,v,v,v,

13、v,v,v,v是簡單鏈，是簡單鏈，12367v ,v,v,v,v是初等鏈，是初等鏈，12341v ,v,v,v,v是初等圈，是初等圈，412357634v,v ,v,v,v,v,v,v,v是簡單圈，是簡單圈，1243567e1e2e3e8e4e7e6e5e916 賦權(quán)圖賦權(quán)圖：設(shè)圖：設(shè)圖 , ,若對其邊集若對其邊集E E定義了一個實值函數(shù)定義了一個實值函數(shù) ， , ,則稱該圖為一個賦權(quán)圖。記作則稱該圖為一個賦權(quán)圖。記作 。 稱稱 為邊為邊 的權(quán)。的權(quán)。 如某工廠內(nèi)連接六個車間的道路網(wǎng)如入所示，已知每條路長，要求沿道路如某工廠內(nèi)連接六個車間的道路網(wǎng)如入所示，已知每條路長，要求沿道路架設(shè)連接六個車

14、間的電話線路，使電話總長最短。架設(shè)連接六個車間的電話線路，使電話總長最短。123456652715344左圖為一賦權(quán)圖左圖為一賦權(quán)圖最優(yōu)解：如紅線所示，最優(yōu)解：如紅線所示，電話總長電話總長15個單位。個單位。紅線所示為圖的最小紅線所示為圖的最小支撐樹支撐樹G= V,Eijijw v ,v, v ,vEG= V,E,ijw v ,vijv ,v17 網(wǎng)絡(luò)圖：網(wǎng)絡(luò)圖：若若 為一賦權(quán)圖為一賦權(quán)圖 ，并在其頂點集合，并在其頂點集合V V中指中指定了起點（或稱發(fā)點）和終點（或稱收點），其余的點為中間點，這樣定了起點（或稱發(fā)點）和終點（或稱收點），其余的點為中間點，這樣的賦權(quán)圖稱為網(wǎng)絡(luò)圖（簡稱網(wǎng)絡(luò)）。記作

15、的賦權(quán)圖稱為網(wǎng)絡(luò)圖（簡稱網(wǎng)絡(luò)）。記作 。 網(wǎng)絡(luò)一般是連通的賦權(quán)圖。網(wǎng)絡(luò)一般是連通的賦權(quán)圖。 若一個網(wǎng)絡(luò)圖中的每條邊都是有向的弧，則稱之為有向網(wǎng)絡(luò)，記作若一個網(wǎng)絡(luò)圖中的每條邊都是有向的弧，則稱之為有向網(wǎng)絡(luò)，記作 G= V,E,N= V,E,N= V,A,9102015714192562022-3-23-第6章 圖與網(wǎng)絡(luò)分析-18-二、圖的模型 例：有甲、乙、丙、丁、戊、己六名運動員報名參加A、B、C、D、E、F六個項目的比賽。如表中所示，打“”的項目是各運動員報名參加比賽的項目。問：六個項目的比賽順序應(yīng)如何安排，才能做到使每名運動員不連續(xù)地參加兩項比賽？甲 乙 丙 丁 戊 己項目人A B C D

16、 E F 2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-19-建立模型：解：項目作為研究對象，排序。設(shè) 點：表示運動項目。邊：若兩個項目之間無無同一名運動員參加。ABCDEFACDEFBAFEDCBACBFEDAFBCDE順序：一個班級的學(xué)生共計選修A、B、C、D、E、F六門課程，其中一部分人同時選修D(zhuǎn)、C、A，一部分人同時選修B、C、F，一部分人同時選修B、E，還有一部分人同時選修A、B，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學(xué)生負擔(dān)，要求每人都不會連續(xù)參加考試，試設(shè)計一個考試日程表。以每門課程為一個頂點，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點對應(yīng)課程不能連續(xù)考試，不相鄰頂

17、點對應(yīng)課程允許連續(xù)考試，因此，作圖的補圖，問題是在圖中尋找一條哈密頓道路，如，就是一個符合要求的考試課程表。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-24-6.2 樹圖和圖的最小部分樹（1）樹圖： 無圈的連通圖稱為樹圖，簡稱為樹。記為T（V，E）一、樹圖的概念樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)域應(yīng)用極為廣泛。乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。AB CDEF GH運動員 某企業(yè)的組織機構(gòu)圖也可用樹圖表示。廠長廠長人事科人事科財務(wù)科財務(wù)科總工總工程師程師生產(chǎn)副生產(chǎn)副廠長廠長經(jīng)營副經(jīng)營副廠長廠長開發(fā)科開發(fā)科技術(shù)科技術(shù)科生產(chǎn)科生產(chǎn)科設(shè)備科設(shè)備科供應(yīng)科供應(yīng)科銷售科

18、銷售科檢驗科檢驗科動力科動力科2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-27-（2）樹圖的性質(zhì)性質(zhì)1：任何樹中必存在次為1的點。性質(zhì)2：具有n個頂點的樹的邊數(shù)恰好為n-1條。性質(zhì)3：任何具有n個點、n-1條邊的連通圖必為樹圖。比如有六個頂點的樹有比如有六個頂點的樹有6 6種種2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-28-性質(zhì)4：樹是邊數(shù)最多的無圈連通圖。在樹中任加一 條邊，就會形成圈。性質(zhì)5：樹是邊數(shù)最少的連通圖。在樹中任減一條邊，則不連通。二、圖的最小部分樹：二、圖的最小部分樹：1圖的部分樹：若G1是G2的一個部分圖，且為樹圖，則稱G1是G2的一個部分樹。G2：ABCD547365576G

19、1：ACBD2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-29-2圖的最小部分樹：樹枝總長為最短的部分樹稱為圖的最小部分樹（或最小支撐樹） 。樹枝：樹圖中的邊稱為樹枝。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-34-三、最小部分樹的求法定理1：圖中任一個點i，若j是與i相鄰點中距離最近的點，則邊i，j一定在其最小部分樹內(nèi)。推論：將圖中所有的點分成V和V兩個集合，則兩個集合之間連線最短的一個邊一定包含在最小部分樹內(nèi)。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-35-SABCDET252414317557最小部分樹長Lmin=14例：要在下圖所示的各個位置之間建立起通信網(wǎng)絡(luò)，試確定使總距離最佳的方案。2

20、022-3-23-第6章 圖與網(wǎng)絡(luò)分析-36-1. 避圈法：將圖中所有的點分V為V兩部分，V最小部分樹內(nèi)點的集合V非最小部分樹內(nèi)點的集合 任取一點vi加粗，令viV， 取V中與V相連的邊中一條最短的邊(vi,vj)， 加粗(vi,vj)，令vjV 重復(fù) ，至所有的點均在V之內(nèi)。2. 破圈法： 任取一圈，去掉其中一條最長的邊， 重復(fù)，至圖中不存在任何的圈為止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5樹與圖的最小樹部分樹2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-40-SABCDET252414317557最小部分樹長Lmin=1437

21、49346321Min C(T)=12Min C(T)=15254173314475答案：6.3 最短路問題 如何用最短的線路將三部電話連起來？ 此問題可抽象為設(shè)ABC為等邊三角形，連接三頂點的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個，其中最短路線者顯然是二邊之和（如ABAC）。ABCABCP但若增加一個周轉(zhuǎn)站（新點P），連接4點的新網(wǎng)絡(luò)的最短路線為PAPBPC。最短新路徑之長N比原來只連三點的最短路徑要短。這樣得到的網(wǎng)絡(luò)不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。最短路問題 問題描述：就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路 .有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投資、

22、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應(yīng)用。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-45- 在圖示的網(wǎng)絡(luò)圖中，從給定的點S出發(fā)，要到達目的地T。問：選擇怎樣的行走路線，可使總行程最短？方法：Dijkstra（D氏）標(biāo)號法按離出發(fā)點的距離由近至遠逐漸標(biāo)出最短距離和最佳行進路線。S1求某兩點間最短距離的D（Dijkstra）氏標(biāo)號法2472022-3-23461. 設(shè) dij 表示圖中兩相鄰點 i 與 j 的距離，若 i 與 j 不相鄰，令 dij =，顯然 dii =0。 Dijkstra 算法假設(shè)：基本思路：如果 v1 v2 v3 v4 是

23、 v1 v4 的最短路徑，則 v1 v2 v3 一定是 v1 v3 的最短路徑。 v2 v3 v4 一定是 v2 v4 的最短路徑。2. 設(shè) Lsi 表示從 s 點到 i 點的最短距離。2022-3-2347Dijkstra 算法步驟：1. 對起始點 s ，因 Lss =0 ，將 0 標(biāo)注在 s 旁的小方框內(nèi)，表示 s 點已標(biāo)號；2. 從點 s 出發(fā)，找出與 s 相鄰的點中距離最小的一個，設(shè)為 r ，將 Lsr = Lss+ dsr 的值標(biāo)注在 r 旁的小方框內(nèi)，表明點 r 也已標(biāo)號；3. 從已標(biāo)號的點出發(fā)，找出與這些點相鄰的所有未標(biāo)號點 p ，若有 Lsp =min Lss+ dsp , L

24、sr+ drp ，則對 p 點標(biāo)號，并將 Lsp 的值標(biāo)注在 p 點旁的小方框內(nèi)；4. 重復(fù)第 3 步，直到 t 點得到標(biāo)號為止。求從起始點 s 到終止點 t 的最短路徑。2022-3-2348例. 求下圖中從 v1 到 v7 的最短路。解： (1) 從 v1 點出發(fā)，對 v1 點標(biāo)號，將 L11=0 標(biāo)注在 旁的小方框內(nèi)，令 v1V，其余點屬于 ；V2022-3-2349L1r = min 0+d12 , 0+ d13 =min5,2=2= L13(2) 同 v1 相鄰的未標(biāo)號點有v2 、 v3 ，2022-3-2350對 v3 標(biāo)號，將 L13 的值標(biāo)注在v3 旁的小方框內(nèi)；將( v1,

25、v3) 加粗，并令 Vv3 V，VvV3。2022-3-2351L1p = min L11+d12 , L13+d34, L13+d36 =min0+5,2+7,2+4 = 5 = L12(3) 同 v1 , v3 相鄰的未標(biāo)號點有v2 、 v4 、 v6 ，2022-3-2352對 v2 標(biāo)號，將 L12 的值標(biāo)注在 v2 旁的小方框內(nèi)；將( v1, v2) 加粗，并令 Vv2 V，VvV22022-3-2353L1p = min L12+d25 , L12+d24, L13+d34 ,L13+d36 =min5+7,5+2,2+7,2+4 = 6 = L16。(4) 同 v1 , v2 ,

26、v3 相鄰的未標(biāo)號點有v4 、 v5、 v6 ，2022-3-2354對 v6 標(biāo)號，將 L16 的值標(biāo)注在 v6 旁的小方框內(nèi)；將( v3, v6) 加粗，并令 Vv6 V，VvV62022-3-2355L1p = 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) 同 v1 , v2 ,v3 , v6 相鄰的未標(biāo)號點有v4 、 v5、 v7 ，2022-3-2356對 v4 , v5 同時標(biāo)號，將 L14 = L15

27、的值標(biāo)注在 v4, v5 旁的小方框內(nèi)；將( v2, v4), ( v6, v5) 加粗，并令Vv4v5V，VvvV54,2022-3-2357L1p = min L15+d57 , L16+d67 =min7+3,6+6=10= L17(6) 同 v1 , v2 ,v3 , v4, v5, v6 相鄰的未標(biāo)號點只有 v7 ，2022-3-2358 對 v7 標(biāo)號，將 L17 的值標(biāo)注在 v7 旁的小方框內(nèi)；將( v5, v7) 加粗。圖中粗線表明從點 v1 到網(wǎng)絡(luò)中其它各點的最短路，各點旁的數(shù)字就是點 v1 到各點的最短距離。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-59-SABCDET25

28、241431755702447891413594 最短路線：S AB E D T最短距離：Lmin=13 練習(xí)： 1. 用Dijkstra算法求下圖從v1到v6的最短距離及路線。v3v54v1v2v4v635222421v1到v6的最短路為：6521vvvv61n 逐次逼近算法逐次逼近算法 DijkstraDijkstra算法只適用于所有算法只適用于所有 的情形，當(dāng)賦權(quán)有向圖中存在的情形，當(dāng)賦權(quán)有向圖中存在負權(quán)時，則算法失效。負權(quán)時，則算法失效。例如在右圖所示的賦權(quán)有向圖中，例如在右圖所示的賦權(quán)有向圖中，用用DijkstraDijkstra算法得算法得 到到 的最短路的的最短路的權(quán)是權(quán)是5.5

29、.但這里顯然不對；但這里顯然不對； 因為因為 到到 的最短路是的最短路是 ，權(quán)為，權(quán)為3 3。 當(dāng)當(dāng) 存在負權(quán)時，可采取逐次逼近算法來求解最短路存在負權(quán)時，可采取逐次逼近算法來求解最短路。 不妨設(shè)從任一點不妨設(shè)從任一點 到任一點到任一點 都有一條弧，如果都有一條弧，如果則添加弧則添加弧 ，且令，且令 。 如果為同一頂點，則如果為同一頂點，則 。 ijw01v3v123vvv1v3v75-4231ivijw jvD= V,A,ijija =(v ,v )Aijija =(v ,v )ii= 0, i=1,2,pw62 由最優(yōu)性原理，若令由最優(yōu)性原理，若令 為從為從 到到 的最短距離，則必滿足如的

30、最短距離，則必滿足如下方程：下方程： ，其中，其中P為為D的點數(shù)。的點數(shù)。 由此可得如下遞推公式：由此可得如下遞推公式： 其中其中 表示從表示從 走一步直接到達走一步直接到達 的最短距離，的最短距離， 表示從表示從 走走t t步到達步到達 的最短距離。為迭代步數(shù)。的最短距離。為迭代步數(shù)。 若第若第k k步，對所有步，對所有 ，有，有 則則 為為 到任一點到任一點 的最短路權(quán)。的最短路權(quán)。 sjd v ,vsvjvsjsiiji=1,2,pd v ,v= mind v ,v+ws到到j(luò) 的最短路的最短路s s到到i的最短路的最短路i j 1sjsjdv ,v= , j1,2,p;w tt-1sj

31、siiji=1,2,pdv ,vmindv ,v +w 1sjdv ,v tsjdv ,vsvjv kk-1sjsjdv ,v=dv ,vj1,2,p ksjdv ,vsvjvsvjv63解：迭代初始條件為：解：迭代初始條件為：有有 第二步迭代：第二步迭代：用表表示全部計算過程。用表表示全部計算過程。 1sjsjdv ,v=w 111112111314111516111718dv ,v= 0, dv ,v= -1,dv ,v= -2, dv ,v= 3, dv ,v=+ , dv ,v=+ ,dv ,v=+ , dv ,v=+ .例例 求所示賦權(quán)有向圖中從求所示賦權(quán)有向圖中從 到各點的最短路。

32、到各點的最短路。11-1-1-2-3-3-56318-527212345678 21sjsiijidv ,v= min dv ,v+w, j=1,2,81-11v640-5-350-1-1710110-1-73208-2-21 1-5-50-3-5-1206003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格為表中空格為） 111111121314dv ,v= 0, dv ,v= -1,dv ,v= -2, dv ,v= 3 6560-5-3-550-1-1-17101-310-1-7-73208-2-2-21

33、1-5-50-3-5-5-12060003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格為表中空格為）66660-5-3-5-550-1-1-1-17101-3-310-1-7-7-73208-2-2-2-21 1-5-50-3-5-5-5-120600003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格為表中空格為）67當(dāng)時當(dāng)時表明已得到從表明已得到從 到各點的最短路的權(quán)，即表中最后一列數(shù)。到各點的最短路的權(quán)，即表中最后一列數(shù)。如

34、果需要知道點到各點的最短路徑，可以采用如果需要知道點到各點的最短路徑，可以采用“反向追蹤反向追蹤”的辦法。的辦法。比如已知，則尋找一點，使比如已知，則尋找一點，使記下，再考察尋找一點，使記下，再考察尋找一點，使記下，直至達到為止本例中記下，直至達到為止本例中因為因為由記下由記下由記下由記下因為因為 一步可達，所以最短路徑一步可達，所以最短路徑 431j1jdv ,v=dv ,vj=1, 2,8t=41v1v1jd v ,v1kkj1jd v ,vwd v ,v1iik1kd v ,vwd v ,vkj(v ,v )1kd v ,v,ik(v ,v )1vivkv18d v ,v=6166818

35、d v ,v+w=(-1)+7=6=d v ,v68(v ,v )133616d v ,v+w =(-2)+1= -1 =d v ,v36(v ,v )13d v ,v=21368vvvv68660-5-3-5-550-1-1-1-17101-3-310-1-7-7-7320-2-2-2-21 1-5-50-3-5-5-5-120600003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格為表中空格為）69例例 設(shè)備更新問題。某企業(yè)使用一臺設(shè)備，在每年年初，都要決定設(shè)備更新問題。某企業(yè)使用一臺設(shè)備，在每年年初，都要

36、決定是否更新。若購置新設(shè)備，要付購買費；若繼續(xù)使用舊設(shè)備，則支是否更新。若購置新設(shè)備，要付購買費；若繼續(xù)使用舊設(shè)備，則支付維修費用。試制定一個付維修費用。試制定一個5 5年更新計劃，使總支出最少。年更新計劃，使總支出最少。 若已知設(shè)備在各年的購買費及不同機器役齡時的殘值和維修費若已知設(shè)備在各年的購買費及不同機器役齡時的殘值和維修費，如下表所示：，如下表所示：第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 購買費購買費 11111212131314141414機器役齡機器役齡 0-10-11-21-22-32-33-43-44-54-5維修費維修費 5 56 68

37、811111818殘值殘值 4 43 32 21 10 070解：把這個問題化為最短路問題解：把這個問題化為最短路問題用用 表示第表示第i i年初購進一臺新設(shè)備，虛設(shè)一個點年初購進一臺新設(shè)備，虛設(shè)一個點 表示第表示第5 5年底；年底； 用弧用弧 表示第表示第i i年初購的設(shè)備一直使用到第年初購的設(shè)備一直使用到第j j年年初（第年年初（第j-1j-1年年低）；弧年年低）；弧旁的數(shù)字表示第旁的數(shù)字表示第i i年初購進設(shè)備，一直使用到第年初購進設(shè)備，一直使用到第j j年初所需支付的購買年初所需支付的購買、維修的全部費用。、維修的全部費用。 這樣設(shè)備更新問題就變?yōu)椋呵髲倪@樣設(shè)備更新問題就變?yōu)椋呵髲?到

38、到 的最短路的最短路. .ivijv ,v1v6vijv ,v6v第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 購買費購買費 11111212131314141414機器役齡機器役齡 0-10-11-21-22-32-33-43-44-54-5維修費維修費 5 56 68 811111818殘值殘值 4 43 32 21 10 071第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 購買費購買費 11111212131314141414機器役齡機器役齡 0-10-11-21-22-32-33-43-44-54-5維修費維修費 5 56

39、 68 811111818殘值殘值 4 43 32 21 10 0194059121314152130152841292220123456購買購買維修維修殘值殘值費用費用72 計算結(jié)果表明計算結(jié)果表明 為最短路，路長為為最短路，路長為4949。即在。即在第第1 1年、第年、第3 3年初各購買一臺新設(shè)備為最優(yōu)決策，這時年初各購買一臺新設(shè)備為最優(yōu)決策，這時5 5年的總費用年的總費用為為4949。136vvv194059121314152130152841292220123456(v1,0)(v1,12)(v1,19)(v1,28)(v3,40)(v3,49) V1 V2 12V3 19 19V4

40、28 28 28V5 40 40 40 40V6 59 53 49 49 49相鄰點相鄰點V1 V1 V1 V1 V3V3標(biāo)號標(biāo)號73n 圖的矩陣表示圖的矩陣表示l距離矩陣：設(shè)圖距離矩陣：設(shè)圖 ， 為邊上的權(quán)，表示點為邊上的權(quán)，表示點 到到 之間的距離，則可構(gòu)造距離矩陣，之間的距離，則可構(gòu)造距離矩陣， 其中其中如：以下無向賦權(quán)圖中的權(quán)表示點與點之間距離如：以下無向賦權(quán)圖中的權(quán)表示點與點之間距離G= V,E,ijwijnnA =aijijijw v ,v Ea =0 ijv ,v 其他其他1234512345 v v v v vv09247v9034+A= v 23085v44806v7+560

41、1 12 24 47 76 63 35 54 48 89 92 23 34 45 5或或 對有向賦權(quán)圖，則定義時將改為。對有向賦權(quán)圖，則定義時將改為。ijaij v ,v ij (v ,v )ivjv654321654321 030303302004020576305020007204346040vvvvvvvvvvvvB v5v1v2v3v4v64332256437下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下:75l鄰接矩陣：鄰接矩陣：設(shè)圖設(shè)圖 ，則鄰接矩陣的元素可定，則鄰接矩陣的元素可定義如下義如下ijn nA= aij1a=0G= V,Eij v ,v E其他其他對有向賦權(quán)圖，則定義時將改為對有向

42、賦權(quán)圖，則定義時將改為如如ijaij v ,v ij (v ,v )1234512345 v v v v vv01010v10110A= v00000v00001v0110012345v5v1v2v3v4v643322564371234561236 6456 010111101100010101111010100101101010 vvvvvvvvvAvvv下圖所表示的圖可以構(gòu)造鄰接矩陣A如下 關(guān)聯(lián)矩陣：對于圖G=(V,E), | V |=n, | E |=m, 有mn階矩陣M=(mij) mn，其中: 其他其他的一個端點的一個端點是邊是邊當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)?shù)膬蓚€端點的兩個端點是邊是邊當(dāng)且僅當(dāng)當(dāng)

43、且僅當(dāng)0ev1ev2jijiijm1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4下

44、圖所表示的圖可以構(gòu)造鄰接矩陣M如下:M=（mij）=2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-79-SABCDET2524143175572求任意兩點間最短距離的矩陣算法2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-80- 構(gòu)造任意兩點間直接到達的最短距離矩陣D（0）= dij（0） S A B C D E T S 0 2 5 4 A 2 0 2 7 B 5 2 0 1 5 3 C 4 1 0 4 D 7 5 0 1 5 E 3 4 1 0 7 T 5 7 0D（0）= 構(gòu)造任意兩點間直接到達、或者最多經(jīng)過1個中間點到達的最短距離矩陣D（1）= dij（1）2022-3-23-第6章 圖與網(wǎng)絡(luò)分析

45、-81-其中 dij（1）= min dir（0）+ drj（0） ， S A B C D E T S 0 2 4 4 9 8 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10 C 4 3 1 0 5 4 11 D 9 7 4 5 0 1 5 E 8 5 3 4 1 0 6 T 12 10 11 5 7 0D（1）=irjdir（0）drj（0）rdSE（1）= min dSS（0）+dSE（0）, dSA（0）+dAE（0）, dSB（0）+dBE（0）, dSC（0）+dCE（0）, dSD（0）+ dDE（0） , dSE（0）+ dEE（0）, dST（0）+ dTE

46、（0） =8例如2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-82-其中 dij（2）= min dir（1）+ drj（1） S A B C D E T S 0 2 4 4 8 7 14 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 14 11 9 10 5 6 0D（2）=irjdir（1）drj（1）r 構(gòu)造任意兩點間最多可經(jīng)過3個中間點到達的最短距離矩陣 D（2）= dij（2）2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-83-其中 dij（3）= min dir（2）+

47、 drj（2） S A B C D E T S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0D（3）=irjdir（2）drj（2）r 構(gòu)造任意兩點間最多可經(jīng)過7個中間點到達的最短距離矩陣 D（3）= dij（3）2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-84-說明：一般，對于D（k）= dij（k），其中 dij（k）= min dir（k-1）+ drj（k-1） ，k=0，1，2，3， 最多可經(jīng)過2k-1

48、個中間點： 其數(shù)列為 0，1，3，7，15，31， 2k-1， 收斂條件： 當(dāng) D（k+1）= D（k）時，計算結(jié)束； 設(shè)網(wǎng)絡(luò)中有p個點，即有p-2個中間點，則 2k-1-1 p-2 2k-1 k-1log2 (p-1) k Klog2(p-1)+1，計算到 k=lg(p-1)/lg2 +1時，收斂，計算結(jié)束。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-85- 例：有7個村鎮(zhèn)要聯(lián)合建立一所小學(xué)，已知各村鎮(zhèn)小學(xué)生的人數(shù)大致為S30人， A40人，B20人，C15人，D35人，E25人， T50人。問：學(xué)校應(yīng)建在那一個地點，可使學(xué)生總行程最少？ S A B C D E T S 0 2 4 4 8 7

49、 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0L=30 40 20 15 35 25 50人數(shù)= 1325 1030 880 1035 910 865 1485T解： 如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡(luò)最大流問題。6.5 網(wǎng)絡(luò)最大流問題2022-3-2387一. 網(wǎng)絡(luò)最大流的有關(guān)概念 1. 有向圖與容量網(wǎng)絡(luò)圖中每條邊有規(guī)定指向的圖稱為有向圖，有向圖的邊稱為弧，記作(vi , vj )，表示方向從點 v

50、i 指向點 vj ，有向圖是點與弧的集合，記作 D(V, A )。弧(vi , vj )的最大通過能力，稱為該弧的容量，記為c(vi , vj ) ，或簡記為 cij 。定義了弧容量的網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)。2022-3-2388容量網(wǎng)絡(luò)通常規(guī)定一個發(fā)點(源點，記為s)一個收點(匯點，記為t)，網(wǎng)絡(luò)中其余的點稱為中間點。從發(fā)點到收點之間允許通過的最大流量稱為最大流。多個收(發(fā))點的網(wǎng)絡(luò)可以轉(zhuǎn)換為只含一個收(發(fā))點。2. 流與可行流流是指加在網(wǎng)絡(luò)各條弧上的一組負載量，對加在弧(vi ,vj )上的負載量記作 f (vi , vj ) ，或簡記作 fij ，若網(wǎng)絡(luò)上所有的 fij =0，這個流稱為零流。

51、2022-3-2389以 v( f )表示網(wǎng)絡(luò)中從 st 的流量，則jtjjjsvvfvvffv),(),()(零流是可行流，求最大流就是求v( f )的最大值。稱網(wǎng)絡(luò)上滿足下述條件(1)、(2)的流為可行流：(1) 容量限制條件: 對所有弧有0f (vi , vj ) c (vi , vj )(2) 中間點平衡條件：f (vi , vj ) - f(vj , vi ) =0 (is , t)2022-3-2390二. 割和流量割(集）是指將容量網(wǎng)絡(luò)中的發(fā)點和收點分割開，并使st 的流中斷的一組弧的集合（截集）弧旁數(shù)字為 cij ( fij ) 有不同的割見教材161頁上圖中 KK 將網(wǎng)絡(luò)上的

52、點分割成 V 和 兩個集合，并有 sV , t ，稱弧的集合 (V, )=(v1 , v3) , (v2 , v4)是一個割。注意，這里不包含(v3 , v2) 。VVV2022-3-2391割的容量是組成它的集合中各弧容量之和，用c(V, )表示，V),(),(),(),(VVjijivvcVVc f (V, ) 表示通過割 (V, ) 中所有 V 方向弧的流量的總和; f ( ,V ) 表示通過割 中所有 V方向弧的流量的總和，則有：VVVVV),(),(),(),(),(),( , ),(),(VVijijVVjijivvfVVfvvfVVf2022-3-2392從 st 的流量等于通過

53、割的從V 的流量減 V的流量，有：VV),(),()(VVfVVffv用 v*( f ) 表示網(wǎng)絡(luò)中從 st 的最大流，則有),(),()(*VVfVVffvV),(),(),()(*VVcVVfVVffv因此，上例中最大流不會超過14（所有割集中最小者） 。最大流 v*( f ) 應(yīng) 最小割的容量(用 c*(V, )表示)定理：網(wǎng)絡(luò)的最大流量等于它的最小割集的容量。定理：網(wǎng)絡(luò)的最大流量等于它的最小割集的容量。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-93- 有向圖：含有以箭頭指示方向的邊的網(wǎng)絡(luò)圖。 弧：有向圖上的邊稱為弧。用（vi,vj）表示。 弧的容量：弧上通過負載的最大能力，簡稱容量。以

54、cij表示。 流：加在網(wǎng)絡(luò)每條弧上的一組負載量，以fij表示。 可行流：能夠通過網(wǎng)絡(luò)的負載量，通常應(yīng)滿足兩個條件： 容量限制條件：對所有的弧，0 fijcij 中間點平衡條件：對任何一個中間點，流入量=流出量 發(fā)點、收點、中間點：流的起源點稱發(fā)點，終到點稱收點，其余的點稱中間點。 最大流；能夠通過網(wǎng)絡(luò)的最大流量。 割集：一組弧的集合，割斷這些弧，能使流中斷。簡稱割。 割的容量：割集中各弧的容量之和。 最小割：所有割集中容量之和為最小的一個割集。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-94-定理：當(dāng)網(wǎng)絡(luò)中不存在任何增廣鏈時，則網(wǎng)絡(luò)達到最大流狀態(tài)。二、最大流最小割定理 前向弧+：一條發(fā)點到收點鏈

55、中，由發(fā)點指向收點的弧，又稱正向弧。 后向弧-：一條發(fā)點到收點鏈中，由收點指向發(fā)點的弧，又稱逆向弧。 增廣鏈：由發(fā)點到收點之間的一條鏈，如果在前向弧上滿足流量小于容量，即fij0，（反向弧非零流），則稱這樣的鏈為增廣鏈。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-95-三、網(wǎng)絡(luò)最大流的標(biāo)號算法(Ford-Fulkerson標(biāo)號算法)基本思想：尋找增廣鏈，改善流量分布；再重復(fù)，直到不 存在任何增廣鏈為止。步驟： 給始點標(biāo)號：（0，+） 從已標(biāo)號點i出發(fā)，看與其相關(guān)聯(lián)的未標(biāo)號點j上的弧，對+，若有0fijcij，則可對j點標(biāo)號，記（i, (j)）， 其中 (j)=min (i) ，cij - fij

56、對-，若有0 fji cij，也可對j點標(biāo)號，記（ i, (j)）， 其中 (j)=min (i) ，fji （注：若有多個可標(biāo)號點，可任選其中之一。）若標(biāo)號中斷，則得到最大流狀態(tài)，否則，重復(fù)，繼續(xù)標(biāo)號，至收點得到標(biāo)號，轉(zhuǎn)。2022-3-23-第6章 圖與網(wǎng)絡(luò)分析-96-當(dāng)收點得到標(biāo)號，則沿標(biāo)號得到的增廣鏈進行流量調(diào)整： 對+，fij = fij + (t) 對-，fij = fij - (t) 其余弧上的流量不變。 重復(fù)上述過程。 最小割集：已標(biāo)號點集合與未標(biāo)號點集合相連接的弧中， 流量=容量的弧。97找可行流找可行流給給S 標(biāo)號標(biāo)號( S， ) ) t 是否已是否已 標(biāo)號標(biāo)號 是否存在已標(biāo)

57、號是否存在已標(biāo)號 但未檢查的點但未檢查的點 倒向追蹤倒向追蹤找出增廣鏈找出增廣鏈 令調(diào)整量令調(diào)整量求改進的可行流求改進的可行流+ijij-ijijijijijf +v ,vf = f -v ,vfv ,vt=vlf不存在關(guān)于不存在關(guān)于的增廣鏈的增廣鏈即為最大流即為最大流 i 已已 標(biāo)號標(biāo)號,但未檢查但未檢查 對對i 進行檢查，并對進行檢查，并對j 標(biāo)號標(biāo)號: 若，且，對若，且，對j 標(biāo)號標(biāo)號: ，ijv ,vAijijfcijv , (v )l jiijijv =minv ,c -fll 若，且，對若，且，對j 標(biāo)號標(biāo)號: ，jiv ,vAji0fij-v , (v )ljijivminv ,

58、 cll 是是否否2022-3-2398例：用標(biāo)號法求下述網(wǎng)絡(luò)圖 s t 的最大流量，并找出該網(wǎng)絡(luò)圖的最小割。2022-3-2399解：(1) 先給 s 點標(biāo)號 (0 , )；2022-3-23100 (2) 從 s 點出發(fā)的弧 (s , v2)，因有 fs20 ，且(v1)=min(v2) , f12)=2故對 v1 點標(biāo)號(v2 , 2)。 (v2 , v4)飽和，不標(biāo)號。2022-3-23102 (4) 弧 (v1 , v3)，因有 f130 ，且(v4)=min(v3) , f43)=1故對 v4 點標(biāo)號(v3 , 1)。 (v3 , t)飽和，不標(biāo)號, v2 已標(biāo)號。2022-3-2

59、3104(6) 弧 (v4 , t)，因有 f4tc4t ，且(t)=min(v4) , (c4t - f4t)=1故對 t 點標(biāo)號(v4 , 1)。2022-3-23105(7) 由于收點 t 得到標(biāo)號，用反追蹤法找出網(wǎng)絡(luò)圖上的一條增廣鏈。2022-3-23106(8) 修改增廣鏈上各弧的流量：918)(011)(514)(314)(615)(4443431313121222tfftfftfftfftffttss非增廣鏈上的所有弧流量不變，這樣得到網(wǎng)絡(luò)圖上的一個新的可行流。2022-3-23107重復(fù)上述標(biāo)號過程，由于對點 s 、v1 、v2 、v3 標(biāo)號后，標(biāo)號中斷，故圖中的可行流即為最大

60、流，v*( f )=14已標(biāo)號點集為V =s , v1 , v2 , v3 ，未標(biāo)號點集 ，(V , ) =(3 , t) , (2 , 4)為網(wǎng)絡(luò)的最小割。VV2022-3-23108三. 應(yīng)用舉例例1：P166，例7ADECBF2321211111、方向含義2、E、D之間3、數(shù)字含義切斷A、F之間的通路，相當(dāng)于求最小割集。2022-3-23109例2：P167，例81、匹配關(guān)系1234562、匹配限制145f=1 f14 f152022-3-23110134f=1 f34 f14 3、等價網(wǎng)絡(luò)圖123456st111111111111例 用標(biāo)號算法求下圖中st的最大流量，并找出最小割。v1