[高等教育]第l六章運籌學(xué)圖與網(wǎng)絡(luò)-資料下載頁
2025-01-21 22:47本頁面
【正文】 ?⒌ 抹去網(wǎng)絡(luò)圖中的所有標號 ,重復(fù)第 1到第 4步 ,一直到在網(wǎng)絡(luò)中找不到任何增廣鏈 ,即出現(xiàn)第 3步的結(jié)局 (1)為止 ,這時網(wǎng)絡(luò)中的流量為網(wǎng)絡(luò)的最大流 . s t1v2v3v4v)8(8)5(7)4(5)4(9)0(2)9(9)1(6)5(5)8(10例 8 用標號法求下面網(wǎng)絡(luò)從 s到 t的最大流量 ,并找出該網(wǎng)絡(luò)的最小割 . ),0( ?)2,(s)2,( 2v )2,(1v)1,( 3v)1,( 4v解 : ⑴ 先給 s標號 。 ),0( ?⑵ 從 s點出發(fā)的弧為 ,因為 對 暫時不標號 ,而 ),(),( 21 vsvs 811 ?? ss cf1v? ?? ? )。2,(,257,m i n)(),(m i n)()),(,(22222svfcsvvs ss標號對其中?????? ???標號對 222 ,75 vcf ss ???⑶ ? ? ? ?)。2,(,24,2m i n),(m i n)()),(,(,0),(,9),(),(,0),(),(2112211211221242442233223212vvfvvvvvfvvcfvvvvfvvvvv號為的標其中標號故對對反向弧不考慮此弧對于弧不考慮弧的弧有指向?????????????⑷ ? ?? ? )。2,(,25,2m i n)(),(m i n)()),(,(,94),(131313133131313211vvfcvvvvvcfvvv的標號為其中標號對因為出發(fā)的弧為從已標號點??????????⑸ ? ? ? ?)。1,(,11,2m i n),(m i n)()),(,(,0),(?))(,(),(34433443443343233vvfvvvvvfvvtvvvv的表號為其中標號故對因為對于反向弧為什么顯然不考慮弧對已標號點???????⑹ ? ?? ? ? ? )。1,(,12,1m i n810,1m i n),(m i n)()),(,(,),(44444444vtfcvttvtcftvtttt標號對其中點得到標號因為是從已標號點出發(fā)的弧對于弧??????????⑺ 因為 t點得到標號 ,用反向追蹤法可找出從 s到t的一條增廣鏈 ,用紅線標出 。 ⑻ 修改增廣鏈上的流量 : 其余弧上的流量不變 ,于是得到網(wǎng)絡(luò)上的一個新可行流 ,重復(fù)上述的標號過程 ,轉(zhuǎn)下一步 。 前向弧后向弧前向弧后向弧前向弧918)(011)(514)(314)(615)(4443431313121222??????????????????????????????tfftfftfftfftffttss?????s t1v2v3v4v)8(8)6(7)3(5)5(9)0(2)9(9)0(6)5(5)9(10),0( ?)1,(s)1,( 2v)1,( 1v標號中斷 ,t點得不到標號 ,網(wǎng)絡(luò)中沒有增廣鏈 ,該網(wǎng)絡(luò)的可行流就是最大流 ,最大流量為 )(14)(* 收點的總輸入量發(fā)點的總輸出量 ??fV)。,0()9( ?標號對 s? ? )。1,()67,m i n,(,76),(),()10(22221ssvcfvsvs ss??????標號對因為而考慮弧不考慮弧? ?? ? )。1,()3,1m i n,()),(m i n,(),(),(),(,)11(22122212123422vvfvvvvvvvvvv???標號對考慮反向弧只不考慮弧出發(fā)從已標號點? ? ? ?)。1,()4,1m i n,()),(m i n,(,),()12(1113131131313311vvfcvvvcfvvv?????標號故對因為出發(fā)的弧考慮從已標號點.14)(,,),(),()13(*343?fVttvvv最大流是中的可行流最大流就是網(wǎng)絡(luò)網(wǎng)絡(luò)中不存在增廣鏈得不到標號點因此標號中斷均不能考慮弧下面求該網(wǎng)絡(luò)的最小割 : ? ?...1495,)4,2(),3(),(.)(,表示最小割的位置線畫出小割的容量的結(jié)論了最大流的流量等于最印證最小割的容量為該網(wǎng)絡(luò)的最小割為稱為最小割后向弧不包含的弧集合及則連接標號點的集合記為未已標號點的集合記為在產(chǎn)生最大流的網(wǎng)絡(luò)中kktVVVVVV???s t1v2v3v4v)8(8)6(7)3(5)5(9)0(2)9(9)0(6)5(5)9(10),0( ?)1,(s)1,( 2v)1,( 1vkk? ?.14),(),(),(),(, 342??VVCtvvvVVkk最小割的容量包含的弧集合為割為最小割例 9 在下面的網(wǎng)絡(luò)中求 到 的最大流，弧旁邊的數(shù)是容量 。 sv tvsv2v3v4v5v6vtv? ?14? ?10??3??6??6? ?10??5??5 ??5??4??4??9ijc本題的網(wǎng)絡(luò)中沒有標明可行流，理論上應(yīng)從零流開始迭代，但是這樣作太繁瑣?，F(xiàn)在介紹用直接消除增廣鏈的方法，求網(wǎng)絡(luò)最大流的簡單算法。 。，，，f，fc，vv，ijijijts這時便得到最大流廣鏈到消除網(wǎng)絡(luò)中的所有增直繼續(xù)下去累加并在圖上直接將為調(diào)整量選出它們的最小值取后向弧取對前向弧的增廣鏈依次取從零流開始????????sv140=14 2v60=6 5v tv90=9 6??sv 3v2v 4v 5v tv 3??10010 ?? 303 ?? 505 ?? 505 ?? 369 ??sv 2v 4v tv8614 ?? 235 ?? 404 ?? 2??sv 3v 4vtv7310 ?? 505 ?? 224 ?? 2??sv 3v4v 6v tv? ? 52310 ??? 325 ?? 404 ?? 10010 ?? 3??sv 3v 6v tv? ? 232310 ???? 606 ?? 7310 ?? 2??sv 2v 3v 6v tv? ? 62614 ???3426 ?? ? ? 52310 ???3??? ? ? ? ? ?? ? ? ? ? ? ? ? 21323362221232332665432???????????????????????tttssffffvfffv或sv2v3v4v5v6vtv? ?14? ?10??3??6??6? ?10??5??5??5??4??4??9326 ??2323 ???32?33? 23?3323?636?22?323
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1