《圖與網(wǎng)絡(luò)分析》PPT課件

《《圖與網(wǎng)絡(luò)分析》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《圖與網(wǎng)絡(luò)分析》PPT課件（80頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、運(yùn)籌學(xué)第六章 圖與網(wǎng)絡(luò)分析,機(jī)電工程學(xué)院 工業(yè)工程系 周宇鵬 辦公電話：86417778-604 手機(jī)：13936135705 Email：,哥尼斯堡七橋問題,第六章 圖與網(wǎng)絡(luò)分析,2,,表示過橋的費(fèi)用,,表示橋單位時間最多通過的車輛數(shù),圖的基本概念 樹圖 最短路徑問題 網(wǎng)絡(luò)最大流問題 網(wǎng)絡(luò)最小費(fèi)用流問題,第六章 圖與網(wǎng)絡(luò)分析,3,圖與網(wǎng)絡(luò)分析的主要內(nèi)容,圖在生產(chǎn)、生活中的應(yīng)用十分廣泛 物流、交通領(lǐng)域 交通圖 供水、電等 管網(wǎng)圖 通訊 網(wǎng)絡(luò)拓?fù)鋱D 設(shè)施規(guī)劃 組織比賽 表示企業(yè)組織架構(gòu),圖的主要應(yīng)用領(lǐng)域,第六章 圖與網(wǎng)絡(luò)分析,4,,樹,,,,,,,,,,第六章 圖與網(wǎng)絡(luò)分析,5,第一節(jié) 圖的基

2、本概念（1）,圖: 由點(diǎn)和點(diǎn)與點(diǎn)之間的連線組成，是點(diǎn)和線的集合。 若點(diǎn)與點(diǎn)之間的連線沒有方向，稱為邊，由此構(gòu)成的圖為無向圖。表示為：G =（V，E）。 若點(diǎn)與點(diǎn)之間的連線有方向，稱為弧，這樣的圖稱為有向圖。表示為：G =（V，A）。,,,,,,,v1,v2,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,e9,頂點(diǎn) 節(jié)點(diǎn),邊,弧,第一節(jié) 圖的基本概念（4）,完全圖：任意兩點(diǎn)均有邊相連的簡單圖。 環(huán)：端點(diǎn)相重的邊或弧。 多重邊：兩點(diǎn)間有多條邊。 簡單圖：無環(huán)和多重邊的圖。 完全圖的特性 含有n個頂點(diǎn)的完全圖，其邊數(shù)有 條。,第六章 圖與網(wǎng)絡(luò)分析,8,,第一節(jié) 圖

3、的基本概念（5）,偶圖（二分圖） 圖的頂點(diǎn)能分為兩個互不相交的非空集合V1和V2，使在同一集合中任意兩個頂點(diǎn)均不相鄰，這樣的圖我們稱為偶圖。 V1和V2間每一對不同的頂點(diǎn)都相鄰，這樣圖稱為完全偶圖。如V1中有m個頂點(diǎn)，V2中有n個頂點(diǎn)，其邊數(shù)共mn條。,第六章 圖與網(wǎng)絡(luò)分析,9,第二節(jié) 樹圖樹的定義和性質(zhì),樹：無圈的連通圖。 樹的性質(zhì)： 樹是簡單圖（無環(huán)和多重邊） 樹中必然存在次為1的點(diǎn) n個頂點(diǎn)的樹，邊為n-1條 有n個頂點(diǎn)，n-1條邊的連通圖必然是樹。,第六章 圖與網(wǎng)絡(luò)分析,10,,,,,,,,,,,,,,,,,,懸掛邊,懸掛點(diǎn),樹枝,根,葉子,,,第二節(jié) 樹圖最小部分樹,子圖： 圖G1=

4、（V1，E1）和G2=（V2，E2），如V2 V1且E2 E1，則稱G2為G1的子圖。 部分圖：如V2= V1且E2 E1，則稱G2為G1的部分圖。 部分樹： G2為G1的部分圖且G2是樹，則稱G2為G1的部分樹。 最小部分樹：樹枝總長最小的部分樹稱為最小部分樹（最小支撐樹）。,第六章 圖與網(wǎng)絡(luò)分析,11,,,,,,,,,,v1,v2,v3,v4,e2,e4,e1,e3,e9,,,,,,,,v1,v2,v3,v4,e2,e4,e1,圖1,圖2,第二節(jié) 樹圖最小部分樹定理,求圖最小部分樹方法： 避圈法 破圈法 定理：圖G任意點(diǎn)vi，若j是與i相鄰點(diǎn)中距離最近的，則邊i,j必包含于G的最小部

