03年02月10日容量有上下界的最大流網(wǎng)絡(luò)

1、 網(wǎng)絡(luò)流求網(wǎng)絡(luò)最大流V1V2V4V6V5V38244476921 網(wǎng)絡(luò)與流 網(wǎng)絡(luò)D(V,A,C) 設(shè)D是一個簡單有向圖(D=(V,A)。在V中指定了一個頂點，稱為源點(記為Vs)和另一個頂點，稱為匯點(記為Vt)，對于每一條弧(Vi，Vj)A，對應(yīng)有一個Cij=0，稱為弧的容量。通常我們就把這樣的D叫做一個網(wǎng)絡(luò)，記作D=(V,A,C)。 網(wǎng)絡(luò)流F 所謂網(wǎng)絡(luò)上的流是指定義在弧集合A上的一個函數(shù)FFij，并稱Fij為弧(Vi,Vj)上的流量。 函數(shù)FFij（ 且 ）：F12=3, F13=2, F23=2, F24=0, F25=1, F34=2, F35=2, F54=0, F56=3, F46

2、=28244476921V1V2V4V6V5V31222220033V1V2V4V6V5V3222P1: V1 V3 V4 V68244476921V1V2V4V6V5V3P2: V1 V2 V3 V5 V622228244476921V1V2V4V6V5V31118244476921P3: V1 V2 V5 V6V1V2V4V6V5V3P2: V1 V2 V3 V5 V61=12=282444769212=22=22=22=22=2002+1=3P3: V1 V2 V5 V6P1: V1 V3 V4 V62=22+1=3V1V2V4V6V5V31222220033可行流與最大流 可行流(可行

3、流的流量V(F)滿足下述條件的流F稱為可行流：(1)容量限制條件：對每一條弧(Vi，Vj) A，0=Fij=Cij (2)平衡條件：對于中間點： 流出量流入量,即對每個i(is,t)有Vi的流出量 -Vi的流入量=0對于源點S：Vs的流出量 -Vs的流入量=源點的凈輸出量對于匯點T：Vt的流出量 -Vt的流入量=(-1)*匯點的凈輸入量 若給一個可行流F(Fij)飽和弧：網(wǎng)絡(luò)中Fij =Cij的弧非飽和?。壕W(wǎng)絡(luò)中Fij Cij的弧非零流?。壕W(wǎng)絡(luò)中 Fij0 的弧零流弧：網(wǎng)絡(luò)中 Fij =0的弧 若P是網(wǎng)絡(luò)中聯(lián)結(jié)源點Vs和匯點Vt的一條路，我們定義路的方向是從Vs到Vt，則路上的弧被分成兩類：一

4、類是弧的方向與路的方向一致，叫做前向弧。前向弧的全體記為P+。另一類弧與路的方向相反，叫做后向弧。后向弧的全體記為P-。 如圖，在路PVl,V3,V2,V4,V6中 P+(Vl,V3)，(V2,V4)，(V4,V6) P -(V3,V2)V1V2V4V6V5V38244476921 在圖G中，一個由不同的邊組成的序列e1,e2,eg，如果ei是連接Vi-1與Vi(i1,2,g)的，我們就稱這個序列為從V0到Vg的一條道路，數(shù)g稱為路長，V0與Vg稱為這條道路的兩個端點，Vi(1=i=g-1)叫做道路的內(nèi)點。對于 且 是邊嗎？ 可改進路P的定義： 設(shè)F是一個可行流，P是從Vs到Vt的一條路，若P

5、滿足下列條件： (1)在P的所有前向弧(Vi,Vj)上，0=FijCij，即P+中的每一條弧是非飽和孤； (2)在P的所有后向弧(Vi,Vj)上，0 Fij= Cij ，即P-中的每一條弧是非零流弧。 (1)不屬于可改進路P的弧(Vi,Vj)上的流量一概不變，即F1ijFij (2)可改進路P上的所有弧(Vi,Vj)上的流量按下述規(guī)則變化； 在前向弧(Vi,Vj)上，F(xiàn)1ijFij+a 在后向弧(Vi,Vj)上， F1ijFij-a a稱為可改進量，它應(yīng)該按照下述原則確定：a既要取得盡量大，又要使變化后的Fij仍滿足可行流的兩個條件容量限制條件和平衡條件。不難看出，按照這個原則,a即不能超過每

6、條前向弧的Cij-Fij，也不能超過每條后向弧的Fij。因此a應(yīng)該等于前向弧上的Cij-Fij與后向弧上的Fij的最小值。V1V2V4V6V5V31222220033P: V1 V3 V2 V4 V6P+(Vl,V3)，(V2,V4)，(V4,V6)P -(V3,V2)C13-F138-2=6C24-F244-0=4C46-F467-2=5F3228244476921V1V2V4V6V5V312+2=42-2=0222+2=40+2=2033改進后的F重要結(jié)論：設(shè)F是網(wǎng)絡(luò)D的一個流，如果不存在從Vs到Vt關(guān)于F的可改進路P，那么F一定是最大流。求最大流的基本思路： 1標號過程 在這個過程，網(wǎng)絡(luò)

7、中的頂點或者是標號點(又分為已檢查和未檢查兩種)，或者是未標號點。每個標號點的標號包含兩個部分。第一標號指明它的標號從哪一頂點得到，以便找出可改進路；第二個標號是為確定可改進量a用的。 標號過程開始，總先給Vs標上(0,+)，這時Vs是已標號而未檢查的頂點，其余都是未標號點。一般，取一個標號而未檢查的頂點Vi，對一切未標號點Vj： (1)若在弧(Vi,Vj)上FijCij,則給Vj標號(Vi,L(Vj)。這里L(fēng)(Vj)minL(Vi),Cij-Fij。這時頂點Vj成為標號而未檢查的頂點。 (2)若在弧(Vj ,Vi)上Fij 0，則給Vj 標號(- Vi ,L(Vj),這里L(fēng)(Vj)minL(

8、Vi), Fij。這時頂點Vj 成為標號而未檢查的頂點。 在Vi的全部相鄰頂點都已標號后，Vi成為標號而已檢查過的頂點。重復(fù)上述步驟，一旦Vt被標上號，表明得到一條從Vs到Vt的可改進路P，轉(zhuǎn)入調(diào)整過程。 若所有標號都已檢查過致使標號過程無法繼續(xù)時算法結(jié)束。這時的可行流即最大流。2調(diào)整過程 采用“倒向追蹤”的方法，從Vt開始，利用標號點的第一個標號逐條弧地找出可改進路P，并以Vt 的第二個標號L(Vt)作為改進量a，改進P路上的流量。 重新進入標號過程。V1V2V4V6V5V38244476921(0,+)(1,4)(1,8)(2,4)(2,1)(4,4)8244476921V1V2V4V6V

9、5V3(0,+)(-4,2)(1,8)(3,2)(4,2)444(3,2)8244476921V1V2V4V6V5V3(0,+)(1,6)(5,2)44622(3,2)(5,2)8244476921V1V2V4V6V5V3(0,+)(1,4)4464222const maxn=100;type nodetype=record可改進路頂點類型 l,p:integer;標號、檢查標志 end; arctype=record網(wǎng)頂點類型 c,f:integer;容量、流量 end; gtype=array0.maxn,0.maxn of arctype; ltype=array0.maxn of no

10、detype;var lt:ltype; g:gtype; n,s,t:integer;頂點數(shù)、源點、匯點 f:text;存儲結(jié)構(gòu)Init;輸入圖的矩陣Main;Successford(del)If success then printElse fulkerson(del)successford(var a:integer):boolean lts.ls icheckIf i=0 then exit; For j1 to nIf (ltj.l=0)and(gi,j.c0) or gj,i0) If gi,j.f0 then ltj.l-i;ltp1 ltt.L0逆推求afulkerson( a:integer) mt jmmabs(ltj.L)If ltj.L0 then gm,j.fgj,m.f+a m=sV1V2V4V6V5V34478292練習(xí)一：用標號法編程計算如圖網(wǎng)絡(luò)的最大流。4168244476921V1V2V4V6V5V3444+2=62+2=422212 413 424 434