[高等教育]第l六章運(yùn)籌學(xué)圖與網(wǎng)絡(luò)-資料下載頁(yè)
2025-01-21 22:47本頁(yè)面
【正文】 ?⒌ 抹去網(wǎng)絡(luò)圖中的所有標(biāo)號(hào) ,重復(fù)第 1到第 4步 ,一直到在網(wǎng)絡(luò)中找不到任何增廣鏈 ,即出現(xiàn)第 3步的結(jié)局 (1)為止 ,這時(shí)網(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 用標(biāo)號(hào)法求下面網(wǎng)絡(luò)從 s到 t的最大流量 ,并找出該網(wǎng)絡(luò)的最小割 . ),0( ?)2,(s)2,( 2v )2,(1v)1,( 3v)1,( 4v解 : ⑴ 先給 s標(biāo)號(hào) 。 ),0( ?⑵ 從 s點(diǎn)出發(fā)的弧為 ,因?yàn)? 對(duì) 暫時(shí)不標(biāo)號(hào) ,而 ),(),( 21 vsvs 811 ?? ss cf1v? ?? ? )。2,(,257,m i n)(),(m i n)()),(,(22222svfcsvvs ss標(biāo)號(hào)對(duì)其中?????? ???標(biāo)號(hào)對(duì) 222 ,75 vcf ss ???⑶ ? ? ? ?)。2,(,24,2m i n),(m i n)()),(,(,0),(,9),(),(,0),(),(2112211211221242442233223212vvfvvvvvfvvcfvvvvfvvvvv號(hào)為的標(biāo)其中標(biāo)號(hào)故對(duì)對(duì)反向弧不考慮此弧對(duì)于弧不考慮弧的弧有指向?????????????⑷ ? ?? ? )。2,(,25,2m i n)(),(m i n)()),(,(,94),(131313133131313211vvfcvvvvvcfvvv的標(biāo)號(hào)為其中標(biāo)號(hào)對(duì)因?yàn)槌霭l(fā)的弧為從已標(biāo)號(hào)點(diǎn)??????????⑸ ? ? ? ?)。1,(,11,2m i n),(m i n)()),(,(,0),(?))(,(),(34433443443343233vvfvvvvvfvvtvvvv的表號(hào)為其中標(biāo)號(hào)故對(duì)因?yàn)閷?duì)于反向弧為什么顯然不考慮弧對(duì)已標(biāo)號(hào)點(diǎn)???????⑹ ? ?? ? ? ? )。1,(,12,1m i n810,1m i n),(m i n)()),(,(,),(44444444vtfcvttvtcftvtttt標(biāo)號(hào)對(duì)其中點(diǎn)得到標(biāo)號(hào)因?yàn)槭菑囊褬?biāo)號(hào)點(diǎn)出發(fā)的弧對(duì)于弧??????????⑺ 因?yàn)?t點(diǎn)得到標(biāo)號(hào) ,用反向追蹤法可找出從 s到t的一條增廣鏈 ,用紅線標(biāo)出 。 ⑻ 修改增廣鏈上的流量 : 其余弧上的流量不變 ,于是得到網(wǎng)絡(luò)上的一個(gè)新可行流 ,重復(fù)上述的標(biāo)號(hào)過程 ,轉(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標(biāo)號(hào)中斷 ,t點(diǎn)得不到標(biāo)號(hào) ,網(wǎng)絡(luò)中沒有增廣鏈 ,該網(wǎng)絡(luò)的可行流就是最大流 ,最大流量為 )(14)(* 收點(diǎn)的總輸入量發(fā)點(diǎn)的總輸出量 ??fV)。,0()9( ?標(biāo)號(hào)對(duì) s? ? )。1,()67,m i n,(,76),(),()10(22221ssvcfvsvs ss??????標(biāo)號(hào)對(duì)因?yàn)槎紤]弧不考慮弧? ?? ? )。1,()3,1m i n,()),(m i n,(),(),(),(,)11(22122212123422vvfvvvvvvvvvv???標(biāo)號(hào)對(duì)考慮反向弧只不考慮弧出發(fā)從已標(biāo)號(hào)點(diǎn)? ? ? ?)。1,()4,1m i n,()),(m i n,(,),()12(1113131131313311vvfcvvvcfvvv?????標(biāo)號(hào)故對(duì)因?yàn)槌霭l(fā)的弧考慮從已標(biāo)號(hào)點(diǎn).14)(,,),(),()13(*343?fVttvvv最大流是中的可行流最大流就是網(wǎng)絡(luò)網(wǎng)絡(luò)中不存在增廣鏈得不到標(biāo)號(hào)點(diǎn)因此標(biāo)號(hào)中斷均不能考慮弧下面求該網(wǎng)絡(luò)的最小割 : ? ?...1495,)4,2(),3(),(.)(,表示最小割的位置線畫出小割的容量的結(jié)論了最大流的流量等于最印證最小割的容量為該網(wǎng)絡(luò)的最小割為稱為最小割后向弧不包含的弧集合及則連接標(biāo)號(hào)點(diǎn)的集合記為未已標(biāo)號(hào)點(diǎn)的集合記為在產(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ò)中沒有標(biāo)明可行流，理論上應(yīng)從零流開始迭代，但是這樣作太繁瑣?，F(xiàn)在介紹用直接消除增廣鏈的方法，求網(wǎng)絡(luò)最大流的簡(jiǎn)單算法。 。，，，f，fc，vv，ijijijts這時(shí)便得到最大流廣鏈到消除網(wǎng)絡(luò)中的所有增直繼續(xù)下去累加并在圖上直接將為調(diào)整量選出它們的最小值取后向弧取對(duì)前向弧的增廣鏈依次取從零流開始????????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號(hào)-1