通信網理論基礎(蘇駟希)(北京郵電大學講義)--第二章 通信網的拓撲結構

1、第2章 通信網拓撲結構第二章 通信網拓撲結構 通信網的拓撲結構是很基本，也是很重要的問題。拓撲結構是通信網規(guī)劃和設計的第一層次問題。通信網的拓撲結構可以用圖論的模型來代表，主要的問題為最短徑和網絡流量問題。本章還介紹了線性規(guī)劃問題的基本概念和方法及網絡優(yōu)化結構模型。2.1圖論基礎圖論是應用數學的一個分支，本節(jié)介紹它的一些概念和結論。其基本內容可參見（1）和（2）。2.1.1圖的定義 例2.1 哥尼斯堡7橋問題;所謂一個圖，是指給了一個集合v，以及v中元素的序對集合e，v和e中的元素分別稱為圖的端點和邊。下面用集合論的術語給出圖的定義：設有集合v和e，v=v1，v2，vn， e=e1，e2， e

2、m ，且則v和e組成圖g，稱v為端集，e為邊集。下面給出圖的一些概念: 當eij=(vi，vj)，稱邊eij和端vi與vj關聯； 當virvj不等價于vjrvi 時，為有向圖； 當virvj等價于vjrvi(eij=eji)時，為無向圖；當v=(此時e必為空集) ，為空圖；自環(huán)，孤立點圖，重邊；簡單圖: 不含自環(huán)和重邊的圖稱為簡單圖. 當v，e均有限元 v，e時，稱為有限圖。我們一般討論的都是有限圖，考慮到實數集的不可數性，任何有限圖都可以表示為三維空間的幾何圖形，使每兩條邊互不相交，而且邊均可用直線來實現。但是若要在平面實現則不一定能辦到，稍后我們會給出平面圖的概念。 子圖:若a的端集與邊集

3、分別為g的端集與邊集的子集，則a為g的子圖。若ag，且ag，則a為g的真子圖。特別地，當a的端集和g的端集相等，稱a為g的支撐子圖。由端點子集誘導生成的子圖. 圖的運算:g1g2, g1g2, gc等 圖的幾種表現形式: 集合論定義, 幾何實現, 矩陣表示. 圖的同構; 權圖.2.1.2圖的連通性 對無向圖的端vi來說，與該端關聯的邊數定義為該端的度數：，記為：d(vi)。對有向圖：d+(vi)表示離開vi的邊數，d-(vi)表示進入vi的邊數對圖g=(v，e)，若|v|=n，|e|=m，則有如下基本性質： 1）若g是無向圖 2）若g是有向圖 下面定義圖的邊序列，鏈，道路，環(huán)和圈： 相鄰二邊有

4、公共端的邊的串序排列（有限） (v1，v2)， (v2，v3)， (v3，v4)， (vi，vj)，稱為邊序列。邊序列中，無重邊的，成為鏈(link)；若邊序列中沒有重復端，稱為道路(path)；若鏈的起點與終點重合，稱之為環(huán)(ring)； 若道路的起點與終點重合,稱之為圈(cycle)。 任何二端間至少存在一條徑的圖，為連通圖。否則，就是非連通圖。對非連通圖來說，它被分為幾個最大連通子圖，即幾個“部分”?！白畲筮B通圖”指的是在此圖上再加任意一個屬于原圖而不屬此圖的元素，則此圖成為非連通圖，如下例: g=abc=a+b+c對于圖的連通, 可以通過下面的方法給予準確的描述: 對于圖g中的任意兩個

5、端點u和v, 如果存在一條從u到v的鏈, 稱u和v有關系, 容易知道這是一個等價關系; 從而可以將圖g做一個等價分類, 每一個等價分類就是一個連通分支.連通分支只有一個的圖為連通圖.下面舉一些圖的例子:(1)完全圖kn：任何二端間有且只有一條邊（即直通路由），稱為完全圖， 其邊、端數之間存在固定關系: 下面是一個n=5的完全圖 (2)正則圖：所有端度數都相同的連通圖為正則圖 d(vi)=常數（i=1，2，n） 正則圖是連通性最均勻的圖 (3)尤拉圖(euler): 端度數均為偶數的連通圖為尤拉圖。 尤拉圖的性質: 尤拉圖存在一個含所有的邊且每邊僅含一次的環(huán).(4) 兩部圖 兩部圖的端點集合分為

