最大流問題優(yōu)秀課件

第八章

圖與網(wǎng)絡(luò)分析

圖的基本概念與模型

樹圖和圖的最小部分樹

最短路問題

網(wǎng)絡(luò)最大流問題

最小費(fèi)用最大流問題

第八章

圖與網(wǎng)絡(luò)分析

圖的基本概念與模型

樹圖和圖的最小部分樹

最短路問題

網(wǎng)絡(luò)最大流問題

最小費(fèi)用最大流問題

網(wǎng)絡(luò)最大流問題50年代福特（Ford）、富克遜（Fulkerson）建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。

如同我們可以把一個(gè)實(shí)際的道路地圖抽象成一個(gè)有向圖來計(jì)算兩點(diǎn)之間的最短路徑，我們也可以將一個(gè)有向圖看作一個(gè)流網(wǎng)絡(luò)來解決另一類型的問題。

流網(wǎng)絡(luò)比較適合用來模擬液體流經(jīng)管道、電流在電路網(wǎng)絡(luò)中的運(yùn)動(dòng)、信息網(wǎng)絡(luò)中信息的傳遞等等類似的過程。問題的提出在一個(gè)輸油管網(wǎng)中，有生產(chǎn)石油的油井、儲(chǔ)存石油的油庫、轉(zhuǎn)運(yùn)石油的中間泵站，同時(shí)，還有各種口徑不同的輸油管。當(dāng)一個(gè)輸油管網(wǎng)給定后，單位時(shí)間內(nèi)最多可把多少石油從油井輸送到油庫？具體方案如何？

分析：就輸油管網(wǎng)絡(luò)問題，可用頂點(diǎn)表示油井、油庫和中間泵站，用有向邊表示輸油管，用有向邊上的權(quán)表示單位時(shí)間沿相應(yīng)的輸油管可以輸送石油的最大數(shù)量（容量）。

如果我們把圖看做輸油管道網(wǎng)，為起點(diǎn)，為終點(diǎn)，為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問應(yīng)該如何安排各管道輸油量，才能使從到的總輸油量最大？

問題的提出管道網(wǎng)絡(luò)中每邊的最大通過能力即容量是有限的，實(shí)際流量也不一定等于容量，上述問題就是要討論如何充分利用裝置的能力，以取得最好效果（流量最大），這類問題通常稱為最大流問題。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)輸問題中，每個(gè)運(yùn)輸方案就是一個(gè)流可行流網(wǎng)絡(luò)最大流問題且滿足此為一個(gè)特殊的線性規(guī)劃問題，將會(huì)看到利用圖的特點(diǎn)，解決這個(gè)問題的方法要比單純形法較為直觀方便。設(shè)

是網(wǎng)絡(luò)D=（V，A，C）的一個(gè)可行流（v1，v2）是飽和的2、如果0≤fij<cij，該弧是非飽和?。唬╲1，v2）是不飽和的間隙為12=c12-f12=5-3=21、如果fij=cij，該弧是飽和??；弧關(guān)于流的分類fij=5cij=5v1v2fij=3cij=5v1v2設(shè)

是網(wǎng)絡(luò)D=（V，A，C）的一個(gè)可行流（v1，v2）是0流弧4、如果fij>0，該弧是非0?。唬╲1，v2）是非0弧3、如果fij=0，該弧是0流?。换￡P(guān)于流的分類fij=0cij=5v1v2fij>0cij=5v1v2鏈及可增廣鏈鏈在最大流問題中，研究的是有向網(wǎng)絡(luò)圖。但是在求最大流的方法中，則要使用無向網(wǎng)絡(luò)中的鏈。vsv1v3vtv2v48(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中弧的集合記為則稱這個(gè)弧的集合是分離點(diǎn)vs與點(diǎn)vt的割集（又稱截集）。中的點(diǎn)為終點(diǎn)割集的容量是割集中各弧的容量之和，用表示。割集的容量為9+9=18割集KK割集的意義：若把某一割集的弧從網(wǎng)絡(luò)中丟去，則從vs到vt便不存路，即割集是從vs到vt的必經(jīng)之道！這里(v3,v2)不屬于此割集vsv1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)考慮KK的不同畫法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)割集割集容量由于有限網(wǎng)絡(luò)的割集只有有限多個(gè)，則截集容量的集合是有限的實(shí)數(shù)集合，令

稱割集容量為C0的割集為D的最小割集。（瓶頸）基本定理(可行流與割集的關(guān)系)最大流-最小割定理：構(gòu)造法證明這樣就得到了一個(gè)尋求最大流的方法(算法思想)：從一個(gè)可行流開始，尋求關(guān)于這個(gè)可行流的可增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個(gè)新的可行流，其流量比原來的可行流要大，重復(fù)這個(gè)過程，直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流。沿著這條鏈從vs到vt輸送流，還有潛力可挖，只需按照調(diào)整方法，就可以把流量提高，調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，即仍為可行流?？稍鰪V鏈的實(shí)際意義求解最大流的標(biāo)號(hào)算法：b)

