網(wǎng)絡(luò)流算法專題ppt課件-展示頁
2025-05-21 13:11本頁面
【正文】 i := n。 if last[n] = 0 then break。 {反向弧 } check[i] := true。 {找到一個(gè)已檢查而未標(biāo)號(hào)的點(diǎn) } if i n then break。 repeat i := 0。 fillchar(check, sizeof(check), false)。 {可改進(jìn)路中的前趨 } check : array[0 .. maxn] of boolean。 {最大流 } var i, j, delta, x : integer。如果所有弧的容量為整數(shù)，則最多需要 v(其中 v為最大流 )次增廣，因此總的計(jì)算量為 O(mv)。 ? 第 4步 (構(gòu)造最小割 )，這時(shí)現(xiàn)行流是最大的，若把所有標(biāo)號(hào)的集合記為 S，所有未標(biāo)號(hào)點(diǎn)的集合記為 T,便得到最小割 (S,T)。 ? 第 2步 (找增廣路 )，如果所有標(biāo)號(hào)都已經(jīng)被檢查，轉(zhuǎn)到第 4步。 最大流等于最小割，即 max V(f) = min C(U, W)。 如果網(wǎng)絡(luò)中所有的弧的容量是整數(shù)，則存在整數(shù)值的最大流。 ? 定理 2：可行流 f是最大流的充分必要條件是： f中不存在可改進(jìn)路。 ? 對(duì)于弧尾在 U，弧頭在 W的弧所構(gòu)成的集合稱之為 割切 ，用（ U， W）表示。 剩余圖 (殘余網(wǎng)絡(luò) ) ? 剩余圖 G’=(V,E’) ? 流量網(wǎng)絡(luò) G=(V,E)中，對(duì)于任意一條邊 (a,b)，若 ? flow(a,b)capacity(a,b) or flow(b,a)0 ? 則 (a,b)∈ E’ 可以沿著 ab方向增廣 ?剩余圖中，從源點(diǎn)到匯點(diǎn)的每一條路徑都對(duì)應(yīng)一條增廣路 Capacity=5 Capacity=6 Capacity=2 Flow=2 Flow=2 Flow=2 有向圖 3 2 2 2 4 剩余圖 ?剩余圖中，每條邊都可以沿其方向增廣 剩余圖的權(quán)值代表能沿邊 增廣的大小 ? G = (V, E, C)是已知的網(wǎng)絡(luò)流圖，設(shè) U是 V的一個(gè)子集，W = V\U，滿足 S ∈ U ， T∈W 。 ? 譬如在圖中， P = (S, V1, V2, V3, V4, T)，那么 P+ = {S, V1, V1, V2, V2, V3, V4, T} P = {V4, V3} ? 給定一個(gè)可行流 f， P是從 S到 T的一條道路，如果滿足： fij是非飽和流，并且 i,j∈ P+ , f ij是非零流，并且i,j∈ P 那么就稱 P是 f的一條 可增廣路 。 ? 定義一條道路 P，起點(diǎn)是 S、終點(diǎn)是 T。若 fij = Cij，稱 vi, vj為飽和?。环駝t稱 vi, vj為非飽和弧。 1. 每一條弧 (i,j)有 fij≤C ij 2. 流量平衡 除源點(diǎn) S和匯點(diǎn) T以外的所有的點(diǎn) vi，恒有： ∑ j(fij)= ∑ k(fjk) 該等式說明中間點(diǎn) vi的流量守恒，輸入與輸出量相等。邊 (vi, vj)的容量用 cij表示。 2. 有且僅有一個(gè)頂點(diǎn) T，它的出度為零，即 d+(T) = 0，這個(gè)頂點(diǎn) T便稱為匯點(diǎn)，或稱為收點(diǎn)。為了解答此題，我們先了解網(wǎng)絡(luò)流的有關(guān)定義和概念。 ? 每條弧代表一條公路，弧上的數(shù)表示該公路的最大運(yùn)載量。圖論算法 最大流問題 長(zhǎng)沙市雅禮中學(xué) 朱 全 民 運(yùn)輸網(wǎng)絡(luò) ? 現(xiàn)在想將一些物資從 S運(yùn)抵 T，必須經(jīng)過一些中轉(zhuǎn)站。連接中轉(zhuǎn)站的是公路，每條公路都有最大運(yùn)載量。最多能將多少貨物從 S運(yùn)抵 T？ 4 2 4 8 4 7 3 6 2 1 S T V1 V2 V3 V4 公路運(yùn)輸圖 基本概念 ? 這是一個(gè)典型的網(wǎng)絡(luò)流模型。 ? 若有向圖 G=(V,E)滿足下列條件： 1. 有且僅有一個(gè)頂點(diǎn) S，它的入度為零，即 d(S) = 0，這個(gè)頂點(diǎn) S便稱為源點(diǎn)，或稱為發(fā)點(diǎn)。 3. 每一條弧都有非負(fù)數(shù)，叫做該邊的容量。 ? 則稱之為網(wǎng)絡(luò)流圖，記為 G = (V, E, C) 可行流 可行流 對(duì)于網(wǎng)絡(luò)流圖 G，每一條弧 (i,j)都給定一個(gè)非負(fù)數(shù) fij，這一組數(shù)滿足下列三條件時(shí)稱為這網(wǎng)絡(luò)的可行流，用 f表示它。 3. 對(duì)于源點(diǎn) S和匯點(diǎn) T有 ， ∑ i(fSi)= ∑ j(fjT)= V(f) 可增廣路 ? 給定一個(gè)可行流 f={fij}。若 fij = 0，稱 vi, vj為零流弧；否則稱 vi, vj為非零流弧。把 P上所有與 P方向一致的弧定義為正向弧，正向弧的全體記為 P+；把 P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為 P。之所以稱作“可增廣”，是因?yàn)榭筛倪M(jìn)路上弧的流量通過一定的規(guī)則修改，可以令整個(gè)流量放大。即 U、 W把 V分成兩個(gè)不相交的集合，且源點(diǎn)和匯點(diǎn)分屬不同的集合。把割切（ U， W）中所有弧的容量之和叫做此割切的容量，記為 C（ U， W），即： 割切 ????WjUiijcWUC ),(割切示例 ? 上例中，令 U = {S, V1}，則 W = {V2, V3, V4, T}，那么， ? C(U, W) = S, V2 + V1, V2 + V1, V3+V1, V4 =8+4+4+1=17 流量算法的基本理論 ? 定理 1：對(duì)于已知的網(wǎng)絡(luò)流圖，設(shè)任意一可行流為 f，任意一割切為 (U, W)，必有： V(f) ≤ C(U, W) 。 ? 定理 3：整流定理。 ? 定理 4：最大流最小割定理。 最大流算法 ? 第 1步，令 x=(xij)是任意整數(shù)可行流，可能是零流，給 s一個(gè)永久標(biāo)號(hào) (, ∞) 。 找到一個(gè)標(biāo)號(hào)但未檢查的點(diǎn) i, 并做如下檢查， ? 對(duì)每一個(gè)弧 (i,j),如果 xijCij, 且 j未標(biāo)號(hào) ,則給 j一個(gè)標(biāo)號(hào) (+i, δ (j) ),其中， δ (j)=min{Cijxij , δ (i) } ? 對(duì)每一個(gè)弧 (j, i),如果 xji0,且 j未標(biāo)號(hào)，則給 j一個(gè)標(biāo)號(hào) (i, δ (j) ),其中， δ (j)=min{xji , δ (i) } ? 第 3步 (增廣 )，由點(diǎn) t開始，使用指示標(biāo)號(hào)構(gòu)造一個(gè)增廣路 ,指示標(biāo)號(hào)的正負(fù)則表示通過增加還是減少弧流量來增加還是減少弧流量來增大流量，抹去 s點(diǎn)以外的所有標(biāo)號(hào)，轉(zhuǎn)第二步繼續(xù)找增廣軌。 實(shí)例 復(fù)雜度分析 ? 設(shè)圖中弧數(shù)為 m,每找一條增廣軌最多需要進(jìn)行 2m次弧的檢查。 procedure maxflow。 last : tline。 {檢查數(shù)組 } begin repeat fillchar(last, sizeof(last), 0)。 last[1] := maxint。 repeat inc(i) until (i n) or (last[i] 0) and not check[i]。 for j := 1 to n do if last[j] = 0 then if flow[i, j] limit[i, j] then last[j] := i {正向弧 } else if flow[j, i] 0 then last[j] := i。 until last[n] 0。 delta := maxint。 repeat
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1