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