5、分樹中。 推論：把圖G分為V和V兩個集合，兩集合間連線的最短邊必定包含于G的最小生成樹中。,第六章 圖與網(wǎng)絡(luò)分析,12,,,,,,,,,,,k,i,j,,,,,,,,第二節(jié) 樹圖避圈法（1）,第六章 圖與網(wǎng)絡(luò)分析,13,,,,,,,,,,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,,,,,,,是否所有點(diǎn)V,任選一點(diǎn)vi V，其余點(diǎn)V,開始,結(jié)束,找出V和V之間的最短邊，vi，vj 最小部分樹,Vvj =V，V vj =V,,,,,,,是,否,算法流程圖：,,,,,,,,,,,,已知：點(diǎn)A、B、C、D、E、S、T代表城市，線代表城市之間的道路，線上的數(shù)字代表道路的長度

6、。 求：沿道路架設(shè)電線，使所有城市都能通上電，如何架設(shè)使總的線路長度最短。,第二節(jié) 樹圖避圈法（2）,第六章 圖與網(wǎng)絡(luò)分析,14,S,D,A,T,B,,C,E,,,,,,,,,,,2,2,4,1,3,4,,7,7,5,5,5,1,第二節(jié) 樹圖破圈法,任選一個圈，從圈中去掉權(quán)最大的一條邊。在余下的圖中重復(fù)這個步驟，直到得到一不含圈的連通圖為止。,第六章 圖與網(wǎng)絡(luò)分析,15,S,D,A,T,B,,C,E,,,,,,2,2,1,3,5,1,第三節(jié) 最短路問題,賦權(quán)無向圖D中的兩個頂點(diǎn)vs和vt，設(shè)P是由vs到vt的一條路，把P中所有邊的權(quán)之和稱為路P的權(quán)，記為d(P)。如果路P*的權(quán)d(P*)是由v

7、s到vt的所有路的權(quán)中的最小者，則稱P*是從vs到vt的最短路。最短路P*的權(quán)d(P*)稱為從vs到vt的距離，記為L(vs,vt)。 狄克斯拉算法（Dijkstra） 矩陣算法,第六章 圖與網(wǎng)絡(luò)分析,16,第三節(jié) 最短路問題狄克斯拉算法（1）,第六章 圖與網(wǎng)絡(luò)分析,17,狄克斯拉算法也稱雙標(biāo)號算法 假定(1，2)，(2，3)，(3，4)是點(diǎn)1到4的最短路 則(1，2)，(2，3)是點(diǎn)1到3的最短路； (2，3)，(3，4)是點(diǎn)2到4的最短路；,1,2,3,4,5,,,,,,第三節(jié) 最短路問題狄克斯拉算法（2）,狄克斯拉算法流程： 用dij表示相鄰點(diǎn)vi與vj的距離，若vi與vj不相鄰，則 d

8、ij= ，dii = 0，用Lij表示最短距離，求s點(diǎn)到t點(diǎn)的最短路。 從s點(diǎn)出發(fā)，Lss=0。將Lss的值標(biāo)示在點(diǎn)s上，表示s點(diǎn)已經(jīng)被標(biāo)號。 找出與s點(diǎn)相鄰點(diǎn)中距離最短的一點(diǎn)，假設(shè)是r，則Lsr= Lss+ dsr，將Lsr的值標(biāo)示在點(diǎn)r上。r點(diǎn)被標(biāo)號。 從已標(biāo)號的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號點(diǎn)，如果有一點(diǎn)p滿足：Lsp = minLss + dsp，Lsr + drp ，則用Lsp的值對p點(diǎn)標(biāo)號。 重復(fù)第3步，直至t點(diǎn)被標(biāo)號。,第六章 圖與網(wǎng)絡(luò)分析,18,第三節(jié) 最短路問題狄克斯拉算法案例一(1),第六章 圖與網(wǎng)絡(luò)分析,19,,,L1=0,5,6,2,4,7,3,,,,,,,,,2

9、,2,4,6,7,2,1,3,6,7,,1,,,5,,L3=2,Lr=minL1+d12,L1+d13=min0+5,0+2=2=L3,求1到7的最短路,,第三節(jié) 最短路問題狄克斯拉算法案例一(2),第六章 圖與網(wǎng)絡(luò)分析,20,,,L1=0,5,6,2,4,7,3,,,,,,,,,2,2,4,6,7,2,1,3,6,7,,1,,,5,,,L3=2,L2=5,Lp=minL1+d12, L3+d34, L3+d36,=min0+5,2+7,2+4=5=L2,,第三節(jié) 最短路問題狄克斯拉算法案例一(3),第六章 圖與網(wǎng)絡(luò)分析,21,,L1=0,5,6,2,4,7,3,,,,,,,,,2,2,4,6

