網(wǎng)絡(luò)最大流課件.ppt

《網(wǎng)絡(luò)最大流課件.ppt》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第六章???網(wǎng)絡(luò)最大流網(wǎng)絡(luò)最大流問(wèn)題50年代福特（Ford）、富克遜（Fulkerson）建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。如同我們可以把一個(gè)實(shí)際的道路地圖抽象成一個(gè)有向圖來(lái)計(jì)算兩點(diǎn)之間的最短路徑，我們也可以將一個(gè)有向圖看作一個(gè)流網(wǎng)絡(luò)來(lái)解決另一類(lèi)型的問(wèn)題。流網(wǎng)絡(luò)比較適合用來(lái)模擬液體流經(jīng)管道、電流在電路網(wǎng)絡(luò)中的運(yùn)動(dòng)、信息網(wǎng)絡(luò)中信息的傳遞等等類(lèi)似的過(guò)程。問(wèn)題的提出在一個(gè)輸油管網(wǎng)中，有生產(chǎn)石油的油井、儲(chǔ)存石油的油庫(kù)、轉(zhuǎn)運(yùn)石油的中間泵站，同時(shí)，還有各種口徑不同的輸油管。當(dāng)一個(gè)輸油管網(wǎng)給定后，單位時(shí)間內(nèi)最

2、多可把多少石油從油井輸送到油庫(kù)？具體方案如何？分析：就輸油管網(wǎng)絡(luò)問(wèn)題，可用頂點(diǎn)表示油井、油庫(kù)和中間泵站，用有向邊表示輸油管，用有向邊上的權(quán)表示單位時(shí)間沿相應(yīng)的輸油管可以輸送石油的最大數(shù)量（容量）。如果我們把圖看做輸油管道網(wǎng)，為起點(diǎn)，為終點(diǎn)，為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問(wèn)應(yīng)該如何安排各管道輸油量，才能使從到的總輸油量最大？問(wèn)題的提出管道網(wǎng)絡(luò)中每邊的最大通過(guò)能力即容量是有限的，實(shí)際流量也不一定等于容量，上述問(wèn)題就是要討論如何充分利用裝置的能力，以取得最好效果（流量最大），這類(lèi)問(wèn)題通常稱(chēng)為最大流問(wèn)題

3、。vsv1v3vtv2v48799562510容量發(fā)點(diǎn)（源）收點(diǎn)（匯）中間點(diǎn)容量網(wǎng)絡(luò)網(wǎng)絡(luò)有向圖D=（V，A，C）網(wǎng)絡(luò)上流的基本概念vsv1v3vtv2v48799562510流vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)運(yùn)輸問(wèn)題中，每個(gè)運(yùn)輸方案就是一個(gè)流可行流網(wǎng)絡(luò)最大流問(wèn)題且滿(mǎn)足此為一個(gè)特殊的線(xiàn)性規(guī)劃問(wèn)題，將會(huì)看到利用圖的特點(diǎn)，解決這個(gè)問(wèn)題的方法要比單純形法較為直觀方便。設(shè)是網(wǎng)絡(luò)D=（V，A，C）的一個(gè)可行流（v1，v2）是飽和的2、如果0≤fij

4、，該弧是非飽和?。唬╲1，v2）是不飽和的間隙為?12=c12-f12=5-3=21、如果fij=cij，該弧是飽和?。换￡P(guān)于流的分類(lèi)fij=5cij=5v1v2fij=3cij=5v1v2設(shè)是網(wǎng)絡(luò)D=（V，A，C）的一個(gè)可行流（v1，v2）是0流弧4、如果fij>0，該弧是非0弧；（v1，v2）是非0弧3、如果fij=0，該弧是0流??；弧關(guān)于流的分類(lèi)fij=0cij=5v1v2fij>0cij=5v1v2鏈及可增廣鏈鏈在最大流問(wèn)題中，研究的是有向網(wǎng)絡(luò)圖。但是在求最大流的方法中，則要使用無(wú)向網(wǎng)絡(luò)中的鏈。vsv

5、1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非0流弧可增廣鏈vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非飽和弧割集和割集的容量設(shè)有網(wǎng)絡(luò)D={V，A，C}，點(diǎn)vs與點(diǎn)vt的是集合V中的任意兩點(diǎn)，若點(diǎn)集V被剖分成兩個(gè)非空集合，使，記以中的點(diǎn)為始點(diǎn)，的A中弧的集合記為則稱(chēng)這個(gè)弧的集合是分離點(diǎn)vs與點(diǎn)vt的割集（又稱(chēng)截集）。中的點(diǎn)為終點(diǎn)割集的容量是割集中各弧的容量之和，用表示。割集的容量為9+9=18割集KKvsv

6、1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)考慮KK的不同畫(huà)法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)割集割集容量基本定理(可行流與割集的關(guān)系)由于有限網(wǎng)絡(luò)的割集只有有限多個(gè)，則截集容量的集合是有限的實(shí)數(shù)集合，令稱(chēng)割集容量為C0的割集為D的最小割集。（瓶頸）§2割切-定理6.1證明－1[]wffSjSijiij=-???,∵又∵0≤fij≤cij∴fij－fji≤fij≤cij因?yàn)楦罴侨我獾?，所以得證。

7、[]=≤-=??????SjSiijSjSijiijcffw,,C(S,)S∴證明增廣路定理：證明：1必要性v(f)為最大流，則不存在可增廣鏈；因?yàn)槿舸嬖谠鰪V鏈，則v(f)不為最大流。2充分性不存在可增廣鏈，則v(f)為最大流；若網(wǎng)絡(luò)流圖G中不存在可增廣路，則考察所有s到t的路徑，將滿(mǎn)足增廣條件路徑連接的節(jié)點(diǎn)并入集合S中，遇到不滿(mǎn)足條件點(diǎn)時(shí)停止；T=V/S，[S,T]為s-t割集。這時(shí)，對(duì)于任意弧(i,j)，若是前向弧，fij=cij，若是逆向弧，fji=0,下式成立，v(f)為最大流,C[S,T]為最小割。

8、[]==-=??????TjSiijTjSijiijcffw,,C(S,)T∴最大流-最小割定理：v(fmax)=Cmin[S,T];這樣就得到了一個(gè)尋求最大流的方法(算法思想)：從一個(gè)可行流開(kāi)始，尋求關(guān)于這個(gè)可行流的可增廣鏈，若存在，則可以經(jīng)過(guò)調(diào)整，得到一個(gè)新的可行流，其流量比原來(lái)的可行流要大，重復(fù)這個(gè)過(guò)程，直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流。沿著這條鏈從vs到vt輸送流，還有潛力可挖，