第4章圖與網(wǎng)絡(luò)

1、精品文檔第4章圖與網(wǎng)絡(luò)一、圖與網(wǎng)絡(luò)的基本概念1 .概念的引入例1我國北京、上海等10個城市間的鐵路交通示意圖如圖所示，它反映了這10個城市的鐵路分布情況。圖中，用點代表城市，點與點之間的連線代表兩個城市之間的鐵路線。北市人評2 .基本概念(1)圖圖：圖是由一些點以及點之間的連線所組成的。其中，這些點又稱為頂點。邊(弧)：兩頂點之間不帶箭頭的連線稱為邊；帶箭頭的連線稱為弧。邊(或弧)上相應(yīng)的數(shù)值稱為邊(或弧)的權(quán)。無向圖：由點和邊構(gòu)成的圖稱為無向圖(簡稱圖)，記作G=(V,E),其中V、E分別是G的頂點集合和邊的集合。連接兩頂點vi,vj£V的邊e記為e=(vi,叩或e=(vj,vi)

2、o有向圖：由點和弧構(gòu)成的圖稱為有向圖，記作D=(V,A),其中V、A分別是D的頂點集合和弧的集合。從起始點vWV指向終點VjCV的弧a記為a=(vi,兇了(環(huán)，vi)o多重邊和環(huán)：兩個頂點間具有兩條以上的邊稱為多重邊；若邊的兩端為同一頂點則稱其為環(huán)，如圖1中的“邊7”。多重圖和簡單圖：含多重邊的圖稱為多重圖；無環(huán)且無多重邊的圖稱為簡單圖。6W圖1環(huán)圖2支撐子圖支撐子圖：如果圖G=(V,E),G'=(V',E'HV'V,EE,則稱G為G的子圖，如圖2(b)所示；若在同一圖中，V'=V,E'JE,則稱G'為G的支撐子圖，如圖2(c)所示。(2

3、)鏈鏈：在圖G=(V,E)中，由一些頂點和邊所組成的交錯序列v1，e1,v2,e2,，vi,ek,vk就稱為一條聯(lián)結(jié)頂點VI、Vk的鏈。開鏈和閉合鏈：起點和終點不是同一頂點的鏈，則稱其為開鏈，否則就稱其為閉合鏈。單純鏈和基本鏈：一條沒有重復(fù)邊的鏈稱為單純鏈，如圖3中的邊序列5,6,2,7,8;一個沒有重復(fù)頂點的鏈稱為基本鏈，如圖3中的邊序列1,2,3。路和回路：一個開的基本鏈稱為路，如圖中的邊序列1,6,7,3;一個閉合的基本鏈稱為回路，如圖中的邊序列1,6,5。連通圖：如果在一個圖中任意兩個不同的頂點之間至少有一條路，則該圖就稱為連通圖。圖3鏈圖4樹（3）樹樹：如果連通圖G的子圖Gi也是連通

4、的，并包含了G的所有頂點，且沒有回路，則稱Gi為G的一個生成樹（簡稱樹），記為T,如圖4中的（b）、（c）、（d）即為圖（a）的樹：=i,3,5,T2=2,3,5,T3=2,4,5。組成樹的邊就稱為樹枝。樹的性質(zhì)如下： 樹的任意兩個頂點之間只有一條鏈； 在樹中不相鄰的兩個頂點間添上一條邊，則恰好得到一個回路； 在樹中去掉任何一條邊，則成為不連通圖；含有n個頂點的樹，則有n-1條邊。例2已知有五個城市，試問如何在它們之間架設(shè)電話線，使任何兩個城市都可以互相通話（允許通過其它城市），且電話線的根數(shù)最少？解用五個點V1,V2,V3,V4,V5代表五個城市，如果某兩個城市之間架設(shè)電話線，則在相應(yīng)的兩點

5、之間連一條邊，則該電話線網(wǎng)就可以用一個圖來表示。為了使任何兩個城市都可以互相通話，則此圖必須是連通圖；另外，若此圖中有回路，從回路上任意去掉一條邊，使余下的圖仍是連通的，且可以省去一根電話線。因此，滿足要求的電話線網(wǎng)所對應(yīng)的圖必定是一個樹，如圖5所示。（這堂由于連通圖對應(yīng)的樹有多個，故這里只給出了其中一個樹）割集：將連通圖分割為兩個子圖所需割斷的最少邊集就稱為割集，如圖6中的邊集8,9、1,3,6、4,5,6等。注意：割集的定義表明，當(dāng)去掉構(gòu)成割集的一組邊時，則原連通圖被分割成相互分離的兩部分；而只要少去掉一條邊，則被分開的兩部分仍是連通的。例如，邊集7,8,9就不是割集因為移去這個邊集可以使

6、圖分離為兩部分，但若再連上邊7,已分離的圖仍不能連通，不符合割集的定義。最小割集：對于一個圖有若干個割集，其中邊數(shù)最少的割集，則稱其為最小割集(簡稱最小割)，如圖6中的邊集8,9。二、最短路問題1 .問題的提出例3(管道鋪設(shè)問題)從油田鋪設(shè)管道，把原油運輸?shù)皆图庸S。要求管道必須沿圖7所給定的路線鋪設(shè)，圖中vi點為油田，V9點為原油加工廠，弧權(quán)為相應(yīng)路段的管道長度，試問如何鋪設(shè)管道才能使管道總長最短？圖7油田管道路線圖圖8油田管道最短路線圖解顯然，可能的油田管道鋪設(shè)方案有多種，而不同方案的管道總長不同，則現(xiàn)在的問題是要尋求一條從Vi到V9的路線，使油田的管道總長最短。若Vi-Vi-V9是從V

