北郵運籌學ch74 最大流問題

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

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

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

4、號（）， A2：選一個點 vi 已標號并且另一端未標號的弧沿著某條鏈向收點檢查： 如果弧的方向向前并且有fij0，則vj標號（fji)當收點不能得到標號時，說明不存在增廣鏈，計算結(jié)束。當收點已得到標號時，說明已找到增廣鏈?！径ɡ怼靠尚辛魇亲畲罅鳟斍覂H當不存在發(fā)點到收點的增廣鏈7/20/20224. 調(diào)整流量 得到新的可行流，去掉所有標號，從發(fā)點重新標號尋找增廣鏈，直到收點不能標號為止。3. 依據(jù)vi 的第一個標號反向跟蹤得到一條增廣鏈； 依據(jù)vi 的第二個標號求最小值得到調(diào)整量進入演示和練習7/20/2022 684412267942202222046217【例】求下圖v1 到v6 的最大流及

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