10、,7,2,1,3,6,7,,1,,,5,,,L3=2,L6=6,,L2=5,Lp=minL2+d24, L2+d25,L3+d34, L3+d36,=min5+7,5+2,2+7, 2+4=6=L6,,,第三節(jié) 最短路問題狄克斯拉算法案例一(4),第六章 圖與網(wǎng)絡(luò)分析,22,,L1=0,5,6,2,4,7,3,,,,,,,,,2,2,4,6,7,2,1,3,6,7,,1,,,5,,L3=2,L2=5,,,L6=6,L4=7,L5=7,Lp=minL2+d24, L2+d25,L3+d34, L6+d67, L6+d64, L6+d65=min5+7,5+2,2+7, 6+2,6+1,6+6=7

11、=L4=L5,,,,第三節(jié) 最短路問題狄克斯拉算法案例一(5),第六章 圖與網(wǎng)絡(luò)分析,23,L1=0,5,6,2,4,7,3,,,,,,,,,2,2,4,6,7,2,1,3,6,7,,1,,,5,,L3=2,L2=5,,L6=6,L4=7,L5=7,L7=10,Lp=minL5+d57, L6+d67=min7+3,6+6=10=L7,得到最短路,第三節(jié) 最短路問題狄克斯拉算法案例二,第六章 圖與網(wǎng)絡(luò)分析,24,2,3,7,1,8,4,5,6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,狄克斯拉算法適用于權(quán)大于等于0的網(wǎng)絡(luò)。對有向圖、無向圖都適用

12、。 在有向圖中： wij表示vi與vj的最短距離Lij cij表示相鄰點(diǎn)vi與vj的距離 dij,求上圖中從1到8的最短路徑,第六章 圖與網(wǎng)絡(luò)分析,25,,2,3,7,1,8,4,5,6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,X=1, w1=0,min c12,c14,c16=min0+2,0+1,0+3=min2,1,3=1 X=1,4, w4=1,,,,w1=0,第六章 圖與網(wǎng)絡(luò)分析,26,,2,3,7,1,8,4,5,6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,X=1,4,minc1

13、2,c16, w4+c42, w4+c47 = min2, 3,1+10,1+2 = min2,3,11,3 = 2 X=1,2,4, w2=2,w1=0,w4=1,,,,w2=2,,第六章 圖與網(wǎng)絡(luò)分析,27,,2,3,7,1,8,4,5,6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,X=1,2,4,min c13, w2+c23, w2+c25, w4+c47 = min 0+3,2+6,2+5,1+2 = min 3,8,7,3 = 3 X=1,2,4,6, w6=3，w7=3,w2=2,w4=1,w1=0,,,,,w6=3,w7=3,第

14、六章 圖與網(wǎng)絡(luò)分析,28,,2,3,7,1,8,4,5,6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,X=1,2,4,6,min w2+c23, w2+c25, w4+c47, w6+c67 = min2+6,2+5,1+2,3+4 = min8,7,3,7=3 X=1,2,4,6,7, w7=3,w2=2,w4=1,w1=0,,,,,w6=3,w7=3,第六章 圖與網(wǎng)絡(luò)分析,29,,2,3,7,1,8,4,5,6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,X=1,2,4,6,7,min w2+

15、c23, w2+c25, w7+c75, w7+c78 = min2+6,2+5,3+3,3+8 = min8,7,6,11 = 6 X=1,2,4,5,6,7, w5=6,w2=2,w4=1,w1=0,,,w6=3,w7=3,,,w5=6,第六章 圖與網(wǎng)絡(luò)分析,30,,2,3,7,1,8,4,5,6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,X=1,2,4,6,7,minw2+c23, w5+c53, w5+c58, w7+c78 = min2+6,6+9,6+4,3+8 = min8,15,10,11 = 8 X=1,2,3,4,5,6,7

16、, w3=8,w2=2,w4=1,w1=0,,w6=3,w7=3,,w5=6,w3=8,,,第六章 圖與網(wǎng)絡(luò)分析,31,,2,3,7,1,8,4,5,6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,X=1,2,3,4,6,7,min w3+c38, w5+c58, w7+c78 = min 8+6,6+4,3+7 = min 14,10,11 = 10 X=1,2,3,4,5,6,7,8, w8=10,w2=2,w4=1,w1=0,w6=3,w7=3,,w5=6,w3=8,,,w8=10,第六章 圖與網(wǎng)絡(luò)分析,32,,2,3,7,1,8,4,5,

17、6,,,,,,,,,,,,,,,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,,X=1,2,3,4,6,7,8,1到8的最短路徑為1，4，7，5，8，長度為10。 1到3的最短距離為8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,第三節(jié) 最短路問題矩陣算法,雙標(biāo)號法能夠計算出網(wǎng)絡(luò)中任意一點(diǎn)到其他點(diǎn)的最短距離。 矩陣算法可以一次計算出網(wǎng)絡(luò)所有點(diǎn)之間的最短距離。 矩陣算法的基本思想與雙標(biāo)號法一致。 假定1，2，2，3，3，4是點(diǎn)1到4的最短路 則1，2，2，3是點(diǎn)1到3的最短路； 2，3，3，4是點(diǎn)2到4的最短路；,第六章 圖與網(wǎng)絡(luò)分析,33,

