第八章圖與網絡分析2ppt課件

1、第第1頁頁第八章第八章圖與網絡分析圖與網絡分析 最短路問題最短路問題 網絡最大流問題網絡最大流問題 最小費用最大流問題最小費用最大流問題 第第2頁頁第八章第八章圖與網絡分析圖與網絡分析 最短路問題最短路問題 網絡最大流問題網絡最大流問題 最小費用最大流問題最小費用最大流問題 第第3頁頁最短路問題最短路問題第第4頁頁最短路問題提出最短路問題提出在現(xiàn)實生活中，除公路運輸網絡、電訊網絡在現(xiàn)實生活中，除公路運輸網絡、電訊網絡等網絡圖以外，還有輸油管線這樣的圖。在輸油等網絡圖以外，還有輸油管線這樣的圖。在輸油管線圖中，為反映油的輸送情況，兩點間不僅有管線圖中，為反映油的輸送情況，兩點間不僅有連線，線上往

2、往還標有箭頭，以表示油的流動方連線，線上往往還標有箭頭，以表示油的流動方向。又如，指揮系統(tǒng)圖、控制系統(tǒng)圖等圖中都標向。又如，指揮系統(tǒng)圖、控制系統(tǒng)圖等圖中都標有指向。從這樣的一類圖中就可以概括為有向圖有指向。從這樣的一類圖中就可以概括為有向圖的概念。的概念。第第5頁頁有向網絡與混合圖有向網絡與混合圖 如果在圖如果在圖D=D=（V V，A A中，給每一弧賦予權值，如中，給每一弧賦予權值，如 將弧將弧aij=(vi,vj)aij=(vi,vj)有權值有權值 wij wij，記為，記為w(aij)=wijw(aij)=wij則賦權有向圖則賦權有向圖D=D=（V V，A A稱為有向網稱為有向網絡，在不至

3、于混淆時，也簡稱網絡。絡，在不至于混淆時，也簡稱網絡。 混合圖如果一個圖中既有邊，也有弧，那么稱這混合圖如果一個圖中既有邊，也有弧，那么稱這種圖為混合圖。它往往出現(xiàn)在既有單行線，又有種圖為混合圖。它往往出現(xiàn)在既有單行線，又有雙行線的交通圖中。雙行線的交通圖中。12534372第第6頁頁最短路問題引例最短路問題引例下圖為單行線交通網，每弧旁的數(shù)字表示通過這條下圖為單行線交通網，每弧旁的數(shù)字表示通過這條線所需的費用?，F(xiàn)在某人要從線所需的費用。現(xiàn)在某人要從v1v1出發(fā)，通過這個交出發(fā)，通過這個交通網到通網到v8v8去，求使總費用最小的旅行路線。去，求使總費用最小的旅行路線。v2v523464v3v1

4、v4v6121061210v8v9v72363從從v1v1到到v8v8：P1=P1=（v1v1，v2v2，v5v5，v8v8） 費用費用 6+1+6=13 6+1+6=13P2=P2=（v1v1，v3v3，v4v4， v6 v6， v7 v7， v8 v8） 費用費用 3+2+10+2+4=21 3+2+10+2+4=21P3= P3= 從從v1v1到到v8v8的旅行路線的旅行路線 從從v1v1到到v8v8的路。的路。旅行路線總費用旅行路線總費用 路上所有弧權之和。路上所有弧權之和。最短路問題中，不考慮有向環(huán)、并行弧。最短路問題中，不考慮有向環(huán)、并行弧。v2v523464v3v1v4v6121

