or教案23_圖論(編輯修改稿)
2025-10-27 15:13 本頁面
【文章內(nèi)容簡介】 所以 V(f *) = C（ V1*， V1*）。于是 f *必是最大流。 定理 2 最大流最小截定理。任一個網(wǎng)絡(luò) D中，從 vs 到 vt 的最大流的流量等于分離 vs， vt 的最小截集 的容量。 二、尋求最大流的標(biāo)號法（ Ford— Fulkerson） 從任一個可行流 f 出發(fā)（若網(wǎng)絡(luò)中沒有給定 f ，則從零流開始），經(jīng)過標(biāo)號過程與調(diào)整過程。 （一）標(biāo)號過程 ????????未標(biāo)號點未檢查已檢查標(biāo)號點網(wǎng)絡(luò)中的點標(biāo)號：（前點標(biāo)記，前點到該點的弧流量可調(diào)整量） 開始， vs 標(biāo)上（ 0， ∞）， vs 是標(biāo)號未檢查的點，其余點都是未標(biāo)號點，一般地，取一個標(biāo)號未檢查的點 vi ，對一切未標(biāo)號的點 vj 。 （ 1）若?。?vi， vj）上， fijcij，則給 vj 標(biāo)號 (i， l(vj))， l(vj)=min[l (vi), cijfij], vj 成為標(biāo)號而未檢查的點。 （ 2）若?。?vj， vi）上， fji0，則給 vj 標(biāo)號 (i， l (vj))， l (vj)=min[l (vi), fji], vj 成為標(biāo)號而未檢查的點。 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的增廣鏈。若所有標(biāo)號都已檢查過，而 vt尚未標(biāo)號，結(jié)束，這時可行流，即最大流。 （二）調(diào)整過程 從 vt 開始，反向追蹤，找出增廣鏈 181。，并在 181。上進(jìn)行流量調(diào)整。 （ 1）找增廣鏈 如 vt 的第一個標(biāo)號為 k（ 或 k）， 則?。?vk， vt）∈ 181。（或?。?vt， vk) ∈ 181。)。檢查 vk 的第一個標(biāo)號，若為 i（或 i），則 (vi,vk) ∈ 181。 (或 (vk,vi) ∈ 181。)。再檢查 vi 的第一個標(biāo)號 ,依此下去 ,直到 vs 。被找出的弧構(gòu)成了增廣鏈 181。 （ 2）流量調(diào)整 令調(diào)整量 ?是 l(vt)，構(gòu)造新的可行流 f ′， 令 ????????????????uvv fuvvfuvvffjiijjiijjiij39。ij ),( ),( ),( 去掉所有的標(biāo)號 ,對新的可行流 f ′={ fij′},重新進(jìn)入標(biāo)號過程。 例 用標(biāo)號法求下圖網(wǎng)絡(luò)的最大流?；∨缘臄?shù)字是 ( cij , fij)。 解：（一）標(biāo)號過程。 （ 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)號條件 。 （ 2）檢查 vs，在?。?vs， v1）上， fs1=1， cs1=5， fs1cs1, 給 v1標(biāo)號 (s, l(v1)), 其中 （ s， 4） （ 3）檢查 v1
外語相關(guān)推薦
鄂ICP備17016276號-1