《網(wǎng)絡(luò)最大流問題》PPT課件.ppt

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

1、課程講授：黃玉誠運籌學(xué)中國礦業(yè)大學(xué)(北京)第六章圖與網(wǎng)絡(luò)分析第一節(jié)圖的基本知識第二節(jié)樹第三節(jié)最短路問題第四節(jié)網(wǎng)絡(luò)最大流問題第五節(jié)最小費用最大流問題9/20/2021第四節(jié)網(wǎng)絡(luò)最大流問題8431763511v1v2v3v5v4v6105圖10-23是聯(lián)結(jié)某產(chǎn)品產(chǎn)地v1和銷地v6的交通網(wǎng)，每一弧(vi，vj)代表從vi到vj的運輸線，產(chǎn)品經(jīng)這條弧由vi輸送到vj，弧旁的數(shù)字表示這條運輸線的最大通過能力。現(xiàn)在要求制定一個運輸方案使從v1運到v6的產(chǎn)品數(shù)量最多。圖10-239/20/2021③①②②③③②⑥v1v2v3v5v4v6⑤①圖10-24給出了一個運輸方案，每條弧旁的數(shù)字表示每

2、條運輸線上的運輸數(shù)量。這個方案使8個單位的產(chǎn)品從v1運到v6。在這個運輸網(wǎng)絡(luò)中，從v1到v6的最大輸送量是多少呢?8431763511v1v2v3v5v4v6105圖10-23圖10-249/20/2021一、基本概念與基本定理1、網(wǎng)絡(luò)與流定義1給一個有向圖D=(V,A)，在V中指定了一點，稱為發(fā)點(記為vs)，和另一點，稱為收點(記為vt)，其余的點叫中間點。對于每一個弧(vi，vj)∈A,對應(yīng)有一個c(vi，vj)≥0(或簡寫為cij)，稱為弧的容量。通常把這樣的D叫作一個網(wǎng)絡(luò)。記作D=(V，A，C)。對D中的任一弧(vi，vj)有流量f(vi，vj)(有時也簡記作fij)

3、，稱集合f={fij}為網(wǎng)絡(luò)D上的一個流。9/20/20212、可行流與最大流定義2滿足下述條件的流f稱為可行流：1）容量限制條件：對每一弧(vi，vj)∈A0≤fij≤cij可行流2）平衡條件：對于中間點：流出量＝流入量，即對每個i(i≠s,t)有9/20/2021對于發(fā)點vs，式中v(f)稱為這個可行流的流量，即發(fā)點的凈輸出量(或收點的凈輸入量)。于是對于收點vt，或9/20/2021所謂最大流問題就是在網(wǎng)絡(luò)中，尋找流量最大的可行流，即：求一個流{fij}使其流量v(f)達到最大，并且滿足0≤fij≤cij(vi，vj)∈A最大流可行流總是存在的，例如(fij)=0就是一個

4、流量為0的可行流。9/20/20213、增廣鏈若給一個可行流f={fij}，我們把網(wǎng)絡(luò)中使fij=cij的弧稱為飽和弧，使fij0的弧稱為非零流弧。若μ是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點vs和收點vt的一條鏈，我們定義鏈的方向是從vs到vt，則鏈上的弧被分為兩類：一類是弧的方向與鏈的方向一致，叫作前向弧。前向弧的全體記為μ+。另一類弧與鏈的方向相反，稱為后向弧。后向弧的全體記為μ-。9/20/2021定義3設(shè)f是一個可行流，μ是從vs到vt的一條鏈，若μ滿足下列條件,稱之為(關(guān)于可行流f的)一條增廣鏈。在弧(vi，vj)∈μ+上，0≤

5、fij0。9/20/20214、截集與截量設(shè)S,T∈V，S∩T=Φ，我們把始點在S，終點在T中的所有弧構(gòu)成的集合，記為(S，T)。定義4給網(wǎng)絡(luò)D=(V，A，C)，若點集V被剖分為兩個非空集合V1和，使vs∈V1，vt∈，則把弧集(V1,)稱為是(分離vs和vt的)截集。可以看

6、出，從網(wǎng)絡(luò)中去掉任一截集，則從vs到vt便不存在路。所以，截集是從vs到的vt必經(jīng)之路。9/20/2021定義5給一截集(V1,)，把截集(V1,)中所有弧的容量之和稱為這個截集的容量(簡稱為截量)，記為c(V1,)，即任何一個可行流的流量v(f)都不會超過任一截集的容量。即9/20/2021顯然，若對于一個可行流f*，網(wǎng)絡(luò)中有一個截集(V1*,)，使v(f*)=c(V1*,),則f*必是最大流，而(V1*,)必定是D的所有截集中容量最小的一個，即最小截集。9/20/2021定理1可行流f*是最大流的充分必要條件是不存在從vs到vt的(關(guān)于f*)增廣鏈。證明：(一)必要性用反證

7、法?？尚辛鱢*是最大流，假設(shè)存在從vs到的vt的(關(guān)于f*)增廣鏈。令：9/20/2021由增廣鏈的定義，可知θ>0,令網(wǎng)絡(luò)上的另一個流：仍為可行流(即滿足容量限制條件與平衡條件)，但的總流量等于的流量加θ，即這與是最大流的前提矛盾。9/20/2021(二)充分性：若不存在關(guān)于f*增廣鏈，那么f*是最大流。因為不存在關(guān)于f*增廣鏈，那么在這種定義下，。令：則。因此，可以得到一個截集。令：若且則令若且則令用下面方法定義點集9/20/2021顯然有那么，可行流f*上的流量則f*必然是最大流。9/