6、兩個部分, 所有邊的端點分別在這兩個集合中. 完全兩部圖km,n(5)2.1.3樹:樹是圖論中一個很簡單，但是又很重要的概念，在圖論中運用是十分重要的。圖的定義有多種, 如下面的定義：1、 任何二端有徑且只有一條徑的圖稱為樹。2、 無圈的連通圖稱為樹.我們采用第2種關于圖的定義方式, 也就是:樹: 無圈的連通圖稱為樹.樹有以下性質: 1.樹是最小連通圖，樹中去一邊則成為非連通圖。 2.樹中一定無環(huán)。任何二端有徑的圖是連通圖，而只有一條徑就不能有環(huán)。 3.樹的邊數m和端數n滿足m=n-1 此式可以用數學歸納法證明。 4.除單點樹，至少有兩個度數為1的端(懸掛點) 樹上的邊稱為樹枝 (branch

7、)定理2.1：給定一個圖t，若p=|v|，q=|e|，則下面論斷等價：（1）t是樹；（2）t無圈，且q=p-1；（3）t連通，且q=p-1；證明：1）2），顯然；2）3），反證：若t不連通，它有k個連通分支（k大于等于2），每個都為樹，若第i個樹有個點，則，與q = p-1相矛盾；3）1），p=1時，顯然。設，t連通，且q=p-1，首先易證t有懸掛點，不然，與q = p-1相矛盾；然后對點數進行歸納即可；定理2.2：若t是樹，則：（1）t是連通圖，去掉任何一條邊，圖便分成兩個且僅僅兩個分圖；（2）t是無圈圖，但添加任何一條邊，圖便會包含一個且僅僅一個圈。同時，若無向圖滿足（1）和（2），則t是

8、樹。定理2.3：設t是樹，則任何兩點之間恰好有一條道路；反之，如圖t中任何兩點之間恰好有一條道路，則t為樹。 定理2.2和2.3刻畫了樹的兩個重要特征，事實上定理2.3也為圖提供了另一個等價定義。上述兩個定理的證明請讀者自行完成。支撐樹(spanning tree)： 考慮樹t是連通圖g的子圖，tg，且t包含g的所有端，稱t是g的支撐樹。 由定義可知，只有連通圖才有支撐樹；反之有支撐樹的圖必為連通圖。一般支撐樹不止一個， 連通圖至少有一個支撐樹。支撐樹上任二端間添加一條樹支以外的邊，則形成環(huán)(circuit)。支撐樹外任一邊稱支撐樹的連枝，連枝的邊集稱為連枝集或樹補(cotree)。不同支撐樹

9、對應不同連枝集。 對非連通圖來說，它可以分成k個最大連通子圖，即k個“部分”，每部分各有支撐樹。k個支撐樹的集合形成圖g的主林，其余的邊為林補。主林的邊數稱為圖的階，用r表示。主林的連枝數稱為空度，用m表示。有如下關系式： n=n1+n2+nk r=( n1-1)+ ( n2-1)+ + ( nk-1)=n-k m=m-n+k 例如： k=3； r=11-3=8； m=12-11+3=42.1.4割(cut) 割指的是某些子集(端集或邊集)。對連通圖，去掉此類子集，變?yōu)椴贿B通。對非連通圖，去掉此類子集，其部分數增加。 割分為割端集與割邊集。1、割端與端集 設v是圖g的一個端，去掉v和其關聯邊后