5、061210v8v9v72363第第8頁頁幾個概念幾個概念路：設路：設p是是D中一個首尾相連的弧的集合，如果中一個首尾相連的弧的集合，如果vs是是它的第一條弧的始點，它的第一條弧的始點，vt是它的最后一條弧的是它的最后一條弧的終點，則稱它是以點終點，則稱它是以點vi為始點，以點為始點，以點vt為終點的為終點的一條路。一條路。路長：路路長：路p中所有弧的權值的和稱為路中所有弧的權值的和稱為路p的長，記為的長，記為設圖設圖D=D=（V V，A A是一有向網絡是一有向網絡paijijawpw)()( v2v523464v3v1V4 v6121061210v8v9v72363第第9頁頁設設P P是以點

6、是以點vsvs為始點，以點為始點，以點vtvt為終點的所有路的集合，為終點的所有路的集合， 假如假如 , ,且且 ，則稱，則稱p0p0是以點是以點vsvs 為始點，以點為始點，以點vtvt為終點的最短路。而稱其路長為為終點的最短路。而稱其路長為點點 vs vs到點到點vtvt的距離，記為的距離，記為 。幾個概念幾個概念Pp 0)()(0pwMinpwPp)(),(0pwvvdts注意：在有向網絡中注意：在有向網絡中, ,一般一般),(),(sttsvvdvvd最短路及一點到另一點的距離最短路及一點到另一點的距離第第10頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近

7、算法逐步逼近算法 路矩陣算法路矩陣算法第第11頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第12頁頁求解最短路問題的求解最短路問題的Dijkstra算法算法條件：當所有條件：當所有wij0時，用來求給定點時，用來求給定點vs到任一到任一個點個點vj最短路的公認的最好方法。最短路的公認的最好方法。事實：如果事實：如果P是是D中從中從vs到到vj的最短路，的最短路，vi是是P中的一中的一基解基解個點，那么，從個點，那么，從vs沿沿P到到vi的路是從的路是從vs到到vi的的最基解最基解短路。短路。 Dijkstra算法是Dijk

8、stra在1959年提出的，可用于求解指定兩點間的最短路問題，或從指定點到其余各點的最短路問題。由于其以標號為主要特征，又稱為標號法。v1v2v3v4v5最短路的子路是最短路最短路的子路是最短路第第13頁頁Dijkstra算法算法0ijw 第第14頁頁 1. 1.標號標號 P P固定標號或永久性標號）固定標號或永久性標號）從始點到該標號點的最短路權從始點到該標號點的最短路權ui ui 。 2. 2.標號標號 T T臨時性標號）臨時性標號）從始點到該標號點的最短路權上界從始點到該標號點的最短路權上界ui ui 。選用符號的意義選用符號的意義P( i, ui)3.前點標號前點標號i表示點表示點vs

9、到到vj的最短路上的最短路上vj的前一點。的前一點。T( i, ui)Dijkstra算法步驟：算法步驟： ijijjwvPvTvT)(),(min)( ,)ijv vE0)(1 vP0jv )()(min0jsvjvTvTj 1,6圖上標號法圖上標號法v5v223464v3v1v4121061210v8v9v72363v60,01,1,1,31,1,1,1,11,1永久標號永久標號永久標號永久標號臨時標號臨時標號1,6圖上標號法圖上標號法v5v223464v3v1v4121061210v8v9v72363v60,01,1,11,1,31,1,1,0,01,14,111,3永久標號永久標號臨時

10、標號臨時標號v5v223464v3v1v4121061210v8v9v72363v60,01,1,1,11,1,1,1,3圖上標號法圖上標號法4,111,31,63,53,5永久標號永久標號臨時標號臨時標號v5v223464v3v1v4121061210v8v9v72363v60,01,4,111,11,1,1,1,3圖上標號法圖上標號法3,52,62,6永久標號永久標號臨時標號臨時標號v5v223464v3v1v4121061210v8v9v72363v60,01,4,111,11,1,1,35,125,95,9圖上標號法圖上標號法3,52,6永久標號永久標號臨時標號臨時標號v5v22346

11、4v3v1v4121061210v8v9v72363v60,04,111,11,5,121,35,95,123,52,6圖上標號法圖上標號法永久標號永久標號臨時標號臨時標號4,11v5v223464v3v1v4121061210v8v9v72363v64,110,01,11,1,35,123,52,6圖上標號法圖上標號法5,9永久標號永久標號臨時標號臨時標號標號結束標號結束反向追蹤反向追蹤第第23頁頁例例 求如下交通網絡中各對點間最短路路長。求如下交通網絡中各對點間最短路路長。DijkstraDijkstra算法標號法算例算法標號法算例31025v4v1v2v5v312262448混合圖混合圖

12、第第24頁頁 無向網絡無向網絡: :負權弧時。負權弧時。wijvivjwijwijvjvi無向網絡中，最短路無向網絡中，最短路最短鏈。最短鏈。多個點對之間最短路？多個點對之間最短路？v1v2v312-3Dijkstra算法失效算法失效Dijkstra算法注意的問題算法注意的問題逐步逼近算法逐步逼近算法路矩陣算法路矩陣算法第第25頁頁5727461263202657710v3v1v2v4v5v6v7練習：求如下無向網絡中練習：求如下無向網絡中v1v1到到v7v7的最短路的最短路Dijkstra算法求最短鏈算法求最短鏈第第26頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步

13、逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第27頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第28頁頁逐次逼近算法逐次逼近算法 計算指定點計算指定點v1v1到其余各點的最短路時，到其余各點的最短路時，某些問題會出現(xiàn)有負權弧的圖某些問題會出現(xiàn)有負權弧的圖, ,如：如： 此時此時DijkstraDijkstra算法標號法有可能失效。算法標號法有可能失效。逐次逼近法對于這類問題的解決很有幫助。逐次逼近法對于這類問題的解決很有幫助。 v1v2v312-3第第29頁頁逐次逼近算法思想逐次逼近算法思想該公式表明，該公式表明，P(1)

14、1j中的第中的第j個分量等于個分量等于P(0)1j的分量的分量與基與基本表中第本表中第j列相應元素路長的最小值，它相當于在點列相應元素路長的最小值，它相當于在點v1與與vj之間插入一個轉接點之間插入一個轉接點v1,v2,vn中的任一個，含點中的任一個，含點v1與與vj后所有可能路中的最短路的路長；每迭代一次，就相后所有可能路中的最短路的路長；每迭代一次，就相當于增加一個轉接點，而當于增加一個轉接點，而P(k)1j中的每一個分量則隨著中的每一個分量則隨著k的的增增加呈不增的趨勢，直到出現(xiàn)穩(wěn)定。加呈不增的趨勢，直到出現(xiàn)穩(wěn)定。)1(11)(1ijkinikjwPMinP第第30頁頁用于計算指定點用于

15、計算指定點v1v1到其余各點的最短路到其余各點的最短路)1(11)(1ijkinikjwPMinPj=1,2,n. k=1,2,tn.2.2.計算計算逐次逼近算法基本步驟逐次逼近算法基本步驟jjwP1)0(1 j=1,2,n.1.1.令令(k)(1)11kjjPP其元素既是其元素既是v1v1到到vjvj的最短路長。的最短路長。3.3.當出現(xiàn)當出現(xiàn)時，時，例例 計算從點計算從點v1v1到所有其它頂點的最短路到所有其它頂點的最短路解：初始條件為解：初始條件為 3, 5, 2, 0114113112111PPPP 以后按照公式以后按照公式 進行迭代。進行迭代。 直到得到直到得到 ，迭代停止。，迭代停

16、止。v1v2v3v4v6v5v8v72-35467-24-3342-1)1(11)(1ijkinikjwPMinP) 1(1)(1tjtjPPv1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij 11jP 21jP 31jP 41jP 51jP 61jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-2042000253021230312561361102123031256123661368150212303123653123661236613687141236810021230312365312366123687912

17、3681002123031236612368791236810123653利用下利用下標追蹤標追蹤路徑路徑第第33頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第34頁頁最短路問題求解方法最短路問題求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩陣算法路矩陣算法第第35頁頁 某些問題需要求網絡上任意兩點間的最短路。某些問題需要求網絡上任意兩點間的最短路。當然，它也可以用標號算法依次改變始點的辦法當然，它也可以用標號算法依次改變始點的辦法來計算，但是比較麻煩。來計算，但是比較麻煩。 這里介紹這里介紹Floyd

18、Floyd在在19621962年提出的路矩陣法，年提出的路矩陣法，它可直接求出網絡中任意兩點間的最短路。它可直接求出網絡中任意兩點間的最短路。FloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想第第36頁頁 網絡D=（V，A，W），令U=(dij)nn， 表示D中vi到vj的最短路的長度。iju 考慮D中任意兩點vi，vj，如將D中vi，vj以外的點都刪掉，得只剩vi，vj的一個子網絡D0，記ij(0)ij ,A ijwv vd當否wij為弧（為?。?vi，vj的權。的權。 在D0中加入v1及D中與vi，vj，v1相關聯(lián)的弧，得D1，D1中vi到vj的最短路記為 ,則一定有(1)i

19、jd(1)(0)(0)(0)i11j min, ijijddddvivjv1wijFloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想第第37頁頁 再在D1中加入v2及D中與vi，vj，v1， v2相關聯(lián)的弧，得D2，D2中vi到vj的最短路長記為 ，則有(2)ijd(2)(1)(1)(1)iji22 j min, ijdddd隨著轉接點的逐步增加隨著轉接點的逐步增加, ,我們會發(fā)現(xiàn)我們會發(fā)現(xiàn) 二指定點間路的條數(shù)也會隨之增加，但是其最短路二指定點間路的條數(shù)也會隨之增加，但是其最短路及路長可以確定；及路長可以確定； 當當V V中所有的點都可以作為轉接點時，指定點中所有的點都可以作為轉

20、接點時，指定點vivi到到vjvj間所有路中的最短路自然是圖中指定點間所有路中的最短路自然是圖中指定點vivi到到vjvj間的最短路。間的最短路。FloydFloyd算法算法( (路矩陣法路矩陣法) )思想思想第第38頁頁FloydFloyd算法算法( (路矩陣法路矩陣法) )步驟步驟設有有向網絡設有有向網絡D=D=（V V，A A），其權矩陣為），其權矩陣為A=(aij)nnA=(aij)nn，AvvjiAvvwajijiijij),( , 0),( ,如下構造路矩陣序列：如下構造路矩陣序列：則則n n階路矩陣階路矩陣D(n)D(n)中的元素中的元素d(n)ijd(n)ij就是就是vivi到

21、到vjvj的最短路的路長。的最短路的路長。令權矩陣令權矩陣A為初始路矩陣為初始路矩陣D0），即令），即令D0）=A2. 2. 依次計算依次計算K K階路矩陣階路矩陣D DK K）= =（d(k)ijd(k)ijnn, k=1,2,nnn, k=1,2,n，,) 1() 1() 1()(kkjkikkijkijdddMind這里這里第第39頁頁路矩陣序列的含義路矩陣序列的含義 K K階路矩陣階路矩陣D DK K） 其中的元素表示相應兩點間可能以點其中的元素表示相應兩點間可能以點v1v1、v2v2、vkvk為為 轉接點的所有路中路長最短的路的路長。轉接點的所有路中路長最短的路的路長。D0）其中的任

22、一元素表示相應兩點間無轉接點時最短路路長。其中的任一元素表示相應兩點間無轉接點時最短路路長。一階路矩陣一階路矩陣D D1 1） 其中的元素表示相應兩點間可能以點其中的元素表示相應兩點間可能以點v1v1為轉接點的所為轉接點的所有路中路長最短的路的路長；有路中路長最短的路的路長；為使計算程序化，轉接點按頂點下標的順序依次加入為使計算程序化，轉接點按頂點下標的順序依次加入n n階路矩陣階路矩陣D(n)D(n) 其中的元素其中的元素d(n)ijd(n)ij就是就是vivi到到vjvj的可能以點的可能以點v1v1、v2v2、vnvn為轉接點的所有路中路長最短的路的路長。既是為轉接點的所有路中路長最短的路

23、的路長。既是vivi到到vjvj的最短路的路長。的最短路的路長。第第40頁頁例例 求如下交通網絡中各對點間最短路路長。求如下交通網絡中各對點間最短路路長。051250 102 A2302826042440該圖的權矩陣為：該圖的權矩陣為：FloydFloyd算法算法( (路矩陣法路矩陣法) )算例算例31025v4v1v2v5v312262448第第41頁頁例例 求如下交通網絡中各對點間最短路路長。求如下交通網絡中各對點間最短路路長。FloydFloyd算法算法( (路矩陣法路矩陣法) )算例算例 0051250 102 D =A230282604244031025v4v1v2v5v312262

24、448 0051250 102 D =A2302826042440(1)(0)(0)(0)i11j min, ijijdddd利用公式利用公式發(fā)現(xiàn)第一行，第一列元素不變發(fā)現(xiàn)第一行，第一列元素不變 105125 D220213621472302841274133042440031025v4v1v2v5v312262448 105125 D2202136214723028412741330424400(2)(1)(1)(1)i22j min, ijijdddd利用公式利用公式發(fā)現(xiàn)第二行，第二列元素不變發(fā)現(xiàn)第二行，第二列元素不變 255 D021362341272214721470232554133

25、44400121257202521731025v4v1v2v5v312262448 255 D0213621472302325541274133042440012214712572025217(3)(2)(2)(2)i33j min, ijijdddd利用公式利用公式發(fā)現(xiàn)第三行，第三列元素不變發(fā)現(xiàn)第三行，第三列元素不變0 3 D21363232554133412001324213256502147224132604531624031025v4v1v2v5v31226244802147204127042400221471257 3 D2136323255413341200132421325650

26、21472241326045316240 4 D0213623032552011325/1456202413264133440221472531/5416413245(4)(3)(3)(3)i44j min, ijijdddd利用公式利用公式發(fā)現(xiàn)第四行，第四列元素不變發(fā)現(xiàn)第四行，第四列元素不變31025v4v1v2v5v31226244831025v4v1v2v5v312262448 4 D021362147230325502401202413264133440221472531/54164132451325/1456 5 D0213621472303255024012024132641334

27、40221472531/54164132451325/1456D(5)中的元素給出相應兩點間中的元素給出相應兩點間的最短路，其下標給出最短路的最短路，其下標給出最短路個頂點下標個頂點下標,比如：比如：第第47頁頁練習練習 已知有已知有7 7個村子，相互間道路的距離如下圖個村子，相互間道路的距離如下圖示。擬合建一所小學，已知示。擬合建一所小學，已知A A處有小學生處有小學生3030人，人，B B處處4040人，人，C C處處2525人，人，D D處處2020人，人，E E處處5050人，人，F(xiàn) F處處6060人，人， G G處處6060人人, ,問小學應建在哪一個村子，使學生上學最問小學應建在哪

28、一個村子，使學生上學最方便原則所有人走的總路程最短；盡可能公方便原則所有人走的總路程最短；盡可能公平。）。平。）。FloydFloyd算法算法( (路矩陣法路矩陣法) )算例算例AGFECB522747163D26第第48頁頁第八章第八章圖與網絡分析圖與網絡分析 最短路問題最短路問題 網絡最大流問題網絡最大流問題 最小費用最大流問題最小費用最大流問題 第第49頁頁第八章第八章圖與網絡分析圖與網絡分析 最短路問題最短路問題 網絡最大流問題網絡最大流問題 最小費用最大流問題最小費用最大流問題 第第50頁頁網絡最大流問題網絡最大流問題50年代福特年代福特Ford）、富克遜）、富克遜Fulkerson

29、建立建立的的“網絡流理論網絡流理論”，是網絡應用的重要組成部分。，是網絡應用的重要組成部分。第第51頁頁問題的提出問題的提出 在一個輸油管網中，有生產石油的油井、儲存石油的油在一個輸油管網中，有生產石油的油井、儲存石油的油庫、轉運石油的中間泵站，同時，還有各種口徑不同的輸油庫、轉運石油的中間泵站，同時，還有各種口徑不同的輸油管。當一個輸油管網給定后，單位時間內最多可把多少石油管。當一個輸油管網給定后，單位時間內最多可把多少石油從油井輸送到油庫？具體方案如何？從油井輸送到油庫？具體方案如何？ 分析：就輸油管網絡問題，可用頂點表示油井、油分析：就輸油管網絡問題，可用頂點表示油井、油庫和中間泵站，用

30、有向邊表示輸油管，用有向邊上庫和中間泵站，用有向邊表示輸油管，用有向邊上的權表示單位時間沿相應的輸油管可以輸送石油的的權表示單位時間沿相應的輸油管可以輸送石油的最大數(shù)量容量）。最大數(shù)量容量）。 第第52頁頁tvsv1234,v v v vtvsv問題的提出問題的提出管道網絡中每邊的最大通過能力即容量是有限的，實際流管道網絡中每邊的最大通過能力即容量是有限的，實際流量也不一定等于容量，上述問題就是要討論如何充分利用量也不一定等于容量，上述問題就是要討論如何充分利用裝置的能力，以取得最好效果流量最大），這類問題通裝置的能力，以取得最好效果流量最大），這類問題通常稱為最大流問題。常稱為最大流問題。v

31、sv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第第53頁頁容量容量發(fā)點源）發(fā)點源）收點匯）收點匯）中間點中間點容量網絡容量網絡( ,)ijDv v的每條弧上有非負數(shù)的點的點一個入次為一個入次為0sv的點的點一個出次為一個出次為0tv其余點其余點( , ,)DV A Cijc網絡有向圖網絡有向圖D=D=（V V，A A，C C） 網絡上流的基本概念網絡上流的基本概念vsv1v3vtv2v48799562510第第54頁頁流流( ,)ijijv vf對D中任一弧都給定一個實際流量ijff 集合集合(1)(2)滿足下面條件的流：容量限制條件中間點平衡

32、條件ijijcf 0 jijkkiff輸出量輸出量中間點的輸入量中間點的輸入量 ( )( )sjjtjjv fstv fff用表示網絡中從的流量 vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)00f 任何網絡必存在可行流，如流量為 的可行流：運輸問題中，每個運運輸問題中，每個運輸方案就是一個流輸方案就是一個流可行流可行流第第55頁頁 ( )ijfv f在容量網絡中，尋求一個流使其流量最大網絡最大流問題網絡最大流問題ijijcf 0( )0( )ijjiv fffv f( , )tjv vA()is(, )is t()i t且滿足此為一個特殊的

