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