【正文】 Ford Fulkerson 算法步驟： 1. 標(biāo)號(hào)過(guò)程 (尋找流 f 的增廣鏈 ) ?(1) 給 網(wǎng)絡(luò)賦一個(gè)初始 0流 f 0；給 vs 標(biāo)號(hào) (,∞)。 ? 證明 (必要性 ) 設(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)整量用的。 ( ) ( , )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 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的弧容量之和稱為 (S,S)的 割集容量 (割量 )。簡(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 }， 稱 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 飽和弧 零流弧 不飽和弧 設(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中的弧可分為兩類： f 是一個(gè)可行流， P是從 vs 到 vt 的一條鏈， 如果 (1) P 的每一前向弧都是不飽和?。? ） 。 例如令所有弧的流量 fij=0，就得到一個(gè)可行流 f ={ 0 }(稱為 零流 )，其流量 v(f)=0. 所謂 最大流問(wèn)題 就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。 (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) 。 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)，稱為 發(fā)點(diǎn) (或 源 ，記為 vs，其入度為 0)，和另一個(gè)點(diǎn)，稱為 收點(diǎn) (或 匯 ，記為 vt，其出度為 0)，其余點(diǎn)叫 中間點(diǎn) ， 對(duì) D的每條弧 (vi ,vj)對(duì)應(yīng)有一個(gè)非負(fù)數(shù) cij ,稱為 弧的容量 ，這樣的網(wǎng)絡(luò) D稱為 容量網(wǎng)絡(luò) ，常記做 D =(V,A,C)。 例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(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)題就是要討論如何充分利用裝置的能力．以取得最好效果 (流量最大 )，這類問(wèn)題通常稱為 最大流問(wè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)稱為運(yùn)輸網(wǎng)絡(luò)的流。再依次計(jì)算 v2 , v3 , … , v7 到其余各點(diǎn)的最短路，類似求出 D(v2),D(v3) , … , D(v7) 。 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 , v3 , v6 }及 { v1 , v4 , v6 }均為最短路。 用點(diǎn) vi表示第 i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備．虛設(shè)一個(gè)點(diǎn) v6 ,表示第五年年底。 若已知設(shè)備在各年年初的價(jià)格為： 年度 第 1年 第 2年 第 3年 第 4年 第 5年 購(gòu)買費(fèi) 11 11 12 12 13 還知使用不同年數(shù)的設(shè)備所需要的維修費(fèi)用為： 使用年數(shù) 01 12 23 34 45 維修費(fèi)用 5 6 8 11 18 可供選則的設(shè)備更新方案是很多的。 i k k j i k jd d d??如在 D(1)中的 是由 ( 1 )0 5 1 25 0 6 7 22 3 0 2 82 7 3 0 42 4 4 0D???????? ?????????(1)23 6d ? ( 0 ) ( 0 )2 1 1 3 5 1 6dd ? ? ? ?得到的，所以 可以寫成 . (1)23d 2136( 2 )0 5 1 2 75 0 6 7 22 3 0 2 52 7 3 0 47 2 4 4 0D??????? ????????而 D(2)中的 是由 ( 2 )35 5d ?( 1) ( 1)3 2 2 5 3 2 5dd ? ? ? ?得到的，所以 可以寫成 . (2)35d 3255( 2 )0 5 1 2 75 0 6 7 22 3 0 2 52 7 3 0 47 2 4 4 0D??????? ????????而 D(2)中的 是由 ( 2 )35 5d ?( 1) ( 1)3 2 2 5 3 2 5dd ? ? ? ?得到的，所以 可以寫成 . (2)35d 3255( 3 )0 4 1 2 65 0 6 7 22 3 0 2 52 6 3 0 46 2 4 4 0D??????? ????????而 D(3)中的 是由 ( 3 )15 6d ? ( 2 ) ( 2 )1 3 3 5 1 5 6dd ? ? ? ?得到的，而 所以 可以寫成 等 . (3)15d 13256( 2 )3 5 3 2 55d ?由此 13 2 13 14 13 2521 21 3 25 4 25( 5 )31 32 34 32 541 41 32 41 3 4553 1 52 53 540 4 1 2 65 0 6 6 22 3 0 2 52 6 3 0 46 2 4 4 0D????? ??????v1 v2 v4 v3 v5 5 1 2 2 3 10 2 8 4 4 6 2 應(yīng) 用 舉 例 例 1 設(shè)備更新問(wèn)題 . 某工廠使用一臺(tái)設(shè)備，每年年初工廠都要作出決定．如果繼續(xù)使用舊的，要付維路費(fèi)；若購(gòu)買一臺(tái)新設(shè)備．要付購(gòu)買費(fèi)。 所以 D(5)就給出了任意兩點(diǎn)間不論幾步到達(dá)的最短路長(zhǎng)。 (2) 計(jì)算 其中 ( ) ( )( ) ( 1 , 2 , , )kk i j n nD d k n???( ) ( 1 ) ( 1 ) ( 1 )m i n [ , ]k k k ki j i j i k k jd d d d? ? ???( 2 )0 5 1 2 75 0 6 7 22 3 0 2 52 7 3 0 47 2 4 4 0D??????? ????????計(jì)算 ( 2 ) ( 1 ) ( 1 ) ( 1 )22m i n [ , ]i j i j i jd d d d??其中 表示從 vi點(diǎn)到 vj點(diǎn) 最多經(jīng)中間點(diǎn) v1 , v2 , v3的最短路長(zhǎng)。 解 : (1)輸入權(quán)矩陣 D(0)=D. v1 v2 v4 v3 v5 5 1 2 2 3 10 2 8 4 4 6 2 ( 0 )0 5 1 25 0 10 22 3 0 2 82 6 0 42 4 4 0D????????? ??????????1v2v3v4v1v 2v 3v 4v5v5v( 0 )0 5 1 25 0 10 22 3 0 2 82 6 0 42 4 4 0D????????? ??????????1v2v3v4v1v 2v 3v 4v5v5v(2) 計(jì)算 其中 ( ) ( )( ) ( 1 , 2 , , )kk i j n nD d k n???( ) ( 1 ) ( 1 ) ( 1 )m i n [ , ]k k k ki j i j i k k jd d d d? ? ???計(jì)算 ( 1 ) ( 1 )()