33、線性規(guī)劃問題，將會看到利用圖的特點，此為一個特殊的線性規(guī)劃問題，將會看到利用圖的特點，解決這個問題的方法要比單純形法較為直觀方便。解決這個問題的方法要比單純形法較為直觀方便。第第56頁頁設設是網絡是網絡D=（V，A，C的一個可行流的一個可行流（v1，v2是飽和的是飽和的2、如果、如果fij0，該弧是非，該弧是非0?。换。唬╲1，v2是非是非0弧弧3、如果、如果fij=0，該弧是，該弧是0流??；流弧；弧關于流的分類弧關于流的分類ijffv1v2v1v2第第58頁頁割集和割集的容量割集和割集的容量vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)(1

34、11VVVV和11,VvVvts1V1V),(11VV設有網絡設有網絡D=V，A，C，點，點vs與點與點vt的是集合的是集合V中中的任意兩點，若點集的任意兩點，若點集V被剖分成兩個非空集被剖分成兩個非空集合合，使，使，記以，記以中的點為始點，中的點為始點，的的A A中弧的集合記為中弧的集合記為則稱這個弧的集合是分離點則稱這個弧的集合是分離點vs與點與點vt的割集又稱截集）。的割集又稱截集）。中的點為終點中的點為終點割集的容量是割集中各弧的容量之和，用割集的容量是割集中各弧的容量之和，用 表示。表示。11( ,)c V V1324( ,),(,)v vv v112134 , , tVs v vV

35、v v v割集的容量為割集的容量為9+9=189+9=18割集割集如圖如圖KK割集的意義：若把某一割集的弧從網絡中丟去，則從割集的意義：若把某一割集的弧從網絡中丟去，則從vs到到vt便不存便不存路，即割集是從路，即割集是從vs到到vt的必經之道！這里的必經之道！這里(v3,v2)不屬于此割集不屬于此割集第第59頁頁考慮考慮KK的不同畫法的不同畫法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)1234,v v v v t34(, ),(, )v tvt12( ,),( ,)s vs v1 , s v s2 ,s v12 ,s v v13 ,s

