運籌學(xué)圖與網(wǎng)絡(luò)分析-資料下載頁
2025-05-14 22:12本頁面
【正文】 對于 D中的每一個弧 （ vi , vj） ∈ E ,都有一個非負(fù)數(shù) cij,叫做弧的容量 。 我們把這樣的圖 G叫做容量網(wǎng)絡(luò) ， 簡稱網(wǎng)絡(luò) ， 記做 G=（ V， E， C） 。 網(wǎng)絡(luò) G上的流，是指定義在弧集合 E上的一個函數(shù) 其中 f(vi ,vj) =fij 叫做弧 (vi， vj)上的流量。 ? ? }{),( jiji fvvff ??稱滿足下列條件的流為可行流： （ 1）容量條件：對于每一個?。?vi ,vj） ∈ E 有 0 ? fij ? cij 。 （ 2） 平衡條件： 對于發(fā)點 vs， 有 對于收點 vt ， 有 對于中間點，有 ???EvvjsjsWf),(WfEvvtjtj???),(? ?? ??Evv Evvijjiji ijff),( ),(可行流中 fij＝ cij 的弧叫做飽和弧， fij＜ cij的弧叫做非飽和弧。 vs v1 v2 v4 v3 vt 3 7 4 5 5 6 3 7 8 S ),( 2vvS s? ),( 431 tvvvvS ?}),(),(,),(,),{(),(4232211vvvvvvvvSS s?18567),( 23241 ??????? lllSSC s 容量網(wǎng)絡(luò) G =（ V， E， C） ， vs為始點 ，vt為終點 。 如果把 V分成兩個非空集合 使 ， 則所有一點屬于 ， 而另一點屬于 的弧的集合 ， 稱為由 決定的割集 ,記作 。 割集 中所有始點在 ，終點在 的弧的容量之和 ， 稱為這個割集的容量 ， 記為 。 SS, SvSv ts ?? ,S),( SS ),( SS),( SSCSSSS關(guān)于最大流問題的定理： 最大流最小割定理：任一網(wǎng)絡(luò)中，最大流的流量等于最小割集的容量。 容量網(wǎng)絡(luò) G， 若 為網(wǎng)絡(luò)中從 vs到 vt的一條鏈 ， 給 定向為從 vs到 vt， 上的弧凡與 方向相同的稱為前向弧 ， 凡與 方向相反的稱為后向弧 ， 其集合分別用 和 表示 。 f 是一個可行流 ， 如果滿足： 則稱 為從 vs到 vt 的關(guān)于 f 的一條增廣鏈。 ?? ? ???? ?????????????????),(0),(0jijijijijijivvcfvvcf?推論 可行流 f 是最大流的充分必要條件是不存在從 vs到 vt 的關(guān)于 f 的一條可增廣鏈。 2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) ? ?7766633232211 ),(,),(,),(,),(, vvvvvvvvvvvvv??? ?),(),(),( 766321 vvvvvv??? ? ?),( 23 vv????是一個增廣鏈 顯然圖中增廣鏈不止一條 （ 二 ） 求最大流的標(biāo)號法 標(biāo)號過程： 1． 給發(fā)點 vs 標(biāo)號（ 0， +∞）。 2． 取一個已標(biāo)號的點 vi， 對于 vi一切未標(biāo)號的鄰接點 vj 按下列規(guī)則處理： （ 1）如果邊 ，且 ，那么給 vj 標(biāo)號 ，其中： （ 2） 如果邊 ， 且 ， 那么給 vj 標(biāo)號 ， 其中： 3． 重復(fù)步驟 2， 直到 vt被標(biāo)號或標(biāo)號過程無法進行下去 ， 則標(biāo)號結(jié)束 。 若 vt被標(biāo)號 ， 則存在一條增廣鏈 ， 轉(zhuǎn)調(diào)整過程；若 vt未被標(biāo)號 ， 而標(biāo)號過程無法進行下去 ， 這時的可行流就是最大流 。 Evv ij ?),( 0?ijf),( jiv ?? ),m in ( iijj f ?? ?Evv ji ?),( ijij cf ?),( jiv ?? ),m i n ( ijijij fc ?? ??調(diào)整過程： 1． 令 2． 去掉所有標(biāo)號 ， 回到第一步 ， 對可行流重新標(biāo)號 。 ?????????????????????),(),(),(jijijitjijitjijivvfvvfvvff 求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為 ),(jiji fc(3,3) (5,1) (1,1) (1,1) (4,3) (2,2) (3,0) (5,3) (2,1) vs v2 v1 v3 v4 vt (3,3) (5,1) (1,1) (1,1) (4,3) (2,2) (3,0) (5,3) (2,1) vs v2 v1 v3 v4 vt (△ ,+∞) (vs,4) (v1,1) (v2,1) (v2,1) (v3,1) 得增廣鏈，標(biāo)號結(jié)束，進入調(diào)整過程 (3,3) (5,2) (1,0) (1,0) (4,3) (2,2) (3,0) (5,3) (2,2) vs v2 v1 v3 v4 vt (vs,3) (△ ,+∞) 無增廣鏈，標(biāo)號結(jié)束，得最大流。同時得最小割。
高考資料相關(guān)推薦
鄂ICP備17016276號-1