or教案23_圖論-文庫吧資料
2024-10-13 15:13本頁面
【正文】 t)), 這里 ? ? ? ? ,m i n)fc(),v(lm i n)v(l ttt 111333 ????vt得到標(biāo)號，標(biāo)號過程結(jié)束。 （ 1）給 vs標(biāo)上（ 0， ∞）； v2 v3 v1 vs v4 vt (3， 3) (4， 3) (1， 1) (5， 3) (5， 1) (2， 2) (2， 1) (1， 1) (3,0) （ 0， ∞） ? ? ? ? 415m i nm i n 111 ??????? ,)fc(),v(l)v(l sss在弧（ vs， v2）上， fs2=cs2=3, 不滿足標(biāo)號條件 ?；∨缘臄?shù)字是 ( cij , fij)。ij ),( ),( ),( 去掉所有的標(biāo)號 ,對新的可行流 f ′={ fij′},重新進(jìn)入標(biāo)號過程。被找出的弧構(gòu)成了增廣鏈 181。)。檢查 vk 的第一個(gè)標(biāo)號，若為 i（或 i），則 (vi,vk) ∈ 181。（或?。?vt， vk) ∈ 181。上進(jìn)行流量調(diào)整。 （二）調(diào)整過程 從 vt 開始，反向追蹤，找出增廣鏈 181。 fijcij vi vj (i , l(vj)) l(vj)=min[l(vi),cijfij], f ji0 vi vj (i , l(vj)) l(vj)=min[l(vi),fji] 重復(fù)上述步驟，一旦 vt被標(biāo)號，則得到一條 vs到 vt的增廣鏈。 （ 1）若?。?vi， vj）上， fijcij，則給 vj 標(biāo)號 (i， l(vj))， l(vj)=min[l (vi), cijfij], vj 成為標(biāo)號而未檢查的點(diǎn)。 二、尋求最大流的標(biāo)號法（ Ford— Fulkerson） 從任一個(gè)可行流 f 出發(fā)（若網(wǎng)絡(luò)中沒有給定 f ，則從零流開始），經(jīng)過標(biāo)號過程與調(diào)整過程。 定理 2 最大流最小截定理。 因?yàn)椴淮嬖陉P(guān)于 f *的增廣鏈，故 vt ∈ V1*， 記 V1*=V\ V1*，得截集（ V1*， V1*），顯然有 ????????),vv),vv cfjijiij*ij*1*1*1*1V V(),( 0 V (V),( 所以 V(f *) = C（ V1*， V1*）。 設(shè) D中不存在關(guān)于 f *的增廣鏈，證明 f *是最大流。 證明：若 f *是最大流，設(shè) D中存在關(guān)于 f *的增廣鏈 181。即 )V,C ( VV ( f ) 11?可行流 f *，截集 (V1*， V1*), 若 V( f *)=C( V1*， V1*）， 則 f *必是最大流， (V1*， V1*) 必是 D的最小截集。 S T 定義 4 網(wǎng)絡(luò) D=(V,A,C） ,若點(diǎn)集 V被剖分為兩個(gè)非空集 合 V1和 V1,使 vs∈ V1， vt ∈ V1，則把弧集 (V1， V1) 稱為是分離 vs和 vt的截集。 0 fij ≤ cij 后向弧 是非零流弧， (vi , vj ) ∈ 181。滿 足下列條件 ,稱之為 (關(guān)于可行流 f 的 )一條增廣 鏈。 ={(v5,v4)} v2 v5 v3 v1 v4 v6 定義 3 設(shè) f 是一個(gè)可行流 , 181。
外語相關(guān)推薦
鄂ICP備17016276號-1