36、v v24 ,s v v123 ,s v v v124 ,s v v v1234 ,s v v v v234,v v v t134,v v v t134,v v v t24,v v t13,v v t1234,v v v v t4,v t t21213( ,),(,),(,)s vv vv v124( ,),(,)s vvv1324(,),(,)v vvv212323( ,),(,),(,),(, )s vv vv vv t1434( ,),(,),(, )s vvvvt243(,),(, )vvv t13434(,),(,),(, )v vvvvt152117181924142515VV割集

37、割集割集容量割集容量由于有限網絡的割集只有有限多個，則截集容量的集由于有限網絡的割集只有有限多個，則截集容量的集合合是有限的實數(shù)集合，令是有限的實數(shù)集合，令稱割集容量為稱割集容量為C0的割集為的割集為D的最小截集。的最小截集。11(,)C V V011 ( ,)Cmin C V V第第60頁頁111111( , ,),( ),( ,),( ,)( )( ,)ststfDV A CvvW fV Vv vV VW fC V V設 為網絡的任一可行流( 為發(fā)點為收點），流量為是分離的任一割集，割集容量為C則有基本定理基本定理(可行流與割集的關系可行流與割集的關系)割集的意義：若把某一割集的弧從網絡中

38、丟去，則從割集的意義：若把某一割集的弧從網絡中丟去，則從vs到到vt便不存便不存路，即割集是從路，即割集是從vs到到vt的必經之道！的必經之道！最大流最大流-最小割定理：最小割定理：的最小割的容量的最小割的容量分離分離的最大流的流量的最大流的流量到到從從中，中，任一個網絡任一個網絡tstsvvvvG, 的的可可增增廣廣鏈鏈到到不不存存在在從從是是最最大大流流可可行行流流tsvvf第第61頁頁鏈及可增廣鏈鏈及可增廣鏈鏈鏈在最大流問題中，研究的是有向網絡圖。在最大流問題中，研究的是有向網絡圖。但是在求最大流的方法中，則要使用無向但是在求最大流的方法中，則要使用無向網絡中的鏈。這時，就要將它看成無向

39、網網絡中的鏈。這時，就要將它看成無向網絡圖，即將網絡中的弧看成邊。那么，以絡圖，即將網絡中的弧看成邊。那么，以發(fā)點發(fā)點vsvs為始點、以收點為始點、以收點vtvt為終點的點、邊為終點的點、邊交錯序列即無向圖中的鏈稱為連接點交錯序列即無向圖中的鏈稱為連接點vsvs、vtvt的鏈，并用其頂點序列來表示。的鏈，并用其頂點序列來表示。第第62頁頁( ,)( ,)ijijijijijfv vffv vf非增廣鏈上的弧(,)(,)min0ijijijijijijijcfv vfv v()( )v fv f,ststvvvvD中，若 為從 到 的一條鏈，給 定向為從 到前向弧集 ：與 同向后向弧集 ：與 反

40、向，11fc30f 10nf22fcnnfc0( ,)0( ,)ijijijijijijstffcv vfcv vvv 是可行流，若則稱 為從 到 的可增廣鏈。非飽和弧非飽和弧非非0流弧流弧可增廣鏈可增廣鏈第第63頁頁這樣就得到了一個尋求最大流的方法這樣就得到了一個尋求最大流的方法(算法思想算法思想)：從一個可行流開始，尋求關于這個可行流的可增從一個可行流開始，尋求關于這個可行流的可增廣鏈，若存在，則可以經過調整，得到一個新的廣鏈，若存在，則可以經過調整，得到一個新的可行流，其流量比原來的可行流要大，重復這個可行流，其流量比原來的可行流要大，重復這個過程，直到不存在關于該流的可增廣鏈時過程，直

41、到不存在關于該流的可增廣鏈時就得到了最大流。就得到了最大流。沿著這條鏈從沿著這條鏈從 vs vs 到到 vt vt 輸送流，還有潛力可挖，輸送流，還有潛力可挖，只需按照調整方法，就可以把流量提高，調整后只需按照調整方法，就可以把流量提高，調整后的流，在各點仍滿足平衡條件及容量限制條件，的流，在各點仍滿足平衡條件及容量限制條件，即仍為可行流。即仍為可行流。可增廣鏈的實際意義可增廣鏈的實際意義第第64頁頁求解最大流的標號算法：求解最大流的標號算法：1.()1( ,)2,:( ),min,(,)( )0,min,(,)(3)(2siijjiijijjijijiijjijijjiiijvvvvavvf

42、ccfvbvvffv 標號過程 尋找可增廣鏈 ：（ ）給 以標號（ ）對已標號的對于 的所有未標號的鄰接點若是 發(fā)出的前向非飽和弧的終點， 即令標號為；否則不標號對是 發(fā)出的后向非零弧的起點， 即令標號為；否則不標號重復)2.121tstijtijijtijvvvfffff直到 若 未得到標號，說明不存在 到 的增廣鏈； 否則按如下方法調整。調整過程（增加流量）：增廣鏈上的前向弧（ ）令增廣鏈上的后向弧不在增廣鏈上（ ）去掉所有標號，回到第 步，對可行流重新標號。()( )tw fw f則有第第65頁頁1v2v3vb) b) 接著檢查與相鄰接的點接著檢查與相鄰接的點1v3v2v4v5vsvtv