10、，g的部分數增加，則稱v是圖g的割端。去掉幾個端后，g的部分數增加，這些端的集合稱為割端集。有的連通圖無割端，這種圖稱為不可分圖。 對于連通圖, 在眾多的割端集中至少存在一個端數最少的割端集，稱為最小割端集。最小割端集，其任意真子集不為割集。 最小割端集的端數目，稱為圖的聯結度。聯結度越大，圖的連通性愈不易被破壞。2、割邊集與割集 連通圖g的邊子集s，去掉s使g為不連通，稱s為割邊集 在眾多的割集中邊數最少的割集，稱為最小割邊集。最小割邊集的任一真子集不為割邊集。最小割集的邊數，稱為結合度. 結合度同樣表示圖的連通程度，結合度越高，連通程度越好。3、基本割集與基本環(huán)（針對連通圖討論）1） 基本

11、割集設t為連通圖g的一個支撐樹，取支撐樹的一邊（枝）與某些連枝，定可構成一個極小邊割集，此割集稱為基本割集。即：基本割集是含支撐樹t之一個樹枝的割集?；靖罴衝-1個.下面一個圖來理解基本割集. 支撐樹t= 連枝：， 則基本割集：（，）， (，)，(，)， (，)2）基本環(huán)t為連通圖g的一個支撐樹，g-t的邊集為連枝集。取一連枝可與某些樹枝構成環(huán)。這種包含唯一連枝的環(huán)稱基本環(huán)。每個基本環(huán)只包含一個連枝-與連枝一一對應，其數目=連枝數，共m-n+1個。環(huán)和運算: 對于集合, 這個運算的意義為對稱差運算.通過環(huán)和運算, 由基本割集和基本環(huán)可以生成新的環(huán)和割集或它們的并集,事實上可以生成所有的環(huán)和

12、割集. 例2.2 通過基本環(huán)和基本割集理解基爾霍夫定律. 下面的圖理解基本環(huán). 連枝集 ， ：， ：， ：， ：，2.1.5 圖的平面性圖g若可以在一個平面上實現，除端點以外，任何兩條邊均無其他交點，則稱g是平面圖。當平面圖有一個平面實現后，它把全平面分成s個區(qū)域（含包含無窮遠點的開區(qū)域）。注意一個圖為平面圖等效于能夠在球面上有一個幾何實現.設連通平面圖有m邊，n端，則s=m-n+2，此為著名的euler公式。這個性質可以用數學歸納法證明或樹的性質證明。 m=4，n=4，s=2定理2.4：簡單連通圖為平面圖的必要條件是:m=3)上述結論可以推廣到有重邊和自環(huán)的情形. 證：形成區(qū)域至少3邊，區(qū)域

13、周線上的邊數至少3s(不考慮區(qū)域共邊)，實際每邊均在二區(qū)域周線上，最多有2m邊（周線上）?？紤]區(qū)域共邊，有2m3s，代入euler公式得m3n-6.此為平面圖的必要，非充分條件。例2.3 討論完全圖k5和完全兩部圖k3,3的平面性.定理2.5連通兩部圖為平面圖的必要條件是:m+4 =3)根據每個平面圖g=（v，e），可以生成一個對偶圖g。g的每個平面對應于g的每個頂點，g中相鄰的兩個面在g中有一些邊與g中的兩個面的每一條邊界的邊相交，如下圖所示。但是簡單平面圖的對偶圖可能不再是簡單圖。 定理2.6 圖g為平面圖當且僅當g不含k5和k3,3或它們的細分圖為子圖.2.1.6圖的矩陣表示 很多時候，

14、需要將圖表示在計算機中，這就有了圖的矩陣表示。下面主要介紹關聯陣和鄰接陣。1 關聯陣設圖g有n個端，m條邊，則全關聯陣 ；端vi對應于矩陣的第 i行(共n行)；邊ej對應于第j 列(共m列);其中: 下面是一個例子說明關聯矩陣, 例2.4 由a0可以看出:(1)第i行非零元個數等于端vi度數, 每列有兩個1;(2)若第i行均為0元素，則vi為孤立端， g為非連通圖;(3)若i行只有一個非o元，則vi為懸掛端;(4)如果將a0中每一個列中的任一個1改為-1, 則n行之和0向量，所以最多只有n-1行線性無關，a0秩最大為n-1。 將無向圖全關聯陣a0 中每一個列中的任一個1改為-1， 再去掉任一行

