《運籌學(xué) 最大流問題》由會員分享，可在線閱讀，更多相關(guān)《運籌學(xué) 最大流問題（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、 第1頁/共28頁。vtv3v2v1v4vs1735108611453Cij第2頁/共28頁第3頁/共28頁ijt ji sWff對于發(fā)點vs,收點vt有對于中間點，有EvvEvvi jjijiijff),(),(0第4頁/共28頁 第5頁/共28頁v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt第6頁/共28頁SSVSSSS,SSSSSEEEE E EE第7頁/共28頁vtvsv1v2v3v442443322231邊集(vs,v1),(vs,v3),(vs,v4)邊集(vs,v1),(v1,v3),(v2,v3),(v3,vt)為圖的割集，割集容量分
2、別為11，9第8頁/共28頁后向的集合記做。SS第9頁/共28頁 vtvsv1v2v3v442443322231第10頁/共28頁第11頁/共28頁第12頁/共28頁第13頁/共28頁 第14頁/共28頁2.2.調(diào)整過程令 不在可增廣鏈),(,),(,),(,jijijitjijitjijivvfvvfvvff3.3.再去掉所有的標(biāo)號，對新的可行流f=f ij,重新進行標(biāo)號過程，直到找到網(wǎng)絡(luò)G G的最大流為止。第15頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)例 求圖的網(wǎng)絡(luò)最大流，弧旁的權(quán) 數(shù)表
3、示（cij,fij）。第16頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)()第17頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)()第18頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)()第19頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,
4、2)(5,2)(4,2)(2,2)()第20頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)()第21頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)()第22頁/共28頁 從vt開始，按照標(biāo)號點的第一個標(biāo)號，用反向追蹤的方法，找出一條從vs到vt的增廣鏈，如圖G G中虛線所示。不難看出,+=(vs,v2),(v1,v4),(v4,vt),=(v5,v1),取 =，在上調(diào)整f，得到f*=f4t+=2+2=
5、4 在+上f14+=2+2=4 在+上f25+=0+2=2 在+上fs2+=2+2=4 在+上 f15=3 2=1 在-上其它的不變第23頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,1)(4,4)(5,4)(3,3)(2,2)(5,4)(4,4)(2,2)(3,2)第24頁/共28頁vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)()4)4)1)(3,0)2)4)第一條可增廣鏈：vs-v2,v5,v1,v4,vt,調(diào)整量為：2流量：f=11無可增廣鏈最大流=14割集=(vs,v1),(vs,v2),(v3,v6)第25頁/共28頁 求最大流的標(biāo)號算法可以解決多發(fā)點多收點網(wǎng)絡(luò)的最大流問題X1X2X3xmY1Y2Y3ynvsvt+第26頁/共28頁 小結(jié) 1、最大流問題的概念、最大流-最小割定理。2、求最大流問題的標(biāo)號算法。作業(yè) 8.10,8.14 第27頁/共28頁感謝您的觀看！第28頁/共28頁
運籌學(xué) 最大流問題