7、i至IJV9的最短路，則V1-Vi是從V1到Vi的最短路，根據(jù)這一原理來求出該最短路問題。(1)與Vi直接相連的點為V2、V3,但ll3=2<li2=4,所以ViV3為最短路，連接ViV3兩點；(2)與ViV3直接相連的點為V2、V、V6,則li2=4,li5=6,116=6,minli2,li5,li6=4,連接ViV2；(3)與Viv2V3直接相連的點為V4、V5、V6,則l14=10,ll5=6,ll6=6,minll4,l15,ll6=115,116=6,連接V3V5、v3V6；(4)與V1V2V3V5V6直接相連的點為V4、V7、Vg,則%=10,1=10,屋=8,min114

8、,117,118=8,連接V5V8；(5)與V1V2V3V5V6V8直接相連的點為V4、V7、V9,貝U%=10,117=10,119=12,min114,117,118=114,117=10,連接V2V4、V5V7；(6)與V1V2V3V4V5V6V7V8直接相連的點為V9,則119=12,min119=12,連接V7V9、V8V9；(7)至此已將所有的點都相連，如圖8所示。由圖可見，V1V3V5V7V9或V1V3V5V8V9為所求的最短路線，相應(yīng)的油田管道總長均為12。2 .兩固定頂點間的的最短路問題一一標(biāo)號算法(又稱狄克斯屈拉算法)利用狄克斯屈拉(Dijkstra)算法，可以求出從起點V

9、1到終點4(即兩個固定頂點間)的最短路，但該算法只適用于各弧權(quán)1ij均為非負(fù)的情況(即1ij>0),一般在實際的管理工作中都能滿足這一要求。注意：標(biāo)號算法不適用于弧權(quán)為負(fù)的情況(但這種情況可以用福特算法來求解，略)標(biāo)號算法的基本思路是：從起點必開始，對每個頂點給定一個標(biāo)號，標(biāo)號分臨時標(biāo)號T和固定標(biāo)號P兩類。頂點Vi的臨時標(biāo)號記為T(i),它表示起點V1到頂點Vi最短距離的上界；頂點M的固定標(biāo)號記為P(i),它表示起點V1到頂點Vi的實際最短距離。已得到P類標(biāo)號的頂點不再改變其標(biāo)號，而沒有標(biāo)上P類標(biāo)號的頂點則必須標(biāo)上T類標(biāo)號，算法的每一步都要把某一頂點的T類標(biāo)號改為P類標(biāo)號，直到終點Vn獲

10、彳導(dǎo)P類標(biāo)號時，就可求得從起點V1到終點Vn的最短路線。標(biāo)號算法的計算步驟如下：(1)給起點V1標(biāo)上固定標(biāo)號P(1)=0,表示V1到V1的最短距離為零；其余頂點Vj(j=2,n)標(biāo)上臨日標(biāo)號T(j)=8,表示V1到Vj暫時無路；(2)設(shè)頂點M是剛得到P類標(biāo)號的頂點，把與頂點Vi有弧直接相連且又屬于T類標(biāo)號的各頂點Vj的標(biāo)號，改為以下新的T類標(biāo)號，即T(j)=minT(j),P(i)+1ij(3)在T類標(biāo)號中選出標(biāo)號最小的頂點j0,并將其臨時標(biāo)號T(j0)改為固定標(biāo)號P(jO);(4)若終點Vn獲彳導(dǎo)P類標(biāo)號，則算法終止，最短路已經(jīng)找到，否則返回(1)。確定由起點V1到終點Vn最短路徑的方法有以