18、6,第三節(jié) 最短路問題矩陣算法（第一步）,第六章 圖與網(wǎng)絡(luò)分析,5,6,2,4,7,3,,,,,,,,,2,2,4,6,7,2,1,3,6,7,,1,,,5,,,d12,d13,d14,d15,d16,d17,d23,d24,d25,d26,d27,d34,d35,d36,d37,d45,d46,d47,d56,d57,d67,dij表示i與j的距離，i和j不相鄰，則令dij= ,34,5,2,,,,,,2,7,,,7,,4,,6,2,,1,3,第六章 圖與網(wǎng)絡(luò)分析,第三節(jié) 最短路問題矩陣算法（第二步）,先考慮i到j(luò)有一個中間點(diǎn)時的情況。 v1到v2的最短距離應(yīng)該是mind11+d12, d1

19、2+d22, d13+d32, d14+d42, d15+d52, d16+d62, d17+d72。即min（d1r+dr2），r=1，2，7。 因此我們可以構(gòu)造一個新矩陣D（1），令dij=mindir+drj，r=1p。 那么這個矩陣就給出了網(wǎng)絡(luò)中直接到達(dá)及經(jīng)過一個中間點(diǎn)的最短距離。,35,第六章 圖與網(wǎng)絡(luò)分析,36,,,5,2,7,12,6,,第三節(jié) 最短路問題矩陣算法（第三步）,在D（1）的基礎(chǔ)上，構(gòu)造一個新矩陣D（2），令dij（2）=mindir（1）+drj （1），r=1p。 這個矩陣就表示出了網(wǎng)絡(luò)中任意兩點(diǎn)，直接到達(dá)；經(jīng)過一個點(diǎn)、兩個點(diǎn)和三個點(diǎn)到達(dá)的最短距離。 dir（1）

20、表示i直接到r，或i經(jīng)過pa到r， a=1p； drj（1）表示r直接到j(luò)，或r經(jīng)過pb到j(luò)， b=1p； 如果r=i，j：dij（2）表示i直接到j(luò)，或i經(jīng)過一點(diǎn)到j(luò)； 如i直接到r，r直接到j(luò)： dij（2）表示i經(jīng)過r到j(luò)； 如i經(jīng)過pa到r，或r經(jīng)過pb到j(luò)： dij（2）表示i經(jīng)過兩點(diǎn)到j(luò)； 如i經(jīng)過pa到r，且r經(jīng)過pb到j(luò)： dij（2）表示i經(jīng)過三點(diǎn)到j(luò)；,第六章 圖與網(wǎng)絡(luò)分析,37,第三節(jié) 最短路問題矩陣算法（第k步）,通過歸納可知：dij(k) =mindir(k-1)+drj(k-1)，能夠表示網(wǎng)絡(luò)中任意兩點(diǎn)直接到達(dá)，或經(jīng)過一個、兩個（2k-1）個中間點(diǎn)到達(dá)的最短距離。

21、假設(shè)網(wǎng)絡(luò)有p個頂點(diǎn)，那么矩陣算法的結(jié)束條件是：,第六章 圖與網(wǎng)絡(luò)分析,38,第六章 圖與網(wǎng)絡(luò)分析,39,5,2,7,,,第四節(jié) 網(wǎng)絡(luò)最大流問題,弧的容量：對網(wǎng)絡(luò)上的每條弧給出一個最大通過能力c（vi，vj），簡記為cij，c稱為弧的容量。 容量網(wǎng)絡(luò)：給定了弧的容量的有向圖D=（V，A，C）叫做一個容量網(wǎng)絡(luò)。 容量網(wǎng)絡(luò)中通常規(guī)定一個發(fā)點(diǎn)s（源點(diǎn)），一個收點(diǎn)t（匯點(diǎn)）。其他點(diǎn)稱為中間點(diǎn)。,第六章 圖與網(wǎng)絡(luò)分析,40,,,,,,,,,,,,,,,,,,,,s,t,s,t,,,第四節(jié) 網(wǎng)絡(luò)最大流問題流和可行流,流：網(wǎng)絡(luò)上某些弧的一組負(fù)載量，?。╲i，vj）的負(fù)載量記作f（vi，vj），簡記為fij。若