43、6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),( 已飽和，流量不可再增。再檢查已飽和，流量不可再增。再檢查 ，可調整量為，可調整量為 4-2=2，可提供量可提供量+，取調整量，取調整量1v2v2min42,2 先給標號先給標號 （，+）1） 尋找可增廣鏈：尋找可增廣鏈：sv第第66頁頁1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),(3v)

44、 1,(sv 下對已標號點可望調整點接著向下檢查。下對已標號點可望調整點接著向下檢查。 已飽已飽 和。再檢查與和。再檢查與 相鄰接且未標號的點相鄰接且未標號的點 6v2v,5v6v給給 標號標號 ，其中，其中 表示表示 的所調整量的所調整量2來自來自 ，且為正向流向前流）且為正向流向前流） 。)2 ,(svsv2vsv2v)2 ,(sv) 1 ,(sv第第67頁頁調整量為調整量為1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(

45、sv5min30, 22)2 ,(2v5v給給 標號為標號為)2 ,(2v第第68頁頁1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v可令調整量為可令調整量為1min3, 22)2 ,(5v給給 標號為標號為)2 ,(5v1v表示可控量，反方向流量。表示可控量，反方向流量。5v, 015 fd) 檢查與 相鄰接且未標號的點 ， 。而 對 來講是流入，現(xiàn)欲增加流出量，應壓縮 的流入量，只要的流入量1vtv1v5

46、v1v第第69頁頁1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5vf) 下面檢查與下面檢查與 相鄰接且未標號的點相鄰接且未標號的點 ，同理，調整量：，同理，調整量：1v4v4min52, 22給給 標號為標號為).2 ,(1v4v)2 ,(1v)2 ,(4vg) 最后，給最后，給 標號標號tv).2 ,(4vmin42, 22t第第70頁頁1v3v2v4v5vsvtv6v)5 , 5()2 ,