15、，得到關聯陣a，為n-1m階。a中的每一個非奇異方陣對應一個支撐樹。圖g的支撐樹數目可由以下方法得到：定理2.7(矩陣-樹定理)用at表示a的轉置, 無向圖g的主樹數目t(g) = det(aat)，注意上面的定理計算的主樹數目為標號樹的數目; 同時n-1階矩陣det(aat)可以直接寫出, 主對角線的元素為相應端點的度數, 其余位置為-1或0, 而這取決于相應的端點之間是否有邊.例2.5 t(kn) = , t(kn,m) = mn-1nm-1.t(kn) = 的計算如下： 繼續(xù)例2.4: 共有8種支撐樹如下 2.鄰接陣鄰接陣是表征圖的端與端關系的矩陣，其行和列都與端相對應。令g=（v，e）

16、是m端，n邊的有向圖，其鄰接陣 其中， 如： 對于無向圖 ，因此是鄰接陣為對稱陣。我們可以通過對c的一些計算，得到圖g的性質。如：計算c的冪次可得到關于轉接徑長的一些信息。若cij(2)=1則存在k，使cik ckj =1，即cik= ckj=1，i，j之間至少有徑，徑長為2；若cij(2)=a，則vivj間有a條徑長為2的徑，若cij(2)=0，則vivj間無徑長為2的徑；所以， cij(2)即為vivj間徑長為2即轉接一次的徑數。同理，若cij(3)=1， 則有vivkvsvj，徑長為3，即經過二次轉接。由此可得下面結論:鄰接陣冪之元素表示了二端間轉接次數不超過b-1的徑，但是經過轉接的端

17、可能重復。已知圖g的鄰接陣c, 需要解決圖g是否連通的問題? 當然通過計算鄰接陣c和c的冪可以解決這個問題,考慮下面的小算法, 它解決同樣的問題, 但效率很高.warshall 1962(1)置新矩陣 p:= c;(2)置 i = 1; (3)對所有的j, 如果p(j,i)=1, 則對k=1,2,n p(j,k):= p(j,k) p(i,k);(4) i = i+1;(5)如n i轉向步驟(3), 否則停止.本節(jié)介紹了圖論的簡要知識，1和2介紹了很好的基礎知識。4介紹了網絡優(yōu)化算法的詳盡的和較新的進展。本節(jié)內容同時也借鑒3的一些結果。某些圖論知識在以后應用是會在介紹。2.2 最短徑問題 上節(jié)

18、中介紹的圖只考慮了圖頂點之間的關聯性，本節(jié)將要對圖的邊和端賦予權值，討論有權圖。權值在各種各樣實際問題中有不同的實際意義，如費用，幾何距離，容量等等。本節(jié)將介紹一些算法，大部分算法可借助計算機實現。2.2.1 最短支撐樹給定連通圖g=(v，e)，w(e)是定義在e上的非負函數，稱w(e)為e的權。t=(v，)為g的一個支撐樹。定義樹t的權為。最短支撐樹問題就是求支撐樹，使w()最小。下面介紹求最短支撐樹的方法。1) 無限制條件的情況 prim在1957年提出一個方法，簡稱p算法。 圖g有n端，端間“距離”dij(i，j=1，2，3，.n)已給定(若無邊則dij=)，找一個支撐樹，使其n-1個邊

19、（樹枝）的權和最小，步驟如下： p0:任取一端v1，子圖g1=v1，在g1到g-g1中取最小的dij 得子圖g2= v1， v2p1:求g3 得子圖g3= v1，v2，v3 pr-2:從gr-1求gr 得子圖gr= v1，v2，vr pr-1:重復pr-2，直至得到gn為止例2.5: g1=v1g2=v1，v3g3=v1，v3，v6g4=v1，v3，v6，v7g5=v1，v3，v6，v7，v2g6=v1，v3，v6，v7，v2，v5g7=v1，v3，v6，v7，v2，v5，v4則w(t)=15 可以看出， prim算法第k步運算，是以gk作為整體尋找至g-gk的最短邊，每次并入gk的邊總是保持