22、網(wǎng)絡(luò)上所有負(fù)載fij=0，則稱這個流為零流。 可行流：滿足下面條件的一組流稱為可行流。 容量限制：0 fij cij 中間點(diǎn)平衡： 中間點(diǎn)總流入量 = 總流出量 網(wǎng)絡(luò)最大流：就是流量最大的可行流，用v(f)表示從s到t的流量，網(wǎng)絡(luò)最大流問題實(shí)際上就是要求max v(f)= 。是線性規(guī)劃問題。,第六章 圖與網(wǎng)絡(luò)分析,41,第六章 圖與網(wǎng)絡(luò)分析,割：將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，使s到t的流中斷的一組弧的集合。,第四節(jié) 網(wǎng)絡(luò)最大流問題割和流量,42,3,4,1,t,2,,,,,,,2(0),,s,,,8(8),9(4),6(1),5(5),5(4),9(9),10(8),7(5)

23、,Cij(fij),,,K,,,第四節(jié) 網(wǎng)絡(luò)最大流問題增廣鏈,鏈的方向是從vs到vt，則s到t的弧叫正向弧，t到s的弧叫反向弧。 我們把網(wǎng)絡(luò)中fijcij的弧稱為飽和弧，fij

24、量。即：v*(f) = c*(V，V)。 求最大流的方法：從一個可行流f開始，尋求關(guān)于f的增廣鏈，沿增廣鏈增加可行流的流量得到流量大于f的可行流f*，重復(fù)這一過程，直到可行流無增廣鏈為止。 求最大流福德-?？松瓨?biāo)號算法。,第六章 圖與網(wǎng)絡(luò)分析,,44,t點(diǎn)得到標(biāo)號,第六章 圖與網(wǎng)絡(luò)分析,45,vs標(biāo)號為(0, ),開始,選擇已標(biāo)號的點(diǎn)vi: 若有非飽和弧(vi,vj)，則vj標(biāo)號(vi, (j))，其中(j) = min(i),uij； 若有非零弧(vj,vi)，則vj標(biāo)號(vi, (j))，其中(j) = min(i),fji。,t點(diǎn)未標(biāo)號，標(biāo)號過程中斷,,,,,,結(jié)束,2,1,,fij=3

25、,cij=5,,流量間隙： uij=c12-f12=2 定義(i)表示上一個標(biāo)號點(diǎn)到i點(diǎn)流量的最大允許調(diào)整值。,f +(t)增廣鏈正向弧 令f*= f (t)增廣鏈反向弧 f 非增廣鏈的弧,,,,,,,,,,6(0),6(1),第四節(jié) 網(wǎng)絡(luò)最大流問題最大流標(biāo)號算法實(shí)例(1),第六章 圖與網(wǎng)絡(luò)分析,46,46,3,4,1,t,2,,,,,,,2(0),,s,,,8(8),9(4),5(5),5(4),9(9),10(8),7(5),(0, ),(s, 2),(2, 2),(1, 2),,(3, 1),,,,,(4, 1),9(5),5(3),10(9),7(6),標(biāo)號vs,9(5),

26、第四節(jié) 網(wǎng)絡(luò)最大流問題最大流標(biāo)號算法實(shí)例(2),第六章 圖與網(wǎng)絡(luò)分析,47,6(0),3,4,1,t,2,,,,,,,2(0),,s,,,8(8),5(5),5(3),9(9),10(9),7(6),(0, ),(s, 1),(2, 1),(1, 1),,,,標(biāo)號過程中斷，最大流v*(f) = 14，最小割集為(2,4),(3,t),,給出一個初始的可行流零流fij=0,2,3,4,5,6,7,1,,,,,,,,,,,,,,,f=0,f=0,6(0),2(0),4(0),3(0),7(0),4(0),3(0),1(0),7(0),9(0),8(0),8(0),第六章 圖與網(wǎng)絡(luò)分析,48,,,找

27、到一條從1到7的增廣鏈f(1),2,3,4,5,6,7,1,,,,,,,,,,,,,,,f=0,,,,(1,8),6(0),2(0),4(0),3(0),7(0),4(0),3(0),1(0),7(0),9(0),8(0),8(0),(0, ),(1,7),(3,1),(2,6),f=0,(3,4),(6,1),第六章 圖與網(wǎng)絡(luò)分析,49,最大可調(diào)整量： = 1；調(diào)整鏈的流量：fij(1)=fij+ ,2,3,4,5,6,7,1,,,,,,,,,,,,,,,f=1,,(1,8),6(0),2(0),4(0),3(0),7(1),4(0),3(0),1(1),7(0),9(0),8(1),8(0

28、),(0, ),(1,6),(2,6),f=1,(3,4),(5,6),第六章 圖與網(wǎng)絡(luò)分析,50,,,(4,3),得到新的可行流f(2),最大可調(diào)整量： = 6；調(diào)整鏈的流量：fij(2)=fij(1)+ ,2,3,4,5,6,7,1,,,,,,,,,,,,,,,f=7,,(1,2),6(6),2(0),4(0),3(0),7(1),4(0),3(0),1(1),7(0),9(6),8(1),8(6),(0, ),(1,6),f=7,(3,4),(5,3),(4,3),(4,4),(6,3),第六章 圖與網(wǎng)絡(luò)分析,51,得到新的可行流f(3),,,,最大可調(diào)整量： = 3；調(diào)整鏈的流量：fi

