北郵運(yùn)籌學(xué)ch74 最大流問(wèn)題

1、基本概念4844122679：在某時(shí)期內(nèi)弧(i，j)上的最大通過(guò)能力。記為C (i，j)或Cij 在上圖中，C12=4，C138，C234等，怎樣安排運(yùn)輸方案，才能使在某一時(shí)期內(nèi)從v1運(yùn)到v6的物資最多，這樣的問(wèn)題就是最大流問(wèn)題，網(wǎng)絡(luò)中所有流起源于一個(gè)叫做發(fā)點(diǎn)的節(jié)點(diǎn)（源） 所有的流終止于一個(gè)叫做收點(diǎn)的節(jié)點(diǎn)其余所有的節(jié)點(diǎn)叫做中間點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)） 通過(guò)每一條弧的流只允許沿著弧的箭頭方向流動(dòng)目標(biāo)是使得從發(fā)點(diǎn)到收點(diǎn)的總流量最大7/20/2022流量：弧(i，j)的實(shí)際通過(guò)量，記為f (i，j)或f ij可行流：如果f ij滿足： 1.對(duì)于所有弧(i，j)有0f ijCij 2.對(duì)于發(fā)點(diǎn)vs有：3.對(duì)于收點(diǎn)

2、vt有：則稱(chēng)流量集合f ij為網(wǎng)絡(luò)的一個(gè)可行流，簡(jiǎn)記為 f , v稱(chēng)為可行流的流量或值，記為v(f).以下假設(shè)網(wǎng)絡(luò)是一個(gè)簡(jiǎn)單連通圖。4.對(duì)于中間點(diǎn)點(diǎn)vm有：7/20/2022截集 將圖G（V，E）的點(diǎn)集分割成兩部分稱(chēng)為一個(gè)截集，截集中所有弧的容量之和稱(chēng)為截集的截量。68441226796411322306下圖所示的截集為請(qǐng)看演示7/20/202268441226796401322106又如下圖所示的截集為上圖所示的截集為所有截量中此截量最小且等于最大流量，此截集稱(chēng)為最小截集?！径ɡ怼孔畲罅髁康扔谧钚〗丶慕亓?。7/20/2022鏈：從發(fā)點(diǎn)到收點(diǎn)的一條路線（弧的方向不一定都同向）稱(chēng)為鏈。從發(fā)點(diǎn)到

3、收點(diǎn)的方向規(guī)定為鏈的方向。前向?。号c鏈的方向相同的弧稱(chēng)為前向弧。后向?。号c鏈的方向相反的弧稱(chēng)為后向弧。增廣鏈 設(shè) f 是一個(gè)可行流，如果存在一條從vs到vt的鏈，滿足：1.所有前向弧上fij0則該鏈稱(chēng)為增廣鏈前向弧后向弧8446952346容量流量想一想，這是一條增廣鏈嗎？7/20/2022【定理】設(shè)網(wǎng)絡(luò)G的一個(gè)可行流f，如果存在一條從vs到vt的增廣鏈，那么就可改進(jìn)一個(gè)值更大的可行流f1，并且val f1val f【證】設(shè)val fv對(duì)改進(jìn)的可行流f1 ：7/20/2022最大流的標(biāo)號(hào)算法步驟 1. 找出第一個(gè)可行流，例如所有弧的流量fij =0 2. 用標(biāo)號(hào)的方法找一條增廣鏈 A1：發(fā)點(diǎn)標(biāo)

4、號(hào)（）， A2：選一個(gè)點(diǎn) vi 已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查： 如果弧的方向向前并且有fij0，則vj標(biāo)號(hào)（fji)當(dāng)收點(diǎn)不能得到標(biāo)號(hào)時(shí)，說(shuō)明不存在增廣鏈，計(jì)算結(jié)束。當(dāng)收點(diǎn)已得到標(biāo)號(hào)時(shí)，說(shuō)明已找到增廣鏈。【定理】可行流是最大流當(dāng)且僅當(dāng)不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈7/20/20224. 調(diào)整流量 得到新的可行流，去掉所有標(biāo)號(hào)，從發(fā)點(diǎn)重新標(biāo)號(hào)尋找增廣鏈，直到收點(diǎn)不能標(biāo)號(hào)為止。3. 依據(jù)vi 的第一個(gè)標(biāo)號(hào)反向跟蹤得到一條增廣鏈； 依據(jù)vi 的第二個(gè)標(biāo)號(hào)求最小值得到調(diào)整量進(jìn)入演示和練習(xí)7/20/2022 684412267942202222046217【例】求下圖v1 到v6 的最大流及

5、最大流量【解】1. 通過(guò)觀察得到初始可行流2.標(biāo)號(hào)3. 得到增廣鏈7/20/2022 68441226794211322304223 得到增廣鏈 4.求調(diào)整量 5.調(diào)整可行流 去掉所有標(biāo)號(hào)，重新標(biāo)號(hào) 6844122679422022220462177/20/202268441226796411322306 求調(diào)整量 調(diào)整可行流 去掉所有標(biāo)號(hào)，重新標(biāo)號(hào)5標(biāo)號(hào)不能繼續(xù)進(jìn)行，說(shuō)明不存在從發(fā)點(diǎn)到收點(diǎn)的增廣鏈，得到最大流.最大流量 v=6+3=917/20/2022The End of Chapter 6 作業(yè): 教材P285 T10.11 10.12 10.14下一章：網(wǎng)絡(luò)計(jì)劃Exit1.基本概念 容量、流量、可