20、余下m-k+1個中最短的，因此算法終止時，所得的支撐樹為最短者(可用數學歸納法證明)。 從算法始至終止，共進行n-1步，每步從k個端與n-k個端比較，須經k(n-k)-1次，可得總計算量 約為n3量級。當n很大時，可借助計算機實現。另一個算法由kruskal在1956年提出:設g(k)是g的無圈支撐子圖,開始g(0)=(v,f)。若g(k)是連通的,則它是最小支撐樹；若g(k)不連通,取e(k)為這樣的一邊,它的兩個端點分屬g(k)的兩個不同連通分圖,并且權最小。令g(k+1)= g(k)+ e(k),重復上述過程。上面算法的實現過程需要排序算法；rosenstiehl和管梅谷提出了另一個算法

21、：設g(k)是g的連通支撐子圖，開始g(0)=g，若g(k)中不含圈，則它是最小支撐樹；若g(k)中包含圈，設m是g(k)中的一個圈，取m上的一條權最大的邊e(k)，令g(k+1)= g(k)-e(k)，重復上述過程。上面算法的實現過程需要解決如小問題：對于一個無向圖g, 如何尋找其中的圈?可以通過搜索圖中度為1的頂點而逐步簡化.上面算法的實施過程,都是一種貪心法原理的應用; 從局部最優(yōu)的結果中尋找全局最優(yōu)的結果.問題如果復雜, 這種方法一般只能找到準最優(yōu)解.2) 有限制情況 在許多情況下，不但要求最短支撐樹，還要求一些額外條件。有兩種解決此類問題的方法窮舉法和調整法。窮舉法就是先把圖中的支撐