47、3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v2調整流量：從調整流量：從 到到 所畫出的紅線即為可增廣鏈。沿所畫出的紅線即為可增廣鏈。沿該可增廣鏈，從該可增廣鏈，從 倒推，標倒推，標“”號的在實際流量上加上號的在實際流量上加上該調整量，標該調整量，標“”符號的在實際流量上減去該調整量。完符號的在實際流量上減去該調整量。完成調整過程。成調整過程。svtvtv反反向向追追蹤蹤第第71頁頁1v3v2v4v5vsvtv6v)5

48、, 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v1v3v2v4v5vsvtv6v)5 , 5()2 , 3()4 , 4()4 , 5()4 , 4()4 , 5()3 , 3() 1 , 3()2 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v)2 ,(5v)2 ,(1v)2 ,(4v第第72頁頁1v3v2v4v5vsvtv6v)5 , 5()2 , 3()4 ,

49、 4()4 , 5()4 , 4()4 , 5()3 , 3() 1 , 3()2 , 3()2 , 2()2 , 2(),() 1 ,(sv當標到當標到 時，與時，與 ， 相鄰接的點相鄰接的點 ， ， 都不滿足標都不滿足標號條件，標號無法繼續(xù)，且沒有完成標號。此時最大流量即號條件，標號無法繼續(xù)，且沒有完成標號。此時最大流量即為所求。為所求。) 1 ,(svsv3v1v2v6vtv12354211ssswfff312456 ,; ,;stVv vVv v v v v v標號點集未標號集12361236( , )( , ),( ,),( ,)( , )11ssssV Vv vv vv vC V

50、Vccc割集割集容量重新開始標號，尋找可增廣鏈。重新開始標號，尋找可增廣鏈。第第73頁頁最小割的意義最小割的意義第第74頁頁tusu1234,u u u utusu解決問題解決問題vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)第第75頁頁vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(3)10(8),(vs,2)(-v2,2)(v1,1)(-v3,1)(v4,1)vsv1v3vtv2v48(8)7(6)9(5)9(9)5(5)6(0)2(0)5(3)10(9),(vs,1)(-v2,1)(v1,2)KKW=

