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

運(yùn)籌學(xué)第六章 圖與網(wǎng)絡(luò)分析,機(jī)電工程學(xué)院 工業(yè)工程系 周宇鵬 辦公電話：86417778-604 手機(jī)：13936135705 Email：,哥尼斯堡七橋問(wèn)題,第六章 圖與網(wǎng)絡(luò)分析,2,表示過(guò)橋的費(fèi)用,表示橋單位時(shí)間最多通過(guò)的車輛數(shù),圖的基本概念 樹圖 最短路徑問(wèn)題 網(wǎng)絡(luò)最大流問(wèn)題 網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題,第六章 圖與網(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é) 圖的基本概念（1）,圖: 由點(diǎn)和點(diǎn)與點(diǎn)之間的連線組成，是點(diǎn)和線的集合。 若點(diǎn)與點(diǎn)之間的連線沒(méi)有方向，稱為邊，由此構(gòu)成的圖為無(wú)向圖。表示為：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)均有邊相連的簡(jiǎn)單圖。 環(huán)：端點(diǎn)相重的邊或弧。 多重邊：兩點(diǎn)間有多條邊。 簡(jiǎn)單圖：無(wú)環(huán)和多重邊的圖。 完全圖的特性 含有n個(gè)頂點(diǎn)的完全圖，其邊數(shù)有 條。,第六章 圖與網(wǎng)絡(luò)分析,8,第一節(jié) 圖的基本概念（5）,偶圖（二分圖） 圖的頂點(diǎn)能分為兩個(gè)互不相交的非空集合V1和V2，使在同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，這樣的圖我們稱為偶圖。 V1和V2間每一對(duì)不同的頂點(diǎn)都相鄰，這樣圖稱為完全偶圖。如V1中有m個(gè)頂點(diǎn)，V2中有n個(gè)頂點(diǎn)，其邊數(shù)共mn條。,第六章 圖與網(wǎng)絡(luò)分析,9,第二節(jié) 樹圖樹的定義和性質(zhì),樹：無(wú)圈的連通圖。 樹的性質(zhì)： 樹是簡(jiǎn)單圖（無(wú)環(huán)和多重邊） 樹中必然存在次為1的點(diǎn) n個(gè)頂點(diǎn)的樹，邊為n-1條 有n個(gè)頂點(diǎn)，n-1條邊的連通圖必然是樹。,第六章 圖與網(wǎng)絡(luò)分析,10,懸掛邊,懸掛點(diǎn),樹枝,根,葉子,第二節(jié) 樹圖最小部分樹,子圖： 圖G1=（V1，E1）和G2=（V2，E2），如V2 V1且E2 E1，則稱G2為G1的子圖。 部分圖：如V2= V1且E2 E1，則稱G2為G1的部分圖。 部分樹： G2為G1的部分圖且G2是樹，則稱G2為G1的部分樹。 最小部分樹：樹枝總長(zhǎng)最小的部分樹稱為最小部分樹（最小支撐樹）。,第六章 圖與網(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的最小部分樹中。 推論：把圖G分為V和V兩個(gè)集合，兩集合間連線的最短邊必定包含于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ù)字代表道路的長(zhǎng)度。 求：沿道路架設(shè)電線，使所有城市都能通上電，如何架設(shè)使總的線路長(zhǎng)度最短。,第二節(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é) 樹圖破圈法,任選一個(gè)圈，從圈中去掉權(quán)最大的一條邊。在余下的圖中重復(fù)這個(gè)步驟，直到得到一不含圈的連通圖為止。,第六章 圖與網(wǎng)絡(luò)分析,15,S,D,A,T,B,C,E,2,2,1,3,5,1,第三節(jié) 最短路問(wèn)題,賦權(quán)無(wú)向圖D中的兩個(gè)頂點(diǎn)vs和vt，設(shè)P是由vs到vt的一條路，把P中所有邊的權(quán)之和稱為路P的權(quán)，記為d(P)。如果路P*的權(quán)d(P*)是由vs到vt的所有路的權(quán)中的最小者，則稱P*是從vs到vt的最短路。最短路P*的權(quán)d(P*)稱為從vs到vt的距離，記為L(zhǎng)(vs,vt)。 狄克斯拉算法（Dijkstra） 矩陣算法,第六章 圖與網(wǎng)絡(luò)分析,16,第三節(jié) 最短路問(wèn)題狄克斯拉算法（1）,第六章 圖與網(wǎng)絡(luò)分析,17,狄克斯拉算法也稱雙標(biāo)號(hà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é) 最短路問(wèn)題狄克斯拉算法（2）,狄克斯拉算法流程： 用dij表示相鄰點(diǎn)vi與vj的距離，若vi與vj不相鄰，則 dij= ，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)號(hào)。 找出與s點(diǎn)相鄰點(diǎn)中距離最短的一點(diǎn)，假設(shè)是r，則Lsr= Lss+ dsr，將Lsr的值標(biāo)示在點(diǎn)r上。r點(diǎn)被標(biāo)號(hào)。 從已標(biāo)號(hào)的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)，如果有一點(diǎn)p滿足：Lsp = minLss + dsp，Lsr + drp ，則用Lsp的值對(duì)p點(diǎn)標(biāo)號(hào)。 重復(fù)第3步，直至t點(diǎn)被標(biāo)號(hào)。,第六章 圖與網(wǎng)絡(luò)分析,18,第三節(jié) 最短路問(wèn)題狄克斯拉算法案例一(1),第六章 圖與網(wǎng)絡(luò)分析,19,L1=0,5,6,2,4,7,3,2,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é) 最短路問(wèn)題狄克斯拉算法案例一(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é) 最短路問(wèn)題狄克斯拉算法案例一(3),第六章 圖與網(wǎng)絡(luò)分析,21,L1=0,5,6,2,4,7,3,2,2,4,6,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é) 最短路問(wèn)題狄克斯拉算法案例一(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=L4=L5,第三節(jié) 最短路問(wèn)題狄克斯拉算法案例一(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èn)題狄克斯拉算法案例二,第六章 圖與網(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ò)。對(duì)有向圖、無(wú)向圖都適用。 在有向圖中： 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,minc12,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,第六章 圖與網(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+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, 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,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，長(zhǎng)度為10。 1到3的最短距離為8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,第三節(jié) 最短路問(wèn)題矩陣算法,雙標(biāo)號(hào)法能夠計(jì)算出網(wǎng)絡(luò)中任意一點(diǎn)到其他點(diǎn)的最短距離。 矩陣算法可以一次計(jì)算出網(wǎng)絡(luò)所有點(diǎn)之間的最短距離。 矩陣算法的基本思想與雙標(biāo)號(hà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,6,第三節(jié) 最短路問(wèn)題矩陣算法（第一步）,第六章 圖與網(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é) 最短路問(wèn)題矩陣算法（第二步）,先考慮i到j(luò)有一個(gè)中間點(diǎn)時(shí)的情況。 v1到v2的最短距離應(yīng)該是mind11+d12, d12+d22, d13+d32, d14+d42, d15+d52, d16+d62, d17+d72。即min（d1r+dr2），r=1，2，7。 因此我們可以構(gòu)造一個(gè)新矩陣D（1），令dij=mindir+drj，r=1p。 那么這個(gè)矩陣就給出了網(wǎng)絡(luò)中直接到達(dá)及經(jīng)過(guò)一個(gè)中間點(diǎn)的最短距離。,35,第六章 圖與網(wǎng)絡(luò)分析,36,5,2,7,12,6,第三節(jié) 最短路問(wèn)題矩陣算法（第三步）,在D（1）的基礎(chǔ)上，構(gòu)造一個(gè)新矩陣D（2），令dij（2）=mindir（1）+drj （1），r=1p。 這個(gè)矩陣就表示出了網(wǎng)絡(luò)中任意兩點(diǎn)，直接到達(dá)；經(jīng)過(guò)一個(gè)點(diǎn)、兩個(gè)點(diǎn)和三個(gè)點(diǎn)到達(dá)的最短距離。 dir（1）表示i直接到r，或i經(jīng)過(guò)pa到r， a=1p； drj（1）表示r直接到j(luò)，或r經(jīng)過(guò)pb到j(luò)， b=1p； 如果r=i，j：dij（2）表示i直接到j(luò)，或i經(jīng)過(guò)一點(diǎn)到j(luò)； 如i直接到r，r直接到j(luò)： dij（2）表示i經(jīng)過(guò)r到j(luò)； 如i經(jīng)過(guò)pa到r，或r經(jīng)過(guò)pb到j(luò)： dij（2）表示i經(jīng)過(guò)兩點(diǎn)到j(luò)； 如i經(jīng)過(guò)pa到r，且r經(jīng)過(guò)pb到j(luò)： dij（2）表示i經(jīng)過(guò)三點(diǎn)到j(luò)；,第六章 圖與網(wǎng)絡(luò)分析,37,第三節(jié) 最短路問(wèn)題矩陣算法（第k步）,通過(guò)歸納可知：dij(k) =mindir(k-1)+drj(k-1)，能夠表示網(wǎng)絡(luò)中任意兩點(diǎn)直接到達(dá)，或經(jīng)過(guò)一個(gè)、兩個(gè)（2k-1）個(gè)中間點(diǎn)到達(dá)的最短距離。 假設(shè)網(wǎng)絡(luò)有p個(gè)頂點(diǎn)，那么矩陣算法的結(jié)束條件是：,第六章 圖與網(wǎng)絡(luò)分析,38,第六章 圖與網(wǎng)絡(luò)分析,39,5,2,7,第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題,弧的容量：對(duì)網(wǎng)絡(luò)上的每條弧給出一個(gè)最大通過(guò)能力c（vi，vj），簡(jiǎn)記為cij，c稱為弧的容量。 容量網(wǎng)絡(luò)：給定了弧的容量的有向圖D=（V，A，C）叫做一個(gè)容量網(wǎng)絡(luò)。 容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)s（源點(diǎn)），一個(gè)收點(diǎn)t（匯點(diǎn)）。其他點(diǎn)稱為中間點(diǎn)。,第六章 圖與網(wǎng)絡(luò)分析,40,s,t,s,t,第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題流和可行流,流：網(wǎng)絡(luò)上某些弧的一組負(fù)載量，弧（vi，vj）的負(fù)載量記作f（vi，vj），簡(jiǎn)記為fij。若網(wǎng)絡(luò)上所有負(fù)載fij=0，則稱這個(gè)流為零流。 可行流：滿足下面條件的一組流稱為可行流。 容量限制：0 fij cij 中間點(diǎn)平衡： 中間點(diǎn)總流入量 = 總流出量 網(wǎng)絡(luò)最大流：就是流量最大的可行流，用v(f)表示從s到t的流量，網(wǎng)絡(luò)最大流問(wèn)題實(shí)際上就是要求max v(f)= 。是線性規(guī)劃問(wèn)題。,第六章 圖與網(wǎng)絡(luò)分析,41,第六章 圖與網(wǎng)絡(luò)分析,割：將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，使s到t的流中斷的一組弧的集合。,第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題割和流量,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),Cij(fij),K,第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題增廣鏈,鏈的方向是從vs到vt，則s到t的弧叫正向弧，t到s的弧叫反向弧。 我們把網(wǎng)絡(luò)中fijcij的弧稱為飽和弧，fij<cij的弧稱為非飽和??； 增廣鏈：設(shè)f是一個(gè)可行流，是從vs到vt的一條鏈，若滿足正向弧都是非飽和弧,反向弧都是非零流弧,則稱是可行流f的一條增廣鏈。,第六章 圖與網(wǎng)絡(luò)分析,43,s,1,2,t,3,f1 c1,f4 c4,f2 0,f3 0,c2 f2 0,0 f4 c4,第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題最大流最小割定理,可行流f是最大流的必要條件是圖中不存在關(guān)于f的增廣鏈。 網(wǎng)絡(luò)中s到t的最大流量等于網(wǎng)絡(luò)最小割集的容量。即：v*(f) = c*(V，V)。 求最大流的方法：從一個(gè)可行流f開始，尋求關(guān)于f的增廣鏈，沿增廣鏈增加可行流的流量得到流量大于f的可行流f*，重復(fù)這一過(guò)程，直到可行流無(wú)增廣鏈為止。 求最大流福德-?？松瓨?biāo)號(hào)算法。,第六章 圖與網(wǎng)絡(luò)分析,44,t點(diǎn)得到標(biāo)號(hào),第六章 圖與網(wǎng)絡(luò)分析,45,vs標(biāo)號(hào)為(0, ),開始,選擇已標(biāo)號(hào)的點(diǎn)vi: 若有非飽和弧(vi,vj)，則vj標(biāo)號(hào)(vi, (j)，其中(j) = min(i),uij； 若有非零弧(vj,vi)，則vj標(biāo)號(hào)(vi, (j)，其中(j) = min(i),fji。,t點(diǎn)未標(biāo)號(hào)，標(biāo)號(hào)過(guò)程中斷,結(jié)束,2,1,fij=3,cij=5,流量間隙： uij=c12-f12=2 定義(i)表示上一個(gè)標(biāo)號(hào)點(diǎn)到i點(diǎn)流量的最大允許調(diào)整值。,f +(t)增廣鏈正向弧 令f*= f (t)增廣鏈反向弧 f 非增廣鏈的弧,6(0),6(1),第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題最大流標(biāo)號(hà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)號(hào)vs,9(5),第四節(jié) 網(wǎng)絡(luò)最大流問(wèn)題最大流標(biāo)號(hà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)號(hào)過(guò)程中斷，最大流v*(f) = 14，最小割集為(2,4),(3,t),給出一個(gè)初始的可行流零流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,找到一條從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),(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)整鏈的流量：fij(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),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èn)題最大流最小割的意義,網(wǎng)絡(luò)中容量決定了網(wǎng)絡(luò)的通過(guò)能力，最小割是網(wǎng)絡(luò)的瓶頸，要提高網(wǎng)絡(luò)的運(yùn)輸能力，首要問(wèn)題就是要改造最小割的通過(guò)能力。 最大流問(wèn)題應(yīng)用極為廣泛，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流、供水系統(tǒng)中有水流，金融系統(tǒng)中有現(xiàn)金流，通訊系統(tǒng)中有信息流。 典型應(yīng)用匹配問(wèn)題。,第六章 圖與網(wǎng)絡(luò)分析,54,第五節(jié) 最小費(fèi)用流問(wèn)題,最小費(fèi)用流問(wèn)題：在一個(gè)關(guān)于流的網(wǎng)絡(luò)中，人們不僅需要流達(dá)到一定的流量，而且每一個(gè)流量都有一定的費(fèi)用，每條弧單位流量費(fèi)用不一樣。流走的路線不同，總的費(fèi)用不一樣。最小費(fèi)用流問(wèn)題就是在限定流費(fèi)用基礎(chǔ)上，找出總費(fèi)用最小的可行流。 最小費(fèi)用流問(wèn)題實(shí)際上是最短路問(wèn)題和最大流問(wèn)題的結(jié)合。 如取消費(fèi)用限制，就是最大流問(wèn)題。 如將單位流量的費(fèi)用當(dāng)成是兩點(diǎn)間的距離，從s到t調(diào)運(yùn)一個(gè)單位流量的最小費(fèi)用，等價(jià)于求s到t的最短距離。,第六章 圖與網(wǎng)絡(luò)分析,55,第五節(jié) 最小費(fèi)用流問(wèn)題最小費(fèi)用流的規(guī)劃描述,設(shè)網(wǎng)絡(luò)有n個(gè)點(diǎn)，令fij為弧(i,j)上的流量，cij為弧的容量，dij為弧通過(guò)單位流量的費(fèi)用，si代表i點(diǎn)的供應(yīng)量或需求量。ss大于0，st小于0，中間點(diǎn)si =0，當(dāng)供需平衡（即 si =0）時(shí)，將各發(fā)點(diǎn)調(diào)運(yùn)到各收點(diǎn)，總費(fèi)用最小問(wèn)題的線性規(guī)劃模型為：,第六章 圖與網(wǎng)絡(luò)分析,56,第五節(jié) 最小費(fèi)用流問(wèn)題最小費(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的一個(gè)可行流 f=fij ，在總的流量W(f)=a(常數(shù))的情況下，使 =,第五節(jié) 最小費(fèi)用流問(wèn)題最小費(fèi)用流的一般描述,第六章 圖與網(wǎng)絡(luò)分析,58,如要求可行流f必須是最大流，就是最小費(fèi)用最大流問(wèn)題。,第五節(jié) 最小費(fèi)用流問(wèn)題最小費(fèi)用流的算法,最小費(fèi)用流的算法主要有兩種： 原始算法 對(duì)偶算法 狄克斯拉算法適用于權(quán)大于等于0的網(wǎng)絡(luò)。對(duì)偶算法中經(jīng)常會(huì)出現(xiàn)權(quán)小于0的情況，因此在介紹對(duì)偶算法之前我們首先要介紹最短路的另一種算法逐次逼近算法。,第六章 圖與網(wǎng)絡(luò)分析,59,第五節(jié) 最小費(fèi)用流問(wèn)題逐次逼近算法(1),狄克斯拉算法計(jì)算s到t的最短路wst =minwss+dst,wss+ds1 =8,5=5。 而實(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)用流問(wèn)題逐次逼近算法(2),第六章 圖與網(wǎng)絡(luò)分析,61,第六章 圖與網(wǎng)絡(luò)分析,61,1,2,3,4,5,第五節(jié) 最小費(fèi)用流問(wèn)題逐次逼近算法(3),用wij表示i到j(luò)的最短距離，cij表示相鄰點(diǎn)i，j的距離，基于以上定理必有w1j=min(w1i+cij)，i=1n。表示從1到j(luò)直接到達(dá)或經(jīng)過(guò)1個(gè)點(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。也就是說(shuō)算法最多執(zhí)行n-1步。,第六章 圖與網(wǎng)絡(luò)分析,62,第五節(jié) 最小費(fèi)用流問(wèn)題逐次逼近算法案例,第六章 圖與網(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, ,第六章 圖與網(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)用流問(wèn)題對(duì)偶算法(1),求最小費(fèi)用流的基本思想是：從零流f(0)開始，以費(fèi)用作為邊的長(zhǎng)度，用最短路方法，求出增廣鏈，調(diào)整流量，使可行流逐步達(dá)到要求的流量。 G=(V,E,C,d)，f為G的一個(gè)可行流 ，為關(guān)于f的增廣鏈，d()= 稱為鏈的費(fèi)用。 若*是s到t增廣鏈中費(fèi)用最小的，稱*是最小費(fèi)用增廣鏈。,第六章 圖與網(wǎng)絡(luò)分析,66,第五節(jié) 最小費(fèi)用流問(wèn)題對(duì)偶算法(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)用流問(wèn)題對(duì)偶算法(3),長(zhǎng)度網(wǎng)絡(luò)： 設(shè)網(wǎng)絡(luò)G=(V,E,C,d)有可行流f，保持網(wǎng)絡(luò)各點(diǎn)不變，用兩條方向相反的弧來(lái)代替*上的弧。 如(vi , vj )E，令Lij= 如(vj , vi )為原網(wǎng)絡(luò)邊的反向弧，則令 Lji=,第六章 圖與網(wǎng)絡(luò)分析,68,第五節(jié) 最小費(fèi)用流問(wèn)題對(duì)偶算法(4),取零流為初始可行流，即f(0)=fij=0 若有f(k-1)，流量為W(f(k-1) )<a，構(gòu)造L(f(k-1) 求長(zhǎng)度網(wǎng)絡(luò)L(f(k-1)從s到t的最短路。若不存在，則f(k-1)為最大流，不存在流量等于a的可行流，算法終止。若存在則繼續(xù)執(zhí)行第4步。 在最短路的增廣鏈上調(diào)整流量： = f(k)的流量為W(f(k-1) )+，若流量=a則算法結(jié)束。否則執(zhí)行第二步。,第六章 圖與網(wǎng)絡(luò)分析,69,第五節(jié) 最小費(fèi)用流問(wèn)題對(duì)偶算法實(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-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)造長(zhǎng)度網(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,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)造長(zhǎng)度網(wǎng)絡(luò)L(f(2),第六章 圖與網(wǎng)絡(luò)分析,75,第六章 圖與網(wǎng)絡(luò)分析,1,2,3,t,s,-2,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),樹：無(wú)圈的連通圖。 樹中必然存在次為1的點(diǎn) n個(gè)頂點(diǎn)的樹，邊為n-1條 有n個(gè)頂點(diǎn)，n-1條邊的連通圖必然是樹。 最小部分樹：樹枝總長(zhǎng)最小的部分樹。 避圈法 破圈法,第六章 圖與網(wǎng)絡(luò)分析,77,第六章 圖與網(wǎng)絡(luò)分析本章小結(jié)(2),最短路問(wèn)題： 狄克斯拉算法 適用于權(quán)大于等于0的網(wǎng)絡(luò)。 能夠計(jì)算出網(wǎng)絡(luò)任意兩點(diǎn)間的最短距離。 矩陣算法 適用于任何網(wǎng)絡(luò)。 能夠計(jì)算出網(wǎng)絡(luò)所有點(diǎn)間的最短距離。,第六章 圖與網(wǎng)絡(luò)分析,78,第六章 圖與網(wǎng)絡(luò)分析本章小結(jié)(3),最大流問(wèn)題 可行流 增廣鏈 正向弧 f 0 最大流最小割定理 v*(f) = c*(V，V)。 最大流標(biāo)號(hào)算法,第六章 圖與網(wǎng)絡(luò)分析,79,第六章 圖與網(wǎng)絡(luò)分析本章小結(jié)(4),最小費(fèi)用流問(wèn)題 實(shí)際上是最短路問(wèn)題和最大流問(wèn)題的一種結(jié)合。 對(duì)偶算法 逐次逼近算法 長(zhǎng)度網(wǎng)絡(luò),第六章 圖與網(wǎng)絡(luò)分析,80,