22、樹窮舉出來，按條件逐個篩選，最后選出最短支撐樹。這種方法較直觀，但很煩瑣。下面討論調整法。以esau-william算法為例(解決一種特定的問題):問題:圖g有n個站,其中已知v1是主機，已知各邊間距離dij，以及各個端站的業(yè)務量fi（i，j=1，2，n），要求任端至v1的徑邊數k(即限轉接次數 d(i)+cij then begind(j):= d(i)+ cijpred(j):=i；if jlist, then 將j并入list;end; end; end; 上面的算法中沒有指明list的結構, 如果將list組織為一個隊列, 算法效率會更高, 計算復雜度為o(nm), 大約為目前最快的算

23、法, 上面兩個算法的解決思路的比較是很有意義的。值得注意的是，如果附加一些條件，那么問題便很復雜了。如果邊有兩個權,相應的算法就復雜的多, 并且很可能無多項式算法.2、所有端間最短徑算法 floyd算法解決了圖g中任意端間的最短距離和路由，并且也采用label-correcting 的方法。給定圖g及其邊 (i, j)的權dij(i，j=1，2，3，n);f0：初始化距離矩陣w(0)和路由矩陣r(0) ; w(0)= wij(0) nn其元素： 同時 r(0)= rij(0) nn f1：已求得w(k-1) 和r(k-1)，求w(k) 和r(k) ; wij(k)=minwij(k-1)，wi

24、k(k-1)+ wkj(k-1) f2：若kn，重復；k=n終止。上面的路由方法為前向路由，容易更改算法使它的路由為回溯路由; 算法要執(zhí)行n次迭代, 第k次迭代的目的為經過端k轉接是否可以使各端之間距離縮短. 從本質上講, floyd算法的迭代過程就是保證滿足下面的定理成立.定理2.8 對于圖g, 如果w(i, j)表示端i和j之間的可實現的距離, 那么w(i, j)表示端i和j之間的最短距離當且僅當對于任意i, k, j有: w(i, j) w(i, k) +w(k, j)floyd算法計算量 : wij(k)=minwij(k-1)，wik(k-1)+ wkj(k-1)中，每定一k值，求w

25、ij經1次加，1次比較，求一次迭代為n2次加，n2次比較，共n個迭代，所以其運算量為n3級; 顯然比重復使用dijkstra算法效率高，同時存儲效率也要高。對于floyd算法, 同樣提出若干問題如下: 1 如果端點有權如何處理? 2 如果邊的權可正可負, 算法是否仍然有效? 3 算法是否對有向圖也適用？例2.7 給定一個無向圖g, 求任意兩端之間最少轉接次數和路由.例2.8圖有六個端，端點之間的有向距離矩陣如下：1. 用d算法求v1到所有其他端的最短徑長及其路徑。2. 用f算法求最短徑矩陣和路由矩陣，并找到v2至v4和v1至v5的最短徑長及路由。3. 求圖的中心和中點。解：1. d算法v1v2

26、v3v4v5v6指定最短徑長,路由0v1w10, 19 1 3v3w131, 193 2 v5w152, 38 3 7v4w143, 18 7 v3w167, 5 8 v2w128, 52. f算法最短路徑矩陣及最短路由陣為w5，r5有向距離為4有向距離為23. 中心為v3或v5中點為v2 在實際問題中，除了求最短徑外，如當主路由（最短徑）上業(yè)務量溢出或故障時，需尋求次短徑或可用徑。次短徑指備用徑，可用徑指一批滿足某種限制條件的徑（如限徑長，限轉接次數.）。但這些問題一般沒有多項式算法, 可以根據實際情況采用某種貪心策略獲得近似解.3、網的中心與中點如網絡用圖g=(v, e)表示, 根據flo

27、yd算法的計算結果可以定義網絡的中心和中點.中心:對每個端點i, 先求 此值最小的端稱為網的中心，即滿足下式的端i*： =網的中心宜做維修中心和服務中心。中點:將“平均最短徑長”最小的端，定義為中點，先計算 si = , 然后求出si的最小值, 相應的端點為中點. 網的中點可用做全網的交換中心。2.3網絡流量問題 網絡的目的是把一定的業(yè)務流從源端送到宿端。流量分配的優(yōu)劣將直接關系到網絡的使用效率和相應的經濟效益。網絡的流量分配受限于網絡的拓撲結構，邊和端的容量以及路由規(guī)劃。本節(jié)及下節(jié)中關于流量的內容均在有向圖上考慮，并且均是單商品流問題，即網絡中需要輸出的只有一種商品或業(yè)務。通信網絡的服務對象

28、有隨機性的特點, 關于通信業(yè)務隨機性特點將在下一章中考慮, 本節(jié)中假設網絡源和宿的流量為常量.2.3.1基本概念 給定一個有向圖g=（v，e），c(e)是定義在e上一個非負函數，稱為容量；對邊eij，邊容量為cij ，表示每條邊能通過的最大流量。設f= fij 是上述網絡的一個流，若能滿足下述二限制條件，稱為可行流。 a)非負有界性：0fijcij； b)連續(xù)性: 對端vi有： v(f) = f為源宿間流fij的總流量.式中 （vi）=vj: ( vi， vj)e 流出vi的邊的末端集合; (vi)=vj: ( vj， vi)e 流入vi的邊的始端集合; 有n個連續(xù)性條件，共有2m+n個限制條

29、件，滿足上述二限制條件的流稱為可行流。 需要解決的問題分為兩類: 1 最大流問題 在確定流的源和宿的情況下, 求一個可行流f, 使v(f) = f為最大; 2 最小費用流問題 如果邊(i,j)的單位流費用為di,j , 流f的費用為: 所謂最小費用流問題: 在確定流的源和宿的情況下, 求一個可行流f, 使為最小. 下面介紹割量和可增流路的概念. 設x是v的真子集，且vsx，vtxc，（x，xc）表示起點和終點分別在x和xc的邊集合，這個集合當然為一個割集,割集的正方向為從vs到vt。割量定義為這個割集中邊容量的和: 對可行流fij: f(x，xc)表示前向邊的流量（和）fij, 其中vix，v

