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

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

2、o有向圖：由點(diǎn)和弧構(gòu)成的圖稱為有向圖，記作D=(V,A),其中V、A分別是D的頂點(diǎn)集合和弧的集合。從起始點(diǎn)vWV指向終點(diǎn)VjCV的弧a記為a=(vi,兇了(環(huán)，vi)o多重邊和環(huán)：兩個(gè)頂點(diǎn)間具有兩條以上的邊稱為多重邊；若邊的兩端為同一頂點(diǎn)則稱其為環(huán)，如圖1中的“邊7”。多重圖和簡(jiǎn)單圖：含多重邊的圖稱為多重圖；無(wú)環(huán)且無(wú)多重邊的圖稱為簡(jiǎ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)中，由一些頂點(diǎn)和邊所組成的交錯(cuò)序列v1，e1,v2,e2,，vi,ek,vk就稱為一條聯(lián)結(jié)頂點(diǎn)VI、Vk的鏈。開(kāi)鏈和閉合鏈：起點(diǎn)和終點(diǎn)不是同一頂點(diǎn)的鏈，則稱其為開(kāi)鏈，否則就稱其為閉合鏈。單純鏈和基本鏈：一條沒(méi)有重復(fù)邊的鏈稱為單純鏈，如圖3中的邊序列5,6,2,7,8;一個(gè)沒(méi)有重復(fù)頂點(diǎn)的鏈稱為基本鏈，如圖3中的邊序列1,2,3。路和回路：一個(gè)開(kāi)的基本鏈稱為路，如圖中的邊序列1,6,7,3;一個(gè)閉合的基本鏈稱為回路，如圖中的邊序列1,6,5。連通圖：如果在一個(gè)圖中任意兩個(gè)不同的頂點(diǎn)之間至少有一條路，則該圖就稱為連通圖。圖3鏈圖4樹(shù)（3）樹(shù)樹(shù)：如果連通圖G的子圖Gi也是連通

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

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

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

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

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

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

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

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

12、號(hào)的頂點(diǎn)是2和3,則將這兩個(gè)頂點(diǎn)的T類標(biāo)號(hào)改為T(mén)(2)=minT(2),P(1)+I12=min-,0+4=4T(3)=minT(3),P(1)+I13=min8,0+3=3在所有的T類標(biāo)號(hào)中，T(3)=3最小，于是令P=3,即頂點(diǎn)3獲得固定標(biāo)號(hào)；第二步0與頂點(diǎn)3直接相連且又為臨日標(biāo)號(hào)的頂點(diǎn)是2和5,則將它們的T類標(biāo)號(hào)改為T(mén)(2)=minT(2),P(3)+I32=min4,3+2=4T(5)=minT(5),P+135=min8,3+2=5CD在所有的T類標(biāo)號(hào)中，T(2)=4最小，于是令P(2)=4;第三步0與頂點(diǎn)2直接相連且又為臨日標(biāo)號(hào)的頂點(diǎn)是4和5,則將它們的T類標(biāo)號(hào)改為T(mén)(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)號(hào)中，T(5)=5最小，于是令P(5)=5;第四步。與頂點(diǎn)5直接相連且又為臨日標(biāo)號(hào)的頂點(diǎn)是4和6,則將它們的T類標(biāo)號(hào)改為T(mén)(4)=minT(4),P+154=min7,5+2=7T(6)=minT(6),P+156=min8,5+4=9CD在所有的T類標(biāo)號(hào)中，T(4)=7最小，于是令P(4)=7;第五步0與頂點(diǎn)4直接相連且又為臨時(shí)標(biāo)號(hào)的頂點(diǎn)只有6,則將它的T類標(biāo)號(hào)改為T(mén)(6)=minT(6),P(4)+146=min9,7+3=9C2顯然應(yīng)令P(6)=9,即終點(diǎn)(頂點(diǎn)6

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

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

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

18、=1）時(shí)各點(diǎn)間的最短距離，相應(yīng)的路徑表示經(jīng)過(guò)中間點(diǎn)1的最短路徑。例如，d421=2表示路徑4一1一2對(duì)應(yīng)的距離為2。第三步，由D1矩陣按上述方法求出D2矩陣和相應(yīng)的路徑此時(shí)中間點(diǎn)為兩個(gè)，即m=2,其計(jì)算公式為dij2=mindi21+d2j1,dij1dij2=mindi21+d2j1,dij1中間點(diǎn)dij2=mindi21+d2j1,dij1中間點(diǎn)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_由于沒(méi)有選擇中間點(diǎn)，所以對(duì)應(yīng)的路徑與上一步相同。注意，D2中的矩陣元素表示經(jīng)過(guò)兩個(gè)中間點(diǎn)時(shí)各點(diǎn)間的最短距離，而不是經(jīng)過(guò)第二個(gè)頂點(diǎn)時(shí)各點(diǎn)間的最短距離，因?yàn)楣絛ij2=mindi21+d2j1,dij1中di21+d2j1或dij1為已經(jīng)經(jīng)過(guò)一個(gè)中間點(diǎn)

20、的值。第四步，由D2矩陣按上述方法求出D3矩陣和相應(yīng)的路徑此時(shí)中間點(diǎn)為三個(gè)，即m=3,其計(jì)算公式為dij3=mindi32+d3j2,dij2dij3=mindi32+d3j2,dij2中間點(diǎn)dij3=mindi32+d3j2,dij2中間點(diǎn)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對(duì)應(yīng)的路徑仍同上。第四步，由D3矩陣按上述方法求出此時(shí)中間點(diǎn)為四個(gè)，即m=4,其計(jì)算公式為333.dij=mindi4+d4j,dij其計(jì)算結(jié)果為-0231121043402230dij4=mindi43+d4j3,dij3中間點(diǎn)dij4=mindi43+d4j3,dij3中間點(diǎn)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對(duì)應(yīng)的路徑矩陣為12341 一12 113 444 -11一由D4矩陣可求出網(wǎng)絡(luò)圖中任意兩點(diǎn)間的最短距離，并確定所對(duì)應(yīng)的路徑。例如，點(diǎn)3到點(diǎn)2之間的的最短距離是4;且由路徑矩陣可知，先由第3行

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

24、(i,j)等于支路容量C(i,j),就稱為支路飽和。2 .基本定理及其有關(guān)概念(1)流量守恒定律根據(jù)上述假設(shè)，仿照電路中的基爾霍夫定律，可以得到流量守恒定律。如果匯X(i,j),jCV(i)表示流出i點(diǎn)的總流量，其中V(i)為可直接到達(dá)j點(diǎn)的點(diǎn)集合；而匯X(j,i),jCR(i)表示流入i點(diǎn)的總流量，其中R(i)為可直接到達(dá)i點(diǎn)的點(diǎn)集合，由于基爾霍夫定律中流入節(jié)點(diǎn)的電流之和與流出節(jié)點(diǎn)的電流之和相等的原理，與上述假設(shè)中的中間點(diǎn)只起傳遞作用相似，因此有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),即實(shí)際流量為非負(fù)且不大于線路的容量，因此，網(wǎng)絡(luò)最大流問(wèn)題的數(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)該問(wèn)題單純形法可以得到最優(yōu)解，故最大流問(wèn)題本質(zhì)上是線性規(guī)劃問(wèn)題，但是當(dāng)網(wǎng)絡(luò)較大時(shí)，約束方程的數(shù)量和變量的個(gè)數(shù)較多，線性規(guī)劃模型很大，不便于求解，則利用圖的特性可是問(wèn)題的求解變得容易。(2)割集和割集容量設(shè)G是一個(gè)連通圖，則滿足下列條件的邊的集合就稱為割集：把這些邊全部從圖G中去掉，則圖G成為

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

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

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

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

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