or教案23_圖論-全文預(yù)覽
【正文】 的應(yīng)用 ? 多發(fā)點、多收點的最大流問題 ? 最大匹配問題 ? Fordfulkerson標(biāo)號法應(yīng)用問題 空車調(diào)運問題 弧旁的數(shù)字是線路上的車輛通行能力，記為 Cij。 181。 （ 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)號條件 。ij ),( ),( ),( 去掉所有的標(biāo)號 ,對新的可行流 f ′={ fij′},重新進入標(biāo)號過程。)。（或?。?vt， vk) ∈ 181。 （二）調(diào)整過程 從 vt 開始，反向追蹤，找出增廣鏈 181。 （ 1）若?。?vi， vj）上， fijcij，則給 vj 標(biāo)號 (i， l(vj))， l(vj)=min[l (vi), cijfij], vj 成為標(biāo)號而未檢查的點。 定理 2 最大流最小截定理。 設(shè) D中不存在關(guān)于 f *的增廣鏈，證明 f *是最大流。即 )V,C ( VV ( f ) 11?可行流 f *，截集 (V1*， V1*), 若 V( f *)=C( V1*， V1*）， 則 f *必是最大流， (V1*， V1*) 必是 D的最小截集。 0 fij ≤ cij 后向弧 是非零流弧， (vi , vj ) ∈ 181。 ={(v5,v4)} v2 v5 v3 v1 v4 v6 定義 3 設(shè) f 是一個可行流 , 181。是聯(lián)結(jié) vs和 vt的一條鏈，定義鏈的方向是從 vs到 vt 。 流 : 定義在弧集 A上的一個函數(shù) f={f(vi ,vj )}，并稱 f(vi ,vj )為弧 (vi ,vj )上的流量。 問題：這個運輸網(wǎng)絡(luò)中，從 v1到 v6的最大輸送量是多少？ v2 v5 3 1 3 v3 v1 v4 v6 1 5 3 6 2 2 2 一、基本概念與定理 1. 網(wǎng)絡(luò)與流 定義 1 給定一個有向圖 D=（ V， A），在 V中指定 一點 vs 稱為發(fā)點，指定另一點 vt 稱為收點， 其余點稱中間點。 弧旁數(shù)字： 運輸能力。記為 D=（ V， A， C）。 可行流總是存在的 3. 增廣鏈 對可行流 f ={ fij }： 非飽和弧： fij cij 飽和?。?fij =cij 非零流?。?fij 0 零流弧： fij =0 鏈的方向：若 181。 后向?。夯〉姆较蚺c鏈的方向相反，記為 181。+={(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6)} 181。 (vi , vj ) ∈ 181。 v2 v5 v3 v1 v4 v6 =(v1,v2,v3) V1 V 1=(v4,v5,v6) 定義 5 給一截集（ V1， V1），把截集（ V1， V1）中所 有弧的容量之和稱為這個截集的容量（簡稱
外語相關(guān)推薦
鄂ICP備17016276號-1