51、5+9=14第第76頁頁下圖中，下圖中，A,B,C,D,E,FA,B,C,D,E,F分別表示陸地和島嶼，分別表示陸地和島嶼， 表示橋梁及其表示橋梁及其編號。若河兩岸分別為互為敵對的雙方部隊占領，問至少應切斷幾座橋梁編號。若河兩岸分別為互為敵對的雙方部隊占領，問至少應切斷幾座橋梁具體指出編號才能達到阻止對方部隊過河的目的。試用圖論方法進行分具體指出編號才能達到阻止對方部隊過河的目的。試用圖論方法進行分析。析。14ABCDEF8911101314127123456最大流問題應用舉例最大流問題應用舉例第第77頁頁在圖中任給可在圖中任給可行流，用標號行流，用標號法尋找網絡最法尋找網絡最大流！大流！弧容

52、量：兩點間的橋梁數(shù)?；∪萘浚簝牲c間的橋梁數(shù)。ABCDFE122211221122ABCDEF8911101314127123456轉化為求網絡最小割轉化為求網絡最小割第第78頁頁 設容量網絡設容量網絡G G有若干發(fā)點，若干個點，有若干發(fā)點，若干個點，可以添加兩個新點可以添加兩個新點vsvs，vt vt ，用容量為，用容量為 的有向邊分別連結的有向邊分別連結vs vs 與發(fā)點，收點與與發(fā)點，收點與vtvt，得到新的網絡得到新的網絡GG，G G 為只有一個發(fā)點，為只有一個發(fā)點，一個收點的網絡，求解一個收點的網絡，求解G G 的最大流問題的最大流問題即可得到即可得到G G的解。的解。多發(fā)點多收點網絡