11、下兩種：其一，在算法進(jìn)行時作出標(biāo)記，以表明每個固定標(biāo)號的頂點是由哪個頂點得到標(biāo)號的，然后從終點反向追蹤到起點，這樣就可找出最短路徑；其二，從終點反向逆算，看哪個頂點的固定標(biāo)號與終點固定標(biāo)號的差值恰好等于與終點直接相連的相應(yīng)弧權(quán)，如頂點j,則對頂點j之前的頂點再做類似的逐點推算，直到起點為止，這樣也可找到最短路徑；例4(郵遞員投遞路線問題)已知某郵遞員沿著圖9所示的街道網(wǎng)絡(luò)投遞郵件，試求從頂點1到頂點6的最短距離及其路線。圖9街道網(wǎng)絡(luò)路線圖解用最短路標(biāo)號算法求解時，首先給頂點1標(biāo)上P類標(biāo)號，即P(1)=0,其余頂點標(biāo)上T類標(biāo)號，且T(j)=00(j=2,，6)。第一步與頂點1直接相連且又為臨日標(biāo)

12、號的頂點是2和3,則將這兩個頂點的T類標(biāo)號改為T(2)=minT(2),P(1)+I12=min-,0+4=4T(3)=minT(3),P(1)+I13=min8,0+3=3在所有的T類標(biāo)號中，T(3)=3最小，于是令P=3,即頂點3獲得固定標(biāo)號；第二步0與頂點3直接相連且又為臨日標(biāo)號的頂點是2和5,則將它們的T類標(biāo)號改為T(2)=minT(2),P(3)+I32=min4,3+2=4T(5)=minT(5),P+135=min8,3+2=5CD在所有的T類標(biāo)號中，T(2)=4最小，于是令P(2)=4;第三步0與頂點2直接相連且又為臨日標(biāo)號的頂點是4和5,則將它們的T類標(biāo)號改為T(4)=min

13、T(4),P(2)+I24=min8,4+3=7T(5)=minT(5),P(2)+I25=min5,4+1=5在所有的T類標(biāo)號中，T(5)=5最小，于是令P(5)=5;第四步。與頂點5直接相連且又為臨日標(biāo)號的頂點是4和6,則將它們的T類標(biāo)號改為T(4)=minT(4),P+154=min7,5+2=7T(6)=minT(6),P+156=min8,5+4=9CD在所有的T類標(biāo)號中，T(4)=7最小，于是令P(4)=7;第五步0與頂點4直接相連且又為臨時標(biāo)號的頂點只有6,則將它的T類標(biāo)號改為T(6)=minT(6),P(4)+146=min9,7+3=9C2顯然應(yīng)令P(6)=9,即終點(頂點6

14、)獲得固定標(biāo)號，算法到此結(jié)束，則頂點1到頂點6的最短距離為9。要找出從頂點1到頂點6最短路的各頂點順序，可從頂點6反向逆算。與頂點6直接相連的是頂點4和頂點5,而頂點6與頂點4或頂點5固定標(biāo)號之差為2和4,與頂點6直接相連的弧中只有弧(5,6)的弧權(quán)為4,因此頂點6之前的是頂點5。類似地可以推算出，頂點5之前的是頂點3,頂點3之前的是頂點1,即有一條最短路線為1一3一5一6;或者得出，頂點5之前的是頂點2,頂點2之前的是頂點1,即另一條最短路線為1一2一5一6。這兩條路線的最短距離均為9。注意:標(biāo)號算法可用于任何弧(邊)權(quán)為正的有向圖(無向圖)。3.任意兩頂點間的最短路問題一一福勞德算法設(shè)網(wǎng)絡(luò)

15、圖的頂點編號為1,2,，N,令Dm矩陣的元素dijm為頂點Vi到Vj的一條最短路長度，該路徑的中間頂點只有m個。若不存在這種最短路，則dijm=8。由dijm的含義可知，dij°為直接相連(即相鄰)的兩頂點間的最短長度，且dii°=0；dijN為所要確定的任意兩頂點aVj之間的最短距離。福勞德算法的求解步驟為：(1)確定D0矩陣，其元素dij0為任意兩相鄰頂點w、Vj間的最短路長度，若頂點m、Vj間不存在這種最短路，則dij°=°°；若i=j,則dii0=0-(2)對m=1,2,，N,依次按下式由Dm口矩陣確定Dm矩陣：dijm=mindimm