29、j(3)=fij(2)+ ,2,3,4,5,6,7,1,,,,,,,,,,,,,,,f=0,,(1,2),6(6),2(0),4(0),3(0),7(4),4(3),3(3),1(1),7(0),9(6),8(4),8(6),(0, ),(1,3),f=0,(3,1),(5,1),(4,1),第六章 圖與網(wǎng)絡(luò)分析,52,得到新的可行流f(4),,,,最大可調(diào)整量： = 1；調(diào)整鏈的流量：fij(4)=fij(3)+ ,,,2,3,4,5,6,7,1,,,,,,,,,,,,,,,(1,2),6(6),2(0),4(1),3(0),7(5),4(4),3(3),1(1),7(0),9(7),8(4

30、),8(6),(0, ),(1,2),f=11,第六章 圖與網(wǎng)絡(luò)分析,53,f=11,已求得最大流v* (f) = c25+c34+c36 = 11,,,,最小割 = (2,5),(3,4),(3, 6),第四節(jié) 網(wǎng)絡(luò)最大流問題最大流最小割的意義,網(wǎng)絡(luò)中容量決定了網(wǎng)絡(luò)的通過能力，最小割是網(wǎng)絡(luò)的瓶頸，要提高網(wǎng)絡(luò)的運(yùn)輸能力，首要問題就是要改造最小割的通過能力。 最大流問題應(yīng)用極為廣泛，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流、供水系統(tǒng)中有水流，金融系統(tǒng)中有現(xiàn)金流，通訊系統(tǒng)中有信息流。 典型應(yīng)用匹配問題。,第六章 圖與網(wǎng)絡(luò)分析,54,第五節(jié) 最小費(fèi)用流問題,最小費(fèi)用流問題：在一個關(guān)于流的網(wǎng)絡(luò)中，人們

31、不僅需要流達(dá)到一定的流量，而且每一個流量都有一定的費(fèi)用，每條弧單位流量費(fèi)用不一樣。流走的路線不同，總的費(fèi)用不一樣。最小費(fèi)用流問題就是在限定流費(fèi)用基礎(chǔ)上，找出總費(fèi)用最小的可行流。 最小費(fèi)用流問題實(shí)際上是最短路問題和最大流問題的結(jié)合。 如取消費(fèi)用限制，就是最大流問題。 如將單位流量的費(fèi)用當(dāng)成是兩點(diǎn)間的距離，從s到t調(diào)運(yùn)一個單位流量的最小費(fèi)用，等價于求s到t的最短距離。,第六章 圖與網(wǎng)絡(luò)分析,55,第五節(jié) 最小費(fèi)用流問題最小費(fèi)用流的規(guī)劃描述,設(shè)網(wǎng)絡(luò)有n個點(diǎn)，令fij為弧(i,j)上的流量，cij為弧的容量，dij為弧通過單位流量的費(fèi)用，si代表i點(diǎn)的供應(yīng)量或需求量。ss大于0，st小于0，中間點(diǎn)si

