【正文】 18 30 41 23 22 31 23 59 41 30 22 年度 第 1年 第 2年 第 3年 第 4年 第 5年 購(gòu)買(mǎi)費(fèi) 11 11 12 12 13 使用年數(shù) 01 12 23 34 45 維修費(fèi)用 5 6 8 11 18 這樣設(shè)備更新問(wèn)題就變?yōu)椋呵髲?v１ 到 v6 的最短路。 求解得： { v1 , v3 , v6 }及 { v1 , v4 , v6 }均為最短路。 總的支付費(fèi)用均為 53。 v1 v2 v3 v4 v5 v6 16 16 17 17 18 30 41 23 22 31 23 59 41 30 22 已知某地區(qū)的交通網(wǎng)絡(luò)如圖所示，其中點(diǎn)代表居民小區(qū)，便表示公路， wij為小區(qū)間公路距離．問(wèn)區(qū)中心醫(yī)院應(yīng)建在哪個(gè)小區(qū)，可使離醫(yī)院最遠(yuǎn)的小區(qū)居民就診時(shí)所走的路程最近 ? v6 v7 v5 v4 v3 v2 v1 60 30 20 25 18 15 15 20 30 例 2 選址問(wèn)題 . 解 ：實(shí)際要求出圖的中心，可以化為一系列求最短路問(wèn)題。 先求出 v1到其它各點(diǎn)的最短路長(zhǎng) dj ,令 D(v1)＝ max(d1, d2 , … , d7)．表示若醫(yī)院建在 v1，則離醫(yī)院最遠(yuǎn)的小區(qū)距離為 D(v1) 。再依次計(jì)算 v2 , v3 , … , v7 到其余各點(diǎn)的最短路，類(lèi)似求出 D(v2),D(v3) , … , D(v7) 。 D(vi)中最小者即為所求，計(jì)算結(jié)果見(jiàn)下表。 v6 v7 v5 v4 v3 v2 v1 60 30 20 25 18 15 15 20 30 1 2 3 4 5 6 71234567()0 3 0 5 0 6 3 9 3 4 5 6 0 9 33 0 0 2 0 3 3 6 3 1 5 3 0 6 35 0 2 0 0 2 0 5 0 2 5 4 0 5 06 3 3 3 2 0 0 3 0 1 8 3 3 6 39 3 6 3 2 0 0 0 4 8 6 3 9 34 5 1 5 2 5 1 8 4 8 0 1 5 4 86 0 3 0 4 0 3 3 6 3 1 5 0 6 3iv v v v v v v D vvvvvvvv由于 D(v6)＝ 48 最小，所以醫(yī)院應(yīng)建在 v6，此時(shí)離醫(yī)院最遠(yuǎn)的小區(qū) (v5) 距離為 48 . 不同網(wǎng)絡(luò)中流的意義不同，流本身是一種輸送，可以把它們統(tǒng)稱(chēng)為運(yùn)輸網(wǎng)絡(luò)的流。 許多系統(tǒng)包含了流量問(wèn)題。 例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車(chē)流、貨物流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流，等等 . 最大流問(wèn)題 8 5 2 8 7 9 6 6 5 3 vs v1 vt v4 v3 v2 管道網(wǎng)絡(luò)中每邊的最大通過(guò)能力即容量是有限的，實(shí)際流量也并不一定等于容量，上述問(wèn)題就是要討論如何充分利用裝置的能力．以取得最好效果 (流量最大 )，這類(lèi)問(wèn)題通常稱(chēng)為 最大流問(wèn)題 。 50年代福持 (Ford)、富克遜 (Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。 8 5 2 8 7 9 6 6 5 3 vs v1 vt v4 v3 v2 一、最大流基本概念 1. 網(wǎng)絡(luò)與流 給一個(gè)有向連通圖 D=(V,A)，在 V 中指定了一個(gè)點(diǎn)，稱(chēng)為 發(fā)點(diǎn) (或 源 ，記為 vs，其入度為 0)，和另一個(gè)點(diǎn)，稱(chēng)為 收點(diǎn) (或 匯 ，記為 vt，其出度為 0)，其余點(diǎn)叫 中間點(diǎn) ， 對(duì) D的每條弧 (vi ,vj)對(duì)應(yīng)有一個(gè)非負(fù)數(shù) cij ,稱(chēng)為 弧的容量 ，這樣的網(wǎng)絡(luò) D稱(chēng)為 容量網(wǎng)絡(luò) ，常記做 D =(V,A,C)。 對(duì)任一 D中的弧 (vi ,vj)有 流量 fij ，稱(chēng)集合 f={ fij } 為 網(wǎng)絡(luò) D上的一個(gè)流 。 (5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 例 網(wǎng) 絡(luò) D 及其一個(gè)流 vs為 發(fā)點(diǎn) (源 )， vt為 收點(diǎn) (匯 )，其余點(diǎn)為 中間點(diǎn) 。 對(duì)每條弧 (vi ,vj)，有 弧的容量 cij ， 弧的流量 fij ， 常記做 (fij , cij ). 如 fs1 = 5， f12 = 4 ， f42 = 2. 集合 f={ fij } 稱(chēng)為 網(wǎng)絡(luò) D上的一個(gè)流 . 2. 可行流與最大流 稱(chēng)滿(mǎn)足下列條件的流 f 為 可行流： (1)容量限制條件：對(duì)所有弧 (vi ,vj) ，成立 (2)平衡條件：對(duì)所有中間頂點(diǎn) v ，成立 其中， f +(v)是流出 v 的總流量， f (v)是流入 v的總流量， 對(duì)于源點(diǎn) v s和匯點(diǎn) vt ，流出源點(diǎn) vs 的流量等于流入?yún)R點(diǎn) v t的流量 . 0 ij ijfc??( ) ( )f v f v???稱(chēng)之為 流 f 的值 ，記為 val f 或 v( f ). ( , )( ) ( ) ,v u Af v f v u??? ?( , ) ( ) ( ) .u v Af v f u v??? ?( , ) ( , )( ) ( ) ( ) ( ) ( )sts s t tv u A u v Av f f v f v u f v f u v????? ? ? ???可行流總是存在的。 例如令所有弧的流量 fij=0，就得到一個(gè)可行流 f ={ 0 }(稱(chēng)為 零流 )，其流量 v(f)=0. 所謂 最大流問(wèn)題 就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。 最大流問(wèn)題實(shí)際是個(gè)線性規(guī)劃問(wèn)題，但是利用它與圖的緊密關(guān)系，能更為直觀簡(jiǎn)便地求解。 (5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 v(f)=7. 3. 增廣鏈 一個(gè)可行流 f ={ fij }， 稱(chēng) fij= cij 的弧為 飽和弧 ，稱(chēng) fij cij 的弧為 不飽和弧 . fij= 0的弧為 零流弧 ， fij 0的弧為 非零流弧 . (5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 飽和弧 零流弧 不飽和弧 設(shè) P是網(wǎng)絡(luò) D的一條連接源點(diǎn) vs 和匯點(diǎn) vt 的鏈，定義鏈 P的方向 是從 vs 到 vt ， ? 前向弧 — 弧的方向與 P的方向一致；全體記為 P +. ? 后向弧 — 弧的方向與 P的方向相反；全體記為 P . 鏈 P ： 1 2 4( , , , , )stv v v v v1 1 2 4{ ( , ) , ( , ) , ( , ) }stP v v v v v v? ? 42{ ( , ) }P v v? ?(5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 注：鏈不是有向路，鏈的每一邊去掉方向是一條路 . 則 P中的弧可分為兩類(lèi)： f 是一個(gè)可行流， P是從 vs 到 vt 的一條鏈， 如果 (1) P 的每一前向弧都是不飽和?。? ） 。 (2) P 的每一后向弧都是非零流弧（ ）； 則稱(chēng) P 是網(wǎng)絡(luò) D 的 關(guān)于可行流 f 的一條增廣鏈 。簡(jiǎn)稱(chēng) 增廣鏈 。 0 ij ijfc??0 ij ijfc??(5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 增廣鏈 P ： 1 2 4( , , , , )stv v v v v4. 割集 設(shè) S、 S是網(wǎng)絡(luò) D的兩個(gè)頂點(diǎn)子集 ,且 且 , 定義 D的一個(gè) 割集 (簡(jiǎn)稱(chēng) 割 )為 也稱(chēng)為 分離 vs和 vt一個(gè)割集 ，可簡(jiǎn)記為 K . ,stv S v S??( , ) { | ( , ) , , , }S S a a u v A u S v S u S v S? ? ? ? ? ? ?或(5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 SS1 2 3 2 3 4 4 1( , ) { ( , ) , ( , ) , ( , ) , ( , ) }S S v v v v v v v v?,S S V S S? ? ?割集 網(wǎng)絡(luò)的割集有多個(gè)，其中割集容量最小者稱(chēng)為網(wǎng)絡(luò)的 最小割集容量 (簡(jiǎn)稱(chēng) 最小割 )。 (5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 SS1 2 3 2 3 4 4 1( , ) { ( , ) , ( , ) , ( , ) , ( , ) }S S v v v v v v v v?( , ) 1 8cap S S ?割集 (S,S)中所有始點(diǎn)在 S，終點(diǎn)在 S的弧容量之和稱(chēng)為 (S,S)的 割集容量 (割量 )。記作 ( , )ca p S S顯然，對(duì)于網(wǎng)絡(luò)的任意一個(gè)可行流 f 和割 (S,S)， 成立 ( ) ( , )v f c a p S S?因此 ,若能找到一個(gè)可行流 f ，一個(gè)割集 (S,S)，使得成立 則 f 必是最大流 ，而 (S,S)是最小割 。 ( ) ( , )v f c a p S S?(5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 SS( , ) 1 8cap S S ? 定理 ：設(shè) f 是網(wǎng)絡(luò) D上的一個(gè)可行流，則 f 是一個(gè)最大流當(dāng)且僅當(dāng)網(wǎng)絡(luò) D不存在 f 的增廣鏈。 (5,8) (4,5) (2,2) (3,8) (1,7) (6,9) (1,6) (2,6) (0,5) (0,3) vs v1 vt v4 v3 v2 增廣鏈 P ： 1 2 4( , , , , )stv v v v v最大流最小割定理 ：任一個(gè)網(wǎng)絡(luò) D中，從 vs到 vt 的最大流的流量等于分離 vs和 vt 的最小割的容量 . ? 定理：設(shè) f 是網(wǎng)絡(luò) D上的一個(gè)可行流，則 f 是一個(gè)最大流當(dāng)且僅當(dāng)網(wǎng)絡(luò) D不存在 f 的增廣鏈。 ? 證明 (必要性 ) 設(shè) f 是一個(gè)最大流，假如 D中存在 f 的增廣鏈 P,則可以得到一個(gè)流值更大的流 f 1,使得 1( ) ( ) , 0v f v f ??? ? ?? 構(gòu)造過(guò)程如下： 1( ) ,( ) ,( ) ,f a a Pf f a a Pf a a P????? ???? ? ??? ??12m i n { ( ) ( ) , } , m i n { ( ) , }c a f a a P f a a P?? ??? ? ? ? ?其中 12m i n { , } 0,? ? ???二、尋找最大流的標(biāo)號(hào)算法 (FordFulkerson算法 ) Ford Fulkerson 算法 基本思想 ： ? 從任意一個(gè)可行流出發(fā)，尋找流的增廣鏈，并在這條增廣鏈上調(diào)整流值 ,進(jìn)而得到一個(gè)新可行流； ? 對(duì)新流繼續(xù)尋找增廣鏈，依次進(jìn)行下去，直到一個(gè)最大流為止 . ? 分兩步： 1 標(biāo)號(hào)過(guò)程 (尋找增廣鏈 )； 2 調(diào)整過(guò)程 . ? 每個(gè)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表明它的標(biāo)號(hào)是從哪一點(diǎn)得到的，以便找出增廣鏈；第二個(gè)標(biāo)號(hào)是為確定增廣鏈的調(diào)整量用的。 Ford 與 Fulkerson 在 1957年提出一個(gè)求解網(wǎng)絡(luò)最大流問(wèn)題的算法，稱(chēng)為 Ford Fulkerson 算法 。 Ford Fulkerson 算法步驟： 1. 標(biāo)號(hào)過(guò)程 (尋找流 f 的增廣鏈 ) ?(1) 給 網(wǎng)絡(luò)賦一個(gè)初始 0流 f 0；給 vs 標(biāo)號(hào) (,∞)。 ?(2) 選擇一個(gè)已標(biāo)號(hào)的點(diǎn) vi , 對(duì)于 vi 的所有未給標(biāo)號(hào)的鄰接點(diǎn) vk , 按下列規(guī)則處理： (a) 對(duì)每條弧 (vi ,