16、+dmjm,dijm若選出的最小元素是由dimm-+dmjmJL決定的，則記下m;若二者相等或取決于dijm-,則不記錄；(3)如此類推，直到計算出DN矩陣為止。例5(防火安全問題)某工地有四個重點防火點，道路和防火點位置如圖10所示，試問安全員該如何確定任一防火點到其他防火點的最短路徑？圖10防火點位置及其道路示意圖精品文檔解應(yīng)用福勞德算法：第一步，寫出D0矩陣123410121022078D=3650241七40_第二步，根據(jù)D0矩陣列表求出D1矩陣和相應(yīng)的路徑dij1=mindi10+d1j0,dij0中間點dij1=mindi10+d1j0,dij0中間點du=du=0d311=min

17、6+0,6=61一-d12=min0+1,1=1d321=min6+1,5=51d13=min0+2,2=21d33=min6+2,0=0d"=min0+1,1=1d341=min6+1,2=21一f-d21=min2+0,2=21d41=min1+0,1=1d221=min2+1,0=0d421=min1+1,0°=21d231=min2+2,7=411一-d43=min1+2,4=31d241=min2+1,0°=311d44=min1+1,0=0一。121043502230其路徑矩陣為12341一121134一11一其中，D1中的矩陣元素表示中間點為1（即m

18、=1）時各點間的最短距離，相應(yīng)的路徑表示經(jīng)過中間點1的最短路徑。例如，d421=2表示路徑4一1一2對應(yīng)的距離為2。第三步，由D1矩陣按上述方法求出D2矩陣和相應(yīng)的路徑此時中間點為兩個，即m=2,其計算公式為dij2=mindi21+d2j1,dij1dij2=mindi21+d2j1,dij1中間點dij2=mindi21+d2j1,dij1中間點du2=min1+2,0=0.2一一一一d31=min5+2,6=62.d12=min1+0,1=1,2,“-d32=min5+0,5=52d13=min1+4,2=22d33=min5+4,0=02d14=min1+3,1=1.2一一一一d34=

19、min5+3,2=22一一d21=min0+2,2=22一d41=min2+2,1=1.2一一一一d22=min0+0,0=02一一d42=min2+0,2=212d23=min0+4,4=41,2一一一d43=min2+4,3=31d242=min0+3,3=31,2,一一一d44=min2+3,0=0012122043,D2=65021230_由于沒有選擇中間點，所以對應(yīng)的路徑與上一步相同。注意，D2中的矩陣元素表示經(jīng)過兩個中間點時各點間的最短距離，而不是經(jīng)過第二個頂點時各點間的最短距離，因為公式dij2=mindi21+d2j1,dij1中di21+d2j1或dij1為已經(jīng)經(jīng)過一個中間點

20、的值。第四步，由D2矩陣按上述方法求出D3矩陣和相應(yīng)的路徑此時中間點為三個，即m=3,其計算公式為dij3=mindi32+d3j2,dij2dij3=mindi32+d3j2,dij2中間點dij3=mindi32+d3j2,dij2中間點3du=min2+6,0=0.3一一一一d31=min0+6,6=6_3一一d12=min2+5,1=1d323=min0+5,5=53d13=min2+0,2=2.3一一一一d33=min0+0,0=03d14=min2+2,1=1d343=min0+2,2=2_3一一一一d21=min4+6,2=23d41=min3+6,1=13d22=:min4+5

21、,0=03d42=min3+5,2=21d23=:min4+0,4=41d433=min3+0,3=31d243=:min4+2,3=31d44=min3+2,0=0-012120436502J230D 4矩陣和相應(yīng)的路徑,D3對應(yīng)的路徑仍同上。第四步，由D3矩陣按上述方法求出此時中間點為四個，即m=4,其計算公式為333.dij=mindi4+d4j,dij其計算結(jié)果為-0231121043402230dij4=mindi43+d4j3,dij3中間點dij4=mindi43+d4j3,dij3中間點4du=min1+1,0=04一d31=min2+1,6=34d24=min1+2,1=1d