接著檢查與相鄰接的點(diǎn)已飽和，流量不可再增。再檢查，可調(diào)整量為4-2=2，可提供量+∞，取調(diào)整量先給標(biāo)號(hào)（?，+∞）1）尋找可增廣鏈：同理，給標(biāo)號(hào)

下對(duì)已標(biāo)號(hào)點(diǎn)（可望調(diào)整點(diǎn)）接著向下檢查。已飽和。再檢查與相鄰接且未標(biāo)號(hào)的點(diǎn)給標(biāo)號(hào)，其中表示的所調(diào)整量2來自，且為正向流（向前流）。調(diào)整量為給標(biāo)號(hào)為可令調(diào)整量為給標(biāo)號(hào)為表示可控量，反方向流量。d)檢查與相鄰接且未標(biāo)號(hào)的點(diǎn)，。而對(duì)來講是流入，現(xiàn)欲增加流出量，應(yīng)該壓縮的流入量，只要的流入量f)下面檢查與相鄰接且未標(biāo)號(hào)的點(diǎn)，同理，調(diào)整量：給標(biāo)號(hào)為g)最后，給標(biāo)號(hào)2）調(diào)整流量：從到所畫出的紅線即為可增廣鏈。沿該可增廣鏈，從倒推，標(biāo)“＋”號(hào)的在實(shí)際流量上加上該調(diào)整量，標(biāo)“－”符號(hào)的在實(shí)際流量上減去該調(diào)整量。完成調(diào)整過程。反向追蹤當(dāng)標(biāo)到時(shí)，與，相鄰接的點(diǎn)，，都不滿足標(biāo)號(hào)條件，標(biāo)號(hào)無法繼續(xù)，且沒有完成標(biāo)號(hào)。此時(shí)最大流量即為所求。重新開始標(biāo)號(hào)，尋找可增廣鏈。

網(wǎng)絡(luò)從發(fā)點(diǎn)到收點(diǎn)的各通路中，由容量決定其通過能力，最小割則是這此路中的咽喉部分，或者叫瓶頸，其容量最小，它決定了整個(gè)網(wǎng)絡(luò)的最大通過能力。要提高整個(gè)網(wǎng)絡(luò)的運(yùn)輸能力，必須首先改造這個(gè)咽喉部份的通過能力。最小割的意義

如果我們把圖看做輸油管道網(wǎng)，為起點(diǎn)，為終點(diǎn)，為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問應(yīng)該如何安排各管道輸油量，才能使從到的總輸油量最大？

解決問題vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)(vs,2)(-v2,2)(v1,1)(-v3,1)(v4,1)vsv1v3vtv2v48(8)7(6)9(5)9(9)5(5)6(0)2(0)5(3)10(9)(vs,1)(-v2,1)(v1,2)KKW=f*s1+f*s2=8+6=14下圖中，A,B,C,D,E,F分別表示陸地和島嶼，①，②，…，表示橋梁及其編號(hào)。若河兩岸分別為互為敵對(duì)的雙方部隊(duì)占領(lǐng)，問至少應(yīng)切斷幾座橋梁（具體指出編號(hào)）才能達(dá)到阻止對(duì)方部隊(duì)過河的目的。試用圖論方法進(jìn)行分析。14ABCDEF8911101314127123456最大流問題應(yīng)用舉例在圖中任給可行流，用標(biāo)號(hào)法尋找網(wǎng)絡(luò)最大流！弧容量：兩點(diǎn)間的橋梁數(shù)。ABCDFE122211221122ABCDEF8911101314127123456轉(zhuǎn)化為求網(wǎng)絡(luò)最小割設(shè)容量網(wǎng)絡(luò)G有若干發(fā)點(diǎn)，若干個(gè)點(diǎn)，可以添加兩個(gè)新點(diǎn)vs，vt，用容量為∞的有向邊分別連結(jié)vs與發(fā)點(diǎn)，收點(diǎn)與vt，得到新的網(wǎng)絡(luò)G'，G'為只有一個(gè)發(fā)點(diǎn)，一個(gè)收點(diǎn)的網(wǎng)絡(luò)，求解G'的最大流問題即可得到G的解。多發(fā)點(diǎn)多收點(diǎn)網(wǎng)絡(luò)的最大流問題最大流問題應(yīng)用舉例設(shè)有5位待業(yè)者，5項(xiàng)工作，他們各自能勝任工作的情況如圖所示，要求設(shè)計(jì)一個(gè)就業(yè)方案，使盡量多的人能就業(yè)。其中表示工人。表示工作。最大匹配問題圖中最大匹配問題，可以轉(zhuǎn)化為最大流問題求解。在圖中增加兩個(gè)新點(diǎn)分別作為發(fā)點(diǎn)，收點(diǎn)。并用有向邊把它們與原圖中頂點(diǎn)相連，令全部邊上的容量均