53、的最大流問題多發(fā)點多收點網絡的最大流問題最大流問題應用舉例最大流問題應用舉例第第79頁頁 設有設有5位待業(yè)者，位待業(yè)者，5項工作，他們各自能勝任工作項工作，他們各自能勝任工作的情況如圖所示，要求設計一個就業(yè)方案，使盡的情況如圖所示，要求設計一個就業(yè)方案，使盡量多的人能就業(yè)。量多的人能就業(yè)。1x2x3x4x5x1y2y3y4y5y其中其中51,xx 表示工人。表示工人。51,yy 表示工作。表示工作。最大匹配問題最大匹配問題第第80頁頁1x2x3x4x5x1y2y3y4y5y圖中最大匹配問題，可以轉化為最大流問題求解。在圖中最大匹配問題，可以轉化為最大流問題求解。在圖中增加兩個新點圖中增加兩個新

54、點 分別作為發(fā)點，收點。并用分別作為發(fā)點，收點。并用有向邊把它們與原圖中頂點相連，令全部邊上的容量有向邊把它們與原圖中頂點相連，令全部邊上的容量均為均為1。當網絡流達到最大時，假如。當網絡流達到最大時，假如 上的流量為上的流量為1，就讓就讓 作作 工作，此即為最大匹配方案。工作，此即為最大匹配方案。svtv,svtv),(jiyxixjy第第81頁頁1x2x3x4x5x1y2y3y4y5ysvtv),() 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 ,(1x) 1 ,(1y第第82頁頁1x2x3x4x5x1

55、y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(4y) 1 , 1 () 1 , 1 () 1 ,(sv) 1 ,(2x)0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (第第83頁頁1x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 ()0 , 1 ()0 , 1 (第第84頁頁1x2x3x4

56、x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(5y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 ()0 , 1 ()0 , 1 () 1 ,(3x第第85頁頁1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (

57、)0 , 1 (第第86頁頁1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 ()0 , 1 () 1 , 1 () 1 ,(2y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(4x) 1 ,(5y) 1 ,(3x) 1 ,(4y)0 , 1 () 1 ,(2x) 1 ,(1y) 1 ,(4x)0 , 1 (第第87頁頁1x2x3x4x5x1y2y3y4y5ysvtv)0 , 1 () 1 , 1 () 1 , 1 ()

58、1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 ()0 , 1 (第第88頁頁1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1

59、() 1 ,(sv)0 , 1 () 1 ,(5x) 1 ,(4y)0 , 1 () 1 ,(3x) 1 ,(5y第第89頁頁1x2x3x4x5x1y2y3y4y5ysvtv),()0 , 1 () 1 , 1 () 1 ,(2y) 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 ()0 , 1 () 1 , 1 ()0 , 1 () 1 , 1 () 1 , 1 () 1 ,(sv)0 , 1 () 1 ,(2x) 1 ,(5x) 1 ,(4y)0 , 1 () 1 ,(3x) 1 ,(

60、5y,1x,2x,3x4x,2y,1y,4y5y第第90頁頁第八章第八章圖與網絡分析圖與網絡分析 最短路問題最短路問題 網絡最大流問題網絡最大流問題 最小費用最大流問題最小費用最大流問題 第第91頁頁第八章第八章圖與網絡分析圖與網絡分析 最短路問題最短路問題 網絡最大流問題網絡最大流問題 最小費用流問題最小費用流問題 第第92頁頁最小費用流問題最小費用流問題 最大流問題僅注意網絡流的流通能力，沒有考最大流問題僅注意網絡流的流通能力，沒有考 慮流通的費用。慮流通的費用。 實際上費用因素是很重要的。例如在交通運輸實際上費用因素是很重要的。例如在交通運輸 問題中，往往要求在完成運輸任務的前提下，問題