22、324=min2+2,5=444一d13=min1+3,2=24一d33=min2+3,0=04d14=min1+0,1=1d344=min2+0,2=2d214=min3+1,2=2d414=min0+1,1=1d224=min3+2,0=04一一d42=min0+2,2=21d234=min3+3,4=414.d43=min0+3,3=31d244=min3+0,3=314d44=min0+0,0=0對應(yīng)的路徑矩陣為12341 一12 113 444 -11一由D4矩陣可求出網(wǎng)絡(luò)圖中任意兩點間的最短距離，并確定所對應(yīng)的路徑。例如，點3到點2之間的的最短距離是4;且由路徑矩陣可知，先由第3行

23、第2列對應(yīng)的4確定由3-4,再查該矩陣的第4行第2列對應(yīng)的1確定由4-1,最后查該矩陣的第1行第2列對應(yīng)的0確定12可直接到達(dá)，因此確定點3到點2之間的的最短路徑為3一4一1一2。三、最大流問題1 .基本假設(shè)和符號含義(1)將出發(fā)點稱為源點S;終點稱為匯點T;其余點稱為中間點i;(2)假設(shè)源點有無限多的物資、能量、信息及人力等要運出，而匯點則有無限大的倉庫來存儲這些物資、能量、信息及人力等；(3)假設(shè)中間點不存儲任何物資、能量、信息等，只起傳遞作用；(4)由i點到j(luò)點的最大傳遞數(shù)量規(guī)定為線路的容量，用C(i,j)表示；(5)規(guī)定X(i,j)為由i點到j(luò)點的實際通過流量。注意:實際支路通過流量X

