,第四節(jié)網(wǎng)絡(luò)最大流問(wèn)題,本節(jié)內(nèi)容的安排,1.應(yīng)用背景在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問(wèn)題。例如鐵路運(yùn)輸系統(tǒng)中的車(chē)輛流，城市給排水系統(tǒng)的水流問(wèn)題,控制系統(tǒng)中的信息流問(wèn)題，常見(jiàn)的人流，物流，水流，氣流，電流，現(xiàn)金流等。在一定條件下,求解給定系統(tǒng)的最大流量,就是網(wǎng)絡(luò)最大流問(wèn)題.網(wǎng)絡(luò)系統(tǒng)最大流問(wèn)題是圖與網(wǎng)絡(luò)理論中十分重要的最優(yōu)化問(wèn)題，它對(duì)于解決生產(chǎn)實(shí)際問(wèn)題起著十分重要的作用。,一引言,2.問(wèn)題描述連通網(wǎng)絡(luò)G(V,A)中有m個(gè)節(jié)點(diǎn),n條弧,弧eij上的流量上界為cij,求從起始節(jié)點(diǎn)vs到終點(diǎn)vt的最大流量的問(wèn)題就是最大流問(wèn)題。,3.引例連接某產(chǎn)品產(chǎn)地v1和銷(xiāo)地v6的交通網(wǎng)如下：,弧（vi，vj）：從vi到vj的運(yùn)輸線，弧旁數(shù)字：這條運(yùn)輸線的最大通過(guò)能力容量。,制定一個(gè)運(yùn)輸方案，使從v1運(yùn)到v6的產(chǎn)品數(shù)量最多。,弧旁數(shù)字：運(yùn)輸數(shù)量流量。,問(wèn)題：這個(gè)運(yùn)輸網(wǎng)絡(luò)中，從v1到v6的最大輸送量是多少？,1、網(wǎng)絡(luò)與流設(shè)一個(gè)賦權(quán)有向圖D=（V,A）,在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)?。╲i,vj）A,都有一個(gè)非負(fù)數(shù)cij,叫做弧的容量。我們把這樣的圖D叫做一個(gè)容量網(wǎng)絡(luò)，簡(jiǎn)稱網(wǎng)絡(luò)，記做D=（V，A，C）?；〉娜萘浚菏菍?duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通過(guò)能力，記為c(vi,vj)或簡(jiǎn)寫(xiě)為cij。,二、基本概念,對(duì)有多個(gè)發(fā)點(diǎn)和多個(gè)收點(diǎn)的網(wǎng)絡(luò),可以另外虛設(shè)一個(gè)總發(fā)點(diǎn)和一個(gè)總收點(diǎn),并將其分別與各發(fā)點(diǎn)、收點(diǎn)連起來(lái)（見(jiàn)圖），就可以轉(zhuǎn)換為只含一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)。,所以一般只研究具有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò),流：加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量f(vi,vj)：加在弧(vi,vj)上的負(fù)載量簡(jiǎn)記為fij，為非負(fù)數(shù)網(wǎng)絡(luò)上的流：是指定義在弧集合上的一個(gè)函數(shù)f=f(vi,vj),其中f(vi,vj)稱為?。╲i,vj)上的流量，流也可看作一個(gè)雙下標(biāo)變量,弧的流量f(vi,vj)：表示弧(vi,vj)上每單位時(shí)間內(nèi)的實(shí)際通過(guò)能力弧的容量c(vi,vj)：表示弧（vi,vj)上每單位時(shí)間內(nèi)的最大通過(guò)能力零流：網(wǎng)絡(luò)上所有的fij=0,圖10-24表示的就是這個(gè)網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案），每一個(gè)弧上的流量fij就是運(yùn)輸量。例如：f12=1,f13=2,f24=3等等。,對(duì)于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流，有幾個(gè)顯著的特點(diǎn)：(1)發(fā)點(diǎn)的凈流出量和收點(diǎn)的凈流入量必相等。(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零。(3)每一個(gè)弧上的流量不能超過(guò)它的最大通過(guò)能力（即容量）,稱滿足下列條件的流為可行流：（1）容量限制條件：對(duì)于每一個(gè)?。╲i,vj）A有0f(vi,vj)c(vi,vj)（簡(jiǎn)記為0fijcij）,2、可行流與最大流,（2）平衡條件：,對(duì)于發(fā)點(diǎn)vs，有,對(duì)于收點(diǎn)vt，有,式子中V(f)稱為可行流f的流量,即發(fā)點(diǎn)的凈輸出量（或收點(diǎn)的凈輸入量）。,對(duì)于中間點(diǎn):流入量=流出量。即對(duì)每個(gè)i(is,t)有f(vi,vj)-f(vj,vi)=0(is，t)(簡(jiǎn)記為fij-fji=0(is，t),即總流量=發(fā)點(diǎn)的凈輸出量=收點(diǎn)的凈輸入量容量網(wǎng)絡(luò)的可行流總是存在的，如當(dāng)所有弧的流均取零，即對(duì)所有的i,j,有f(vi,vj)=0就是一個(gè)可行流,可行流中fijcij的弧叫做飽和弧，fijcij的弧叫做非飽和弧。fij0的弧為非零流弧，fij0的弧叫做零流弧。,圖中為零流弧，都是非飽和弧。,就是要求一個(gè)流fij,使其流量v(f)達(dá)到最大,并且滿足0fijcij,網(wǎng)絡(luò)的最大流:,求網(wǎng)絡(luò)的最大流，即是指滿足容量限制條件和平衡條件的條件下，使v(f)值達(dá)到最大.,容量網(wǎng)絡(luò)D，若為網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向?yàn)閺膙s到vt，上的弧分為兩類(lèi)：凡與方向相同的稱為前向弧，凡與方向相反的稱為后向弧，其集合分別用+和-表示。,鏈的方向：若是聯(lián)結(jié)vs和vt的一條鏈，定義鏈的方向是從vs到vt。,3、增廣鏈,增廣鏈：f是一個(gè)可行流，如果滿足：,即中的每一條弧都是非飽和弧,即中的每一條弧都是非零流弧,則稱為從vs到vt的關(guān)于f的一條增廣鏈。,=(v1,v2,v3,v4,v5,v6),+=(v1,v2),(v2,v3),(v3,v4),(v5,v6),-=(v5,v4),是一個(gè)增廣鏈,顯然圖中增廣鏈不止一條,4、截集與截量,容量網(wǎng)絡(luò)D=（V，A，C），vs為始點(diǎn)，vt為終點(diǎn)。如果把V分成兩個(gè)非空集合使，則所有始點(diǎn)屬于V1，而終點(diǎn)屬于的弧的集合稱為是分離vs和vt的截集（或割）,1=(v4,v5,v6),1=(v4,v5,v6),截集為黃色弧集：,截集中所有弧的容量之和，稱為這個(gè)截集的容量，記為,，也稱截量，則有：,截量為24,設(shè)，,則截集為,截量為20,截集與可行流無(wú)關(guān)，而只與網(wǎng)絡(luò)本身有關(guān)最小截量是個(gè)定值,對(duì)應(yīng)的截量也不相同，其中截量最小的截集稱為最小截集。,設(shè)f為網(wǎng)絡(luò)D=（V，A，C）的任一可行流，流量為v(f)，,為任一截集，則有,結(jié)論1：,即任何一個(gè)可行流的流量都不會(huì)超過(guò)任一截集的容量,若對(duì)割和割用表示割中所有方向的弧的流量的總和，表示割中所有方向的弧的流量的總和，則，割的流量有,由此式可知，當(dāng)某一流量等于某一截量，即：,即所有的v(f)v(f)，,v(f)一定是D上的最大流，而,一定是D的最小截集的截量。,滿足條件,那么f*一定是D上的最大流，而,如果網(wǎng)絡(luò)上的一個(gè)可行流f*,和網(wǎng)絡(luò)中的一個(gè)截集,一定是D的最小截集。,結(jié)論2：,當(dāng)f有增廣鏈存在時(shí)，找出,證明：,定理8：可行流f是D的最大流的充分必要條件是不存在從vs到vt的關(guān)于f的一條增廣鏈。,先證f是D的最大流時(shí)，則D中一定沒(méi)有增廣鏈，用反證法,非增廣鏈上的弧,顯然f仍是一個(gè)可行流，(因滿足容量限制條件和平衡條件）但和原來(lái)的可行流f比較，這時(shí)網(wǎng)絡(luò)中從st的流量增大了一個(gè)值（0）.因此：當(dāng)f有增廣鏈時(shí)，f不是最大流，即f是最大流時(shí)，f就一定沒(méi)有增廣鏈,下面證明當(dāng)f沒(méi)有增廣鏈時(shí)，f一定是最大流,證明：若網(wǎng)絡(luò)中沒(méi)有增廣鏈，則對(duì)它構(gòu)造一個(gè)點(diǎn)的集合V*，定義(1)sV*(2)若iV*和f(i,j)0,則jV*(3)若iV*和f(i,j)=c(i,j),則jV*若iV*和f(j,i)=0,則jV*顯然,否則將存在st的增廣鏈，與假設(shè)矛盾.,由此為該網(wǎng)絡(luò)的一個(gè)割，該割的容量為,由上面定義，通過(guò)這個(gè)割的流有：,由結(jié)論2，f一定是最大流。,在網(wǎng)絡(luò)中st的最大流量等于它的最小割集的容量，即,最大流最小截量定理：,由上面證明可得,最小截集的容量,最大流的流量,網(wǎng)絡(luò)中可行流的流量,網(wǎng)絡(luò),割所含弧的流量和,割所含弧的容量和,弧的流量,f(vi,vj),弧的容量,c(vi,vj),弧(vi,vj),滿足條件,那么f*一定是D上的最大流，而,如果網(wǎng)絡(luò)上的一個(gè)可行流f*,和網(wǎng)絡(luò)中的一個(gè)截集,一定是D的最小截集。,結(jié)論2：,結(jié)論1：,即任何一個(gè)可行流的流量都不會(huì)超過(guò)任一截集的容量,總結(jié)：對(duì)最大流問(wèn)題有下列結(jié)論和定理：,定理8可行流f*fij*是最大流，當(dāng)且僅當(dāng)D中不存在關(guān)于f*的增廣鏈。,定理9（最大流最小截定理）任一網(wǎng)絡(luò)中，從st的最大流的流量等于它的最小截集的截量。,定理8為我們提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法。亦即，如果網(wǎng)絡(luò)D中有一個(gè)可行流f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f的增廣鏈。如果沒(méi)有增廣鏈，那么f一定是最大流。如有增廣鏈，那么可以按照定理8中必要性，不斷改進(jìn)和增大可行流f的流量，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。,這種算法由Ford和Fulkerson于1956年提出,故又稱FordFulkerson標(biāo)號(hào)法；實(shí)質(zhì)：判斷是否存在增廣鏈,并設(shè)法把增廣鏈找出來(lái),并予以調(diào)整,最終使圖中無(wú)增廣鏈.,二尋求最大流的標(biāo)號(hào)法,此算法從網(wǎng)絡(luò)中的一個(gè)可行流f出發(fā)（如果D中沒(méi)有f，可以令f是零流），運(yùn)用標(biāo)號(hào)法，經(jīng)過(guò)標(biāo)號(hào)過(guò)程和調(diào)整過(guò)程，最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。下面用給頂點(diǎn)標(biāo)號(hào)的方法來(lái)定義定理8中的V1*.在標(biāo)號(hào)過(guò)程中，有標(biāo)號(hào)的頂點(diǎn)是V1*中的點(diǎn)，沒(méi)有標(biāo)號(hào)的點(diǎn)不是V1*中的點(diǎn)。如果vt有了標(biāo)號(hào)，表示存在一條關(guān)于f的增廣鏈。如果標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，并且vt未被標(biāo)號(hào)，則表示不存在關(guān)于f的增廣鏈。此時(shí)，就得到了網(wǎng)絡(luò)中的一個(gè)最大流和最小截集。,在標(biāo)號(hào)過(guò)程中，網(wǎng)絡(luò)中的點(diǎn)分為兩種：已標(biāo)號(hào)的點(diǎn)（分為已檢查和未檢查）和未標(biāo)號(hào)的點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的，以便找出增廣鏈。第二個(gè)標(biāo)號(hào)是從上一個(gè)標(biāo)號(hào)點(diǎn)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值，是為了用來(lái)確定增廣鏈上的調(diào)整量。標(biāo)號(hào)過(guò)程開(kāi)始，先給vs標(biāo)號(hào)（0，+）。這時(shí)，vs是標(biāo)號(hào)未檢查的點(diǎn)，其它都是未標(biāo)號(hào)點(diǎn)。一般地，取一個(gè)標(biāo)號(hào)未檢查點(diǎn)vi，對(duì)一切未標(biāo)號(hào)點(diǎn)vj,1標(biāo)號(hào)過(guò)程,例14求圖10-25的網(wǎng)絡(luò)最大流，弧旁的權(quán)數(shù)表示（cij,fij）。,解：1.標(biāo)號(hào)過(guò)程。1）首先給vs標(biāo)號(hào)（0，+）2）看vs:在弧(vs,v2)上,fs2=cs3=3,不具備標(biāo)號(hào)條件。在弧(vs,v1)上,fs1=10,故給v2標(biāo)號(hào)（-v1,l(v2)）,其中l(wèi)(v2)=minl(v1),f21=min4,1=1.v2標(biāo)號(hào)（-v1,1），此時(shí)v1為已檢查的標(biāo)號(hào)點(diǎn),(vs,4),(0,+),(v1,1),(0,+),(vs,4),(v1,1),(v2,1),(-v2,1),(v3,1),（4）看v2:在弧（v2,v4）上，f24=30,故給v3標(biāo)號(hào)（-v2，l(v3),其中l(wèi)(l(v3)=minl(v2),f32=min1,1=1。（5）在v3,v4中任意選一個(gè)，比如v3,在?。╲3,vt）上，f3t=1c3t=2,故給vt標(biāo)號(hào)(v3,l(vt),其中l(wèi)(vt)=minl(v3),(c3t-f3t)=min1,1=1.因?yàn)関t被標(biāo)上號(hào)，根據(jù)標(biāo)號(hào)法，轉(zhuǎn)入調(diào)整過(guò)程。,（1）如果在前向?。╲i,vj）上，有fij0,那么給vj標(biāo)號(hào)（-vi,l(vj)）.其中l(wèi)(vj)=minl(vi),fji.這時(shí)，vj成為標(biāo)號(hào)未檢查點(diǎn)。于是vi成為標(biāo)號(hào)已檢查的點(diǎn)。重復(fù)以上步驟，如果所有的標(biāo)號(hào)都已經(jīng)檢查過(guò)，而標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，則標(biāo)號(hào)法結(jié)束。這時(shí)的可行流就是最大流。,但是，如果vt被標(biāo)上號(hào)，表示得到一條增廣鏈，轉(zhuǎn)入下一步調(diào)整過(guò)程。,總結(jié)標(biāo)號(hào)過(guò)程,2.調(diào)整過(guò)程利用反向追蹤找增廣鏈，調(diào)整增廣鏈的流量，去掉舊的標(biāo)號(hào)，對(duì)新的可行流重新進(jìn)行標(biāo)號(hào)。具體做法如下：（1）按照vt和其它已檢查的標(biāo)號(hào)點(diǎn)的第一個(gè)標(biāo)號(hào)，反向追蹤，找出增廣鏈，確定調(diào)整量。（2),得新的可行流。(3)再去掉所有的標(biāo)號(hào)，對(duì)新的可行流f=fij,重新進(jìn)行標(biāo)號(hào)過(guò)程，直到找到網(wǎng)絡(luò)D的最大流為止。,非增廣鏈上的弧,(5,2),(1,0),(1,0),(2,2),(cij,fij),增廣鏈的調(diào)整量為1，則有：,調(diào)整后的可行流f*如圖,再對(duì)這個(gè)可行流從新進(jìn)行標(biāo)號(hào)過(guò)程，尋找增廣鏈。一直到標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，不存在從vS到vt的增廣鏈，算法結(jié)束。,(0,+),(vs,3),最大流的流量v(f*)=fs1+fs2=5.最小截集它的容量也為5.,得到的截集為最小截集（V1，），其中V1是標(biāo)號(hào)的集合，是未標(biāo)號(hào)的集合。,此時(shí)，網(wǎng)絡(luò)中的可行流f*即是最大流，,(0,),(s,2),(-v2,2),(v1,2),(-v3,1),(v4,1),例:用標(biāo)號(hào)法求下圖中st的最大流量,并找出該網(wǎng)絡(luò)的最小割.,(v2)=min(s),(cs2-fs2)=2(v1)=min(v2),f12=min2,4=2(v3)=min(v1),(c13-f13)=min2,5=2(v4)=min(v3),f43=min2,1=1(t)=min(v4),(c4t-f4t)=min1,2=1,V*(f)=,s,v2,v4,v3,v1,t,7(6),8(8),9(5),5(3),2(0),9(9),6(0),10(9),5(5),(-v2,1),(0,),(v1,1),(s,1),(0+,),(s+,6),(2,6),(3+,1),(4+,1),(0+,),(s+,5),(2+,2),(5,2),(4+,2),例：,(0+,),(s+,3),(2,3),最小截集,最大流的流量為：14+12+5+4=35,例：求下圖所示網(wǎng)絡(luò)的最大流,解：給定初始可行流為全零流，即f（0）=0,給vs標(biāo)號(hào)（0，+），檢查vs：給v1標(biāo)號(hào)(vs,4),給v2標(biāo)號(hào)(vs,3),給v3標(biāo)號(hào)(vs,10),(0,+),(vs,4),(vs,3),(vs,10),檢查v1：給v4標(biāo)號(hào)(v1,1)，檢查完畢；,(v1,1),檢查v2：給v5標(biāo)號(hào)(v2,3)，檢查完畢；,(v2,3),檢查v5：給vt標(biāo)號(hào)(v5,3)，檢查完畢；,(v5,3),因?yàn)榻K點(diǎn)vt已標(biāo)號(hào)，故找出一條從vs到vt的增廣鏈：vsv2v5vt.取=3,(vs,4),(v1,3),(vs,10),(v1,1),(v2,2),(0,+),(v5,2),(vs,2),(v3,3),(vs,10),(v2,3),(v3,4),(0,+),(v4,3),(0,+),(vs,2),(vs,7),(v3,4),(v5,2),(v5,3),(0,+),(vs,2),(vs,4),(v1,