30、jxc f(xc，x)表示反向邊的流量 (和) fji, 其中vix，vjxc則源為vs宿為vt的任意流f有:(1) v(f)=f(x,xc)-f(xc,x), 其中vsx，vtxc證明： 對任vix : 對所有vix,求和上式： 源端 s: fs1+fs2+fs3 中轉端 1: f14 -(fs1+f21)中轉端 2: f21+f23 -(fs2)中轉端 3: f3t -(fs3+f23+f53)-= f14+f3t-f53= f(x,xc)-f(xc,x)=f(2) fc(x,xc)由（1）及f(x, xc)非負，可得：下面討論可增流路的概念。 從端s到端t的一個路，有一個自然的正方向，然

31、后將路上的邊分為兩類：前向邊集合和反向邊集合。對于某條流，若在某條路中，前向邊均不飽和（fijcij），反向邊均有非0流量（fij0），稱這條路為可增流路徑（或增廣鏈）。在可增流路上增流不影響連續(xù)性條件，也不改變其它邊上的流量，同時可以使從源端到宿端的流量增大。 若流 fi,j 已達最大流，f則從源至宿端的每條路都不可能是可增流路，即每條路至少含一個飽和的前向邊或流量為0的反向邊。2.3.2 最大流問題 所謂最大流問題，在確定流的源端和宿端的情況下, 求一個可行流f, 使v(f) 為最大。對于一個網絡，求最大流的方法采用可增流路的方法，下面的定理2.9為這種方法提供了保證. 如果網絡為圖g =

32、 (v, e),源端為vs, 宿端為vt.定理2.9 (最大流-最小割定理)可行流f* = 為最大流當且僅當g中不存在從vs 到vt的可增流路.證明: 必要性: 設f*為最大流,如果g中存在關于f*的從vs 到vt的可增流路.令 0 fi,j ， 則標vj 為: (+，i，j)其中j =min(ci,j-fi,j ，i ) i 為vi 已標值。若（vj ,vi ）e，且 fj,i 0， 則標vj 為: (-，i，j)， 其中j =min（i ，fj,i ）其它端vj 不標。所有能加標的鄰端vj 已標，則稱vi已查。倘若所有端已查且宿端未標，則算法終止。m3：若宿端vi 已標，則沿該可增流路增流

33、。m4: 返回m1。 上面的算法是針對有向圖且端無限制的情況。若是有無向邊，端容量及多源多宿的情況，可以進行一些變換，化為上述標準情形。 若端i和端j之間為無向邊，容量為ci,j，那么將它們化為一對單向邊(i，j)和(j，i)，并且它們的容量均為ci,j。 如果端i有轉接容量限制ci，那么將vi 化為一對頂點，原終結于vi的邊全部終結于，原起始于vi的邊均起始于，且從至有一條邊容量為ci。 對多源多宿的情況，設原有源為，原有宿為，要求從源集到宿集的最大流量，可以虛擬一個新的源和新的宿，源到的各邊容量均為無限大，到宿的各邊容量也為無限大，這樣多源多宿的問題就化為從到的最大流問題。見下圖：仔細考慮

34、一下會發(fā)現，前面介紹的算法在任何網絡中是否一定會收斂，也就是說會不會不斷有增流路，但卻不收斂于最大流呢？如果邊的容量均為有理數，是不會出現這種情況，也就是說一定會收斂。但若邊的容量為無理數，就不一定收斂。對于計算量的問題, ford和fulkerson曾給出下面的例子。如圖所示，一個四個節(jié)點的網絡，求至的最大流量。假設按前述算法，并且按如下順序從f=0開始增流：例2.8；;顯然，這樣需要2n+1步增流才能找到的最大流，流量為2n+1。這個例子說明前述算法雖然能夠達到最大流，但是由于沒有指明增流方向，導致有可能象這個例子一樣，效率很低，這個例的計算工作量與邊容量有關。1972年，edmonds和karp 修改了上述算法, 在m2步驟時采用fifo原則(在選哪個端查時), 從而解決了這個問題；新算法一方面收斂, 同時也為多項式算法. 后來，人們提出了許多改進的算法，如dini