32、 =0，當(dāng)供需平衡（即 si =0）時，將各發(fā)點(diǎn)調(diào)運(yùn)到各收點(diǎn)，總費(fèi)用最小問題的線性規(guī)劃模型為：,第六章 圖與網(wǎng)絡(luò)分析,56,,第五節(jié) 最小費(fèi)用流問題最小費(fèi)用流的圖形表示,第六章 圖與網(wǎng)絡(luò)分析,57,s2=-2,s4=3,s3=5,s5=-6,s6=-5,s1=5,d24=5,d46=1,d13=3,d35=2,d56=4,d34=4,d12=6,2,3,4,5,6,1,,,,,,,,,,,,,,dij 單位流量的費(fèi)用,若給定容量網(wǎng)絡(luò)G=(V,E,C)，除給出邊((vi , vj )E）上的容量（cij C）外，還給出流量的費(fèi)用 dij0，記為G=(V,E,C,d)，求G的一個可行流 f=fij

33、 ，在總的流量W(f)=a(常數(shù))的情況下，使 =,第五節(jié) 最小費(fèi)用流問題最小費(fèi)用流的一般描述,第六章 圖與網(wǎng)絡(luò)分析,58,,,如要求可行流f必須是最大流，就是最小費(fèi)用最大流問題。,第五節(jié) 最小費(fèi)用流問題最小費(fèi)用流的算法,最小費(fèi)用流的算法主要有兩種： 原始算法 對偶算法 狄克斯拉算法適用于權(quán)大于等于0的網(wǎng)絡(luò)。對偶算法中經(jīng)常會出現(xiàn)權(quán)小于0的情況，因此在介紹對偶算法之前我們首先要介紹最短路的另一種算法逐次逼近算法。,第六章 圖與網(wǎng)絡(luò)分析,59,第五節(jié) 最小費(fèi)用流問題逐次逼近算法(1),狄克斯拉算法計算s到t的最短路wst =minwss+dst,wss+ds1 =8,5=5。

34、 而實(shí)際上s到t的最短路應(yīng)該是(s,1),(1,t)， wst= 8 5 = 3。,第六章 圖與網(wǎng)絡(luò)分析,60,s,1,t,,,,Ls=0,Lt=5,-5,5,8,逐次逼近算法與狄克斯拉算法基本思想一致 假定(1，2)，(2，3)，(3，4)是點(diǎn)1到4的最短路 則(1，2)，(2，3)是點(diǎn)1到3的最短路； (2，3)，(3，4)是點(diǎn)2到4的最短路；,第五節(jié) 最小費(fèi)用流問題逐次逼近算法(2),第六章 圖與網(wǎng)絡(luò)分析,61,第六章 圖與網(wǎng)絡(luò)分析,61,1,2,3,4,5,,,,,,第五節(jié) 最小費(fèi)用流問題逐次逼近算法(3),用wij表示i到j(luò)的最短距離，cij表示相鄰點(diǎn)i，j的距離，基于以上定理必有

35、w1j=min(w1i+cij)，i=1n。表示從1到j(luò)直接到達(dá)或經(jīng)過1個點(diǎn)到達(dá)的最短距離。 構(gòu)造算法流程： 令w1j(1) =c1j使用迭代公式w1j(k) =min(w1i(k-1)+cij)，j=1n。如進(jìn)行到第k步出現(xiàn)w1j(k) =w1j(k-1)，則算法結(jié)束。 k小于等于n-1。也就是說算法最多執(zhí)行n-1步。,第六章 圖與網(wǎng)絡(luò)分析,62,第五節(jié) 最小費(fèi)用流問題逐次逼近算法案例,第六章 圖與網(wǎng)絡(luò)分析,63,2,2,4,5,7,8,1,,,,,,,,3,6,,,,,,,5,4,3,7,4,6,4,3,2,1,2,3,求1到8的最短路,w1j(1) = c1j = 0,2,5, 3, ,

36、,,,第六章 圖與網(wǎng)絡(luò)分析,64,2,2,4,5,7,8,1,,,,,,,,3,6,,,,,,,5,4,3,7,4,6,4,3,2,1,2,3,w1j(2) = minw1i(1) + cij = 0,2,0, 3, 6, 11, , ,w1j(2) = c1j = 0,2,0, 3, 6, 11, , ,第六章 圖與網(wǎng)絡(luò)分析,65,2,2,4,5,7,8,1,,,,,,,,3,6,,,,,,,5,4,3,7,4,6,4,3,2,1,2,3,w1j(3) = minw1i(2) + cij = 0,2,0, 3, 6, 6, , 9,第五節(jié) 最小費(fèi)用流問題對偶算法(1),求最小費(fèi)用流的基本思想

37、是：從零流f(0)開始，以費(fèi)用作為邊的長度，用最短路方法，求出增廣鏈，調(diào)整流量，使可行流逐步達(dá)到要求的流量。 G=(V,E,C,d)，f為G的一個可行流 ，為關(guān)于f的增廣鏈，d()= 稱為鏈的費(fèi)用。 若*是s到t增廣鏈中費(fèi)用最小的，稱*是最小費(fèi)用增廣鏈。,第六章 圖與網(wǎng)絡(luò)分析,66,第五節(jié) 最小費(fèi)用流問題對偶算法(2),+ = (s,1),(2,3),(3,4),(5,t) - = (2,1), (5,4) d() = (3+4+1+6) (5+7) = 2,第六章 圖與網(wǎng)絡(luò)分析,67,1,2,3,4,,,,s,5,t,,,,3,5,4,1,7,6,第五節(jié) 最小費(fèi)用流問題對偶算法(

38、3),長度網(wǎng)絡(luò)： 設(shè)網(wǎng)絡(luò)G=(V,E,C,d)有可行流f，保持網(wǎng)絡(luò)各點(diǎn)不變，用兩條方向相反的弧來代替*上的弧。 如(vi , vj )E，令Lij= 如(vj , vi )為原網(wǎng)絡(luò)邊的反向弧，則令 Lji=,第六章 圖與網(wǎng)絡(luò)分析,68,,,第五節(jié) 最小費(fèi)用流問題對偶算法(4),取零流為初始可行流，即f(0)=fij=0 若有f(k-1)，流量為W(f(k-1) )

39、-1) )+，若流量=a則算法結(jié)束。否則執(zhí)行第二步。,第六章 圖與網(wǎng)絡(luò)分析,69,第五節(jié) 最小費(fèi)用流問題對偶算法實(shí)例,第六章 圖與網(wǎng)絡(luò)分析,70,1,2,3,t,s,5(2),8(1),10(3),2(6),4(2),10(4),第六章 圖與網(wǎng)絡(luò)分析,70,在上圖所示的運(yùn)輸網(wǎng)絡(luò)上求流量為10的最小費(fèi)用流。 弧上給出了弧的容量和單位費(fèi)用，即cij(dij)。,,,,,,,,7(1),Cij(dij),,從f(0)開始，構(gòu)造L(f(0))，權(quán)dij0，可用狄克斯拉算法求出最短路(s,2),(2,1),(1,t),第六章 圖與網(wǎng)絡(luò)分析,71,1,2,3,t,s,2,1,3,6,2,4, = min8