24、(i,j)等于支路容量C(i,j),就稱為支路飽和。2 .基本定理及其有關(guān)概念(1)流量守恒定律根據(jù)上述假設(shè)，仿照電路中的基爾霍夫定律，可以得到流量守恒定律。如果匯X(i,j),jCV(i)表示流出i點的總流量，其中V(i)為可直接到達(dá)j點的點集合；而匯X(j,i),jCR(i)表示流入i點的總流量，其中R(i)為可直接到達(dá)i點的點集合，由于基爾霍夫定律中流入節(jié)點的電流之和與流出節(jié)點的電流之和相等的原理，與上述假設(shè)中的中間點只起傳遞作用相似，因此有f,i二SXX(i,j)-XX(j,i)=(0,i¥S,i#Tj田(i)j市(i)上.十一f,i=T上式就稱為流量守恒方程，式中f表示流量

25、。由假設(shè)(4)可知，0WX(i,j)WC(i,j),即實際流量為非負(fù)且不大于線路的容量，因此，網(wǎng)絡(luò)最大流問題的數(shù)學(xué)規(guī)劃模型為目標(biāo)函數(shù)maxf=X(S,j)jV(i)'7,i=SXX(i,j)-ZX(j,i)=J0,i=S,i#TSt.3jaj擊-f,i=TJ0<X(i,j)<C(i,j)該問題單純形法可以得到最優(yōu)解，故最大流問題本質(zhì)上是線性規(guī)劃問題，但是當(dāng)網(wǎng)絡(luò)較大時，約束方程的數(shù)量和變量的個數(shù)較多，線性規(guī)劃模型很大，不便于求解，則利用圖的特性可是問題的求解變得容易。(2)割集和割集容量設(shè)G是一個連通圖，則滿足下列條件的邊的集合就稱為割集：把這些邊全部從圖G中去掉，則圖G成為

26、不連通的兩部分；,把該邊集合的任何子集從圖G中去掉，則圖G仍是連通的。割集中各支路容量的和稱為割集容量。(3)最大流一一最小割定理定理：網(wǎng)絡(luò)中從源點S到匯點T的最大流量就等于把S和T分開的最小割集容量。3.標(biāo)記法由最大流一一最小割定理可知，在求解網(wǎng)絡(luò)最大流問題時，可以利用窮舉法列出所有將源點S和匯點T分開的割集，并計算其相應(yīng)的割集容量，從而確定其最小割集容量，即最大流量。這種方法雖然準(zhǔn)確，但過于繁瑣，因此采用標(biāo)記法來求解網(wǎng)絡(luò)最大流問題。標(biāo)記法的基本思路是：先假設(shè)網(wǎng)絡(luò)各支路中有一個滿足流量守恒方程的初始流量，該C1為了計算方便，可將可行流全部初始流量就稱為“可行流”。選擇可行流的方法有兩種:選為

27、零，因為零也是符合流量守恒方程的；。2為了加快計算速度，通常把可行流選擇成使網(wǎng)絡(luò)中某些主要支路飽和。然后在該可行流的基礎(chǔ)上，再試探著對其進(jìn)行擴充，一次次地試探擴充，直到再也無法擴充為止，這樣就找到了該網(wǎng)絡(luò)的最大流。標(biāo)記法的求解步驟如下：第一步，先給源點S以標(biāo)記(8),其中“表示開始，依據(jù)假設(shè)條件(1)可知“8”表示進(jìn)入源點S的流量可無窮大，這時源點S成為已標(biāo)記未檢查的點。第二步，用已標(biāo)記未檢查的點i對有聯(lián)系的未標(biāo)記的點j進(jìn)行檢查(1)首先檢查從已標(biāo)記點出發(fā)的支路C1如果初始流量小于最大容量，即X(i,j)<C(i,j),則將j點標(biāo)記為(i+,£(j),表示可以由i點向j點增加的

28、流量為e(j),其中s(j)表示i點能夠向j點提供的數(shù)量和支路可以進(jìn)一步擴充的流量中最小的一個，且£(j)=mine(i),C(i,j)-X(i,j),如圖11(a)所示；如果X(i,j)=C(i,j),則不標(biāo)記；完成上述檢查后，由i點出發(fā)的支路檢查完畢，j點成為已標(biāo)記未檢查的點。(2)檢查流向節(jié)點的支路C1如果X(j,i)>0,則將j點標(biāo)記為(i二£(j),表示i點向j點可以少提供的流量為£(j),實質(zhì)上也等于j點向i點多提供的流量為£(j),其中£(j)表示i點可以少提供的數(shù)量和流量中最小的一個，且 £圖11標(biāo)記法(j)=1

29、1(b)所示;已標(biāo)號 (fr)2當(dāng)£(i)<X(j,i),則表明i點不能提供足夠流量使X(j,i)=0,故還要有一部分流量流向i點；C3X(i,j)=0不標(biāo)記;通過對i點的檢查，使j點成為已標(biāo)記未檢查的點，而i點則由已標(biāo)記未檢查的點變?yōu)橐褬?biāo)記已檢查的點，這樣一直進(jìn)行到匯點T也標(biāo)記成(n+,£(T)為止。第三步，從匯點T反向查找可以擴充的路徑，并確定擴充量其方法是：由匯點T的標(biāo)記(n+,e(T),倒推到n點，再按n點的標(biāo)記倒推到n-1點,最后一直倒推到源點S為止，就可以找到由源點S到匯點T的一條可以擴充的路徑。在此擴充線路上標(biāo)記相應(yīng)的值e(j),并選e(j)=mine(

30、j)作為擴充量。第四步，根據(jù)擴充路徑上標(biāo)記的擴充流量對支路(i,j)擴充時，如果j點的標(biāo)記為i+,初始流量X(i,j)就增加e*(j);如果j點的標(biāo)記為i;初始流量X(i,j)就減少e*(j),這就完成了一次擴充，得到一個新的可行流。第五步，重復(fù)上述步驟，一直到無擴充路徑為止，即得到該網(wǎng)絡(luò)的最大流。例6某工地需要大量礫石，采石場與工地間的公路網(wǎng)及運輸能力如圖12所示，為了安排運輸計劃，試確定該公路網(wǎng)可運輸?shù)[石的最大數(shù)量為多少?圖12公路網(wǎng)及運輸能力解采用標(biāo)記法，假設(shè)已預(yù)先給定初始可行流并用括號標(biāo)注在線路旁。第一步，點S標(biāo)記(，8);第二步，對呂標(biāo)記,去檢查的S點進(jìn)行檢查。先看由i出發(fā)的支路(S,2)、(S,3)。因C(S,2)=13,X(S,2)=7,C(S,2)>X(S,2),則點2應(yīng)標(biāo)記(S+,&(2),£(2)=min巴c(s,2)X(S,2)=min8,6=6,所以點2標(biāo)記(S+,6),它表明由S可增加6單位流量到點2。此時，由于C(S,3)=9,X(S,3)=9為飽和支路；無指向點S的支路，故點S已檢查完，成為已標(biāo)記、已檢查的點。點2成為旦標(biāo)記耒檢直網(wǎng)點2.對其進(jìn)好檢查?一先看由點2出發(fā)的兩條支路(2,4)、(2,5),C(2,5)=X(2,5),C(2,4)=X(2,4)均為飽和支路；再看流向點2的支路(