40、-0,5-0,7-0= 5,,,,,,,,1,Cs1=7,Cs2=8,C21=5,按照 = 5 調(diào)整增廣鏈流量得到f(1),第六章 圖與網(wǎng)絡(luò)分析,72,第六章 圖與網(wǎng)絡(luò)分析,72,1,2,3,t,s,5(5,2),8(5,1),10(0,3),2(0,6),4(0,2),10(0,4),W(f(1))=5<10， d(f(1))=51+ 52 + 51=20,,,,,,,,7(5,1),Cij(fij,dij),73,構(gòu)造長度網(wǎng)絡(luò)L(f(1)),第六章 圖與網(wǎng)絡(luò)分析,73,第六章 圖與網(wǎng)絡(luò)分析,1,2,3,t,s,-2,1,3,6,2,4,由于有負(fù)權(quán)，采用逐次逼近法求出最短路(s,1),(1,

41、t),,,,,,,,-1,,1,,-1,10(0,4),7(7,1), =min(cs1 fs1), (c1t f1t) =min(10 0),(7 5) = 2，調(diào)整增廣鏈流量得到f(2),第六章 圖與網(wǎng)絡(luò)分析,74,W(f(2))=7<10， d(f(2))=42+51+ 52 + 71=30,1,2,3,t,s,5(5,2),8(5,1),10(0,3),2(0,6),4(0,2),,,,,,,,7(5,1),Cij(fij，dij),,10(2,4),75,第六章 圖與網(wǎng)絡(luò)分析,75,構(gòu)造長度網(wǎng)絡(luò)L(f(2)),第六章 圖與網(wǎng)絡(luò)分析,75,第六章 圖與網(wǎng)絡(luò)分析,1,2,3,t,s,-2

42、,1,3,6,2,4,采用逐次逼近法求出最短路(s,2),(2,3) ,(3,t),,,,,,,,-1,,-1,,-4, = min8 5,10 0,4 0 = 3，調(diào)整增廣鏈流量得到f(3),第六章 圖與網(wǎng)絡(luò)分析,76,W(f(3))=10，f(3)就是所求最小費(fèi)用流，d(f(3))=42+81+ 52+ 33 + 32+ 71=48,1,2,3,t,s,5(5,2),8(5,1),10(0,3),2(0,6),4(0,2),10(2,4),,,,,,,,7(7,1),8(8,1),10(3,3),4(3,2),第六章 圖與網(wǎng)絡(luò)分析本章小結(jié)(1),樹：無圈的連通圖。 樹中必然存在次為1的點(diǎn)

43、n個頂點(diǎn)的樹，邊為n-1條 有n個頂點(diǎn)，n-1條邊的連通圖必然是樹。 最小部分樹：樹枝總長最小的部分樹。 避圈法 破圈法,第六章 圖與網(wǎng)絡(luò)分析,77,第六章 圖與網(wǎng)絡(luò)分析本章小結(jié)(2),最短路問題： 狄克斯拉算法 適用于權(quán)大于等于0的網(wǎng)絡(luò)。 能夠計算出網(wǎng)絡(luò)任意兩點(diǎn)間的最短距離。 矩陣算法 適用于任何網(wǎng)絡(luò)。 能夠計算出網(wǎng)絡(luò)所有點(diǎn)間的最短距離。,第六章 圖與網(wǎng)絡(luò)分析,78,第六章 圖與網(wǎng)絡(luò)分析本章小結(jié)(3),最大流問題 可行流 增廣鏈 正向弧 f 0 最大流最小割定理 v*(f) = c*(V，V)。 最大流標(biāo)號算法,第六章 圖與網(wǎng)絡(luò)分析,79,,第六章 圖與網(wǎng)絡(luò)分析本章小結(jié)(4),最小費(fèi)用流問題 實(shí)際上是最短路問題和最大流問題的一種結(jié)合。 對偶算法 逐次逼近算法 長度網(wǎng)絡(luò),第六章 圖與網(wǎng)絡(luò)分析,80,