第6章圖與網(wǎng)絡(luò)分析

1、第第1頁頁運運 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析Graphs and Network AnalysisGraphs and Network Analysis第第2頁頁Leonhard Euler(公元1707-1783年)歐拉1707年出生在瑞士的巴塞爾城，13歲就進(jìn)巴塞爾大學(xué)讀書，得到當(dāng)時最有名的數(shù)學(xué)家約翰.伯努利的精心指導(dǎo)。他從19歲開始發(fā)表論文，直到76歲。幾乎每一個數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)

2、，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等。據(jù)統(tǒng)計他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%。 1733年，年僅26歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授。1741年到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長，直到1766年，重回彼得堡，沒有多久，完全失明歐拉在數(shù)學(xué)上的建樹很多，對著名的哥尼斯堡七橋問題的解答開創(chuàng)了圖論的研究。第第3頁頁哥尼斯堡七橋問題能否從某個地方出發(fā)，穿過所有的橋各一次能否從某個地方出發(fā)，穿過所有的橋各一次后再回到出發(fā)點。后再回到出發(fā)點。ACDB圖論模型第第4頁頁|6.1 圖與子

3、圖圖與子圖|6.2 圖的連通性圖的連通性|6.3 樹與支撐樹樹與支撐樹|6.4 最小樹問題最小樹問題|6.5 最短有向最短有向路路問題問題|6.6 最大最大流流問題問題|6.7 最小費用最小費用流流問題問題|6.8 最大最大對集對集問題問題第第5頁頁|圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò) 無向圖的基本概念無向圖的基本概念 有向圖和網(wǎng)絡(luò)有向圖和網(wǎng)絡(luò)|關(guān)聯(lián)矩陣和鄰接矩陣關(guān)聯(lián)矩陣和鄰接矩陣 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣 鄰接矩陣鄰接矩陣 主要結(jié)論主要結(jié)論|子圖子圖 第第6頁頁1n1n 圖6.1.12n3n4n11e12e14e24e23e34e34e5n關(guān)聯(lián)關(guān)聯(lián)：一條邊的端點稱為與這條邊的關(guān)聯(lián)：一條邊的端點稱為與這條邊的關(guān)聯(lián)鄰接鄰

4、接：與同一條邊關(guān)聯(lián)的端點稱為是鄰接的，同時如果兩條邊：與同一條邊關(guān)聯(lián)的端點稱為是鄰接的，同時如果兩條邊 有一個公共端點，則稱這兩條邊是鄰接的有一個公共端點，則稱這兩條邊是鄰接的有限圖有限圖：任何圖：任何圖G=(N,E),G=(N,E),若若N N和和E E都是有限集合都是有限集合, ,則稱則稱G G為為空圖空圖：沒有任何邊的圖：沒有任何邊的圖平凡圖平凡圖：只有一個點的圖：只有一個點的圖簡單圖簡單圖：一個圖：一個圖, ,既沒有環(huán)既沒有環(huán), ,也沒有重邊也沒有重邊, ,則稱為則稱為 例如例如:(a):(a)是是 一簡單圖一簡單圖, ,但但(b)(b)就不是簡單圖就不是簡單圖. .(a)(b)續(xù)1第

5、第8頁頁完全圖完全圖：每一對點之間均有一條邊相連的圖：每一對點之間均有一條邊相連的圖二分圖二分圖 G=G=( (N,EN,E) )：存在的一個二分劃存在的一個二分劃( (S S, ,T T) )，使得使得G G的的每條邊有一個端點在每條邊有一個端點在S S中，另一個端點在中，另一個端點在T T中中完全二分圖完全二分圖 G=(S,T,E)G=(S,T,E)：S S中的每個點與中的每個點與T T中的每個點中的每個點都相連的簡單二分圖都相連的簡單二分圖簡單圖簡單圖G G的補圖的補圖 : :與與G G有相同頂點集合的簡單圖，且補有相同頂點集合的簡單圖，且補圖中的兩個點相鄰當(dāng)且僅當(dāng)它們在圖中的兩個點相鄰

6、當(dāng)且僅當(dāng)它們在G G中不相鄰中不相鄰圖6.1.3(b)(a)續(xù)23n1n4n2n續(xù)3第第10頁頁7BADC2358設(shè)G是一個圖（有向圖），若對G的每條邊（?。┒假x予一個實數(shù)，并稱為這條邊（?。┑臋?quán)，則G連同它邊（弧）上的權(quán)稱為一個（有向）網(wǎng)絡(luò)或賦權(quán)（有向）圖，記為G=(N,E,W).1543212224443圖6.4.1續(xù)4無向完全圖無向完全圖：在無向圖中，如果任意兩個頂點之間：在無向圖中，如果任意兩個頂點之間存在邊。存在邊。 有向完全圖有向完全圖：在有向圖中，如果任意兩頂點之間都：在有向圖中，如果任意兩頂點之間都有存在方向互為相反的兩條弧。有存在方向互為相反的兩條弧。 含有含有n個頂點的無向

7、完全圖有個頂點的無向完全圖有多少多少條邊？條邊？含有含有n個頂點的有向完全圖有個頂點的有向完全圖有多少多少條??？條?。?0123012n(n-1)/2n(n-1)續(xù)5續(xù)6右圖的關(guān)聯(lián)矩陣是右圖的關(guān)聯(lián)矩陣是 右圖的關(guān)聯(lián)矩陣是右圖的關(guān)聯(lián)矩陣是 135241 111000002 100110003 010101104 001001015 00001011143211110000210111103010101140000101圖6.1.7圖6.1.8續(xù)7續(xù)8圖（圖（6.1.76.1.7）的鄰接矩陣是）的鄰接矩陣是 圖（圖（6.1.86.1.8）的鄰接矩陣是）的鄰接矩陣是 0111010101110111

8、0101011105432154321 010000001100011043214321143213524圖6.1.7圖6.1.8續(xù)9第第16頁頁握手定理握手定理續(xù)10第第17頁頁續(xù)11第第18頁頁圖6.2.1:(1,2,3,4,2,3,5,6)是一條1,6路；(1,2,4,5,3,4,6)是一條1,6簡單路；(1,2,3,5,6）一條1,6初級路；(1,2,4,3,2,4,5,3,1)是一條回路；(1,2,3,4,5,3,1）是一條簡單回路；(1,2,4,5,3,1)是一條初級回路。165432圖6.2.11.圖的連通第第19頁頁點點i i和和j j點是點是連通的連通的：G G中存在一條中存

9、在一條ii，jj路路G G是是連通的連通的：G G中任意兩點都是連通的中任意兩點都是連通的 連通分支連通分支：G G的極大連通子圖的極大連通子圖 圖圖6.2.16.2.1中（中（a a）是連通圖；（）是連通圖；（b b）是一個具有）是一個具有三個連通分支的非連通圖。三個連通分支的非連通圖。 圖6.2.2（a）（b）第第20頁頁第第21頁頁有向圖有向圖G G中的一條有向路中的一條有向路：個點和弧的交錯序列：個點和弧的交錯序列 ( (n ni i, ,a aijij, ,n nj j, , ,n nk k, ,a aklkl, ,n nl l) )， 記為記為( (n ni i, ,n nl l)

10、 )有向路有向路 簡單有向路簡單有向路：弧不重的有向路：弧不重的有向路 初級有向路初級有向路：點不重的有向路：點不重的有向路 有向回路有向回路：至少包含一條弧且：至少包含一條弧且n ni i= =n nj j的的( (n ni i, ,n nj j) )有向路有向路 簡單有向回路簡單有向回路：弧不重的有向回路：弧不重的有向回路 初級有向回路初級有向回路：點不重的有向回路：點不重的有向回路第第22頁頁如下圖：(1,2,4,3,2,4,6)是一條(1,6)有向路; (1,2,4,5,3,4,6)是一條(1，6)簡單有向路; (1,2,3,4,6)是一條（1，6）初級有向路；(1,2,4,3,2,4

11、,5,3,1)是一條有向回路；(1,2,3,4,5,3,1)是一條簡單有向回路；(1,2,4,5,3,1)是一條初級有向回路。165432第第23頁頁點點i i和點和點j j是強連通的是強連通的：G G中存在一條中存在一條( (i,j)i,j)有向路有向路, ,也也存在一條存在一條( (j,i)j,i)有向路有向路G是強連通的是強連通的：G G中任意兩點都是強連通的中任意兩點都是強連通的 G的強連通分支的強連通分支：G G的極大連通子圖的極大連通子圖圖圖6.2.4中，（中，（a）是一個強連通分支，（）是一個強連通分支，（b）是一個）是一個具有三個強連通分支的非強連通圖。具有三個強連通分支的非強

12、連通圖。(a)(b)圖6.2.4第第24頁頁如何編寫判斷一個圖（有向圖）是否（強如何編寫判斷一個圖（有向圖）是否（強）連通的算法呢？）連通的算法呢？第第25頁頁第第26頁頁1765423圖6.2.5中2，4和6，7都是割邊圖6.2.6中，邊集2，1，2，4，2，3和邊集2，3，2，4，1，4，1，5均為割集15432圖6.2.5圖6.2.6第第27頁頁第第28頁頁1 1、樹及其性質(zhì)、樹及其性質(zhì)第第29頁頁-樹的性質(zhì)第第30頁頁-支撐樹及其性質(zhì)第第31頁頁|最小樹及其性質(zhì)最小樹及其性質(zhì)|求最小樹的求最小樹的KruskalKruskal算法算法 算法步驟算法步驟 算例算例 算法復(fù)雜性算法復(fù)雜性 |

13、求最小樹的求最小樹的DijkstraDijkstra算法（又稱算法（又稱PrimPrim算法）算法） 算法步驟算法步驟 算例算例 算法復(fù)雜性算法復(fù)雜性第第32頁頁第第33頁頁第第34頁頁DCBEAF251234192646382517例：例：第第35頁頁用用Kruskal算法求解下圖所示網(wǎng)絡(luò)的最小樹，其中每條算法求解下圖所示網(wǎng)絡(luò)的最小樹，其中每條邊上的數(shù)表示該邊的權(quán)值。邊上的數(shù)表示該邊的權(quán)值。 1543212224443圖6.4.1第第36頁頁154321154321215432122154321223第第37頁頁本算法遺留問題：本算法復(fù)雜性是如何算出來的？如何判斷加入一條邊后是否構(gòu)成回路？“

14、點的重新標(biāo)號”是什么意思？a) 按什么數(shù)據(jù)結(jié)構(gòu)存儲和如何編程才能使得此算法節(jié)省時間？第第38頁頁注：在許多教科書上此算法叫Prim算法第第39頁頁U=A U=A，F(xiàn) 例：例：DCBEAF251234192646381725U=A，F(xiàn)，C U=A，F(xiàn)，C，D U=A，F(xiàn)，C，D，E U=A，F(xiàn)，C，D，E，B 第第40頁頁例：例：DCBEAF251234192646381725(A, )(A, 34)(A, )(A, 46)(A, 19)(A, )第第41頁頁例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(F,25)(C

15、,17)第第42頁頁例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)第第43頁頁例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)第第44頁頁例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)第第45頁頁例：例：DCBEAF251234192646381725(A, )(E, 12)(F, 26)(F, 25)(A, 19)(C,17)第第46

16、頁頁1543212224443圖6.4.1用用算法求解下圖所示網(wǎng)絡(luò)的最小樹，其中每條邊上的算法求解下圖所示網(wǎng)絡(luò)的最小樹，其中每條邊上的數(shù)表示該邊的權(quán)值。數(shù)表示該邊的權(quán)值。第第47頁頁1543212224443154321222444315432122244431543212224443第第48頁頁第第49頁頁|最短有向路方程最短有向路方程|求最短有向路的求最短有向路的Dijkstra算法算法 算法步驟算法步驟 算例算例 算法復(fù)雜性算法復(fù)雜性第第50頁頁第第51頁頁第第52頁頁注：本算法僅適用于弧的權(quán)值為正數(shù)的有向網(wǎng)絡(luò)！第第53頁頁 用用Dijkstra算法求解下圖所示有向網(wǎng)絡(luò)中自點算法求解下圖

17、所示有向網(wǎng)絡(luò)中自點1到到其他各點的最短有向路。其中每條弧上的數(shù)表示其他各點的最短有向路。其中每條弧上的數(shù)表示其權(quán)值。其權(quán)值。16534251225343647圖圖6.5.1第第54頁頁165342512253436471653425122534364705340354（1 1） （2 2）第第55頁頁1653425122534364716534251225343647050343104588（3 3） （4 4）第第56頁頁1653425122534364716534251225343647003434588858（5 5） （6 6）第第57頁頁DEBCA501030101002060(A,

18、 )(A, 10)(A, 30)(A, 100)(0, 0）當(dāng)前狀態(tài)下當(dāng)前狀態(tài)下v到此點的到此點的距離距離dist(i)當(dāng)前狀態(tài)下，當(dāng)前狀態(tài)下，v到此點的到此點的最短路上的最后的頂點最短路上的最后的頂點加加入入邊邊信信息息的的存存儲儲后后的的算算法法第第58頁頁加加入入邊邊信信息息的的存存儲儲后后的的算算法法DEBCA501030101002060(A, )(A, 10)(A, 30)(A, 100)(0, 0）(B, 60)第第59頁頁DEBCA501030101002060(A, 10)(A, 30)(A, 100)(0, 0）(B, 60)(D, 50)(D, 90)加加入入邊邊信信息息

19、的的存存儲儲后后的的算算法法第第60頁頁DEBCA501030101002060(A, 10)(A, 30)(D, 90)(0, 0）(D, 50)(C, 60)加加入入邊邊信信息息的的存存儲儲后后的的算算法法第第61頁頁DEBCA501030101002060(A, 10)(A, 30)(0, 0）(D, 50)(C, 60)加加入入邊邊信信息息的的存存儲儲后后的的算算法法第第62頁頁如果大家想知道怎樣求所有點對之間的最短路算法請大家看相關(guān)的參考資料第第63頁頁|最大流最小割定理最大流最小割定理 基本概念基本概念 主要結(jié)論主要結(jié)論|最大流算法最大流算法 算法步驟算法步驟 算例算例 算法復(fù)雜性

20、算法復(fù)雜性第第64頁頁第第65頁頁定定理理6.6.1（增增廣廣路路定定理理）一一個個可可行行流流是是最最大大流流當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)不不存存在在 關(guān)關(guān)于于它它的的從從s到到t的的增增廣廣路路。 定定理理6.6.2（整整流流定定理理）如如果果網(wǎng)網(wǎng)絡(luò)絡(luò)中中所所有有弧弧容容量量是是整整數(shù)數(shù)，則則存存在在 值值為為整整數(shù)數(shù)的的最最大大流流。 定定理理6.6.3（最最大大流流最最小小割割定定理理）一一個個(s,t)-流流的的最最大大值值等等于于(s,t)-割割 的的最最小小容容量量。 第第66頁頁第第67頁頁 求解下圖所示有向網(wǎng)絡(luò)中自點求解下圖所示有向網(wǎng)絡(luò)中自點1到點到點6的最大流。的最大流。其中每條弧上的

21、數(shù)表示其容量。其中每條弧上的數(shù)表示其容量。1653428695625378圖圖6.6.4第第68頁頁1653428,66,49,75,26,62,15,13,27,08,61653428,66,49,75,26,62,15,13,27,08,6( ,) ( 4,2)( 2,2)( 1,1)( 2,2)( 1,2)1653428,86,49,95,46,62,15,13,27,08,6( ,) ( 5,1)( 2,1)( 1,1)( 2,1)( 3,1)1653428,86,49,95,46,52,25,13,17,18,6( ,) 圖圖6.6.5第第69頁頁第第70頁頁|最小費用流算法最小費用

22、流算法 規(guī)劃形式規(guī)劃形式 算法步驟算法步驟 算例算例 算法復(fù)雜性算法復(fù)雜性|最特殊的最小費用流運輸問題最特殊的最小費用流運輸問題 規(guī)劃形式規(guī)劃形式 算法步驟算法步驟 算例算例 第第71頁頁第第72頁頁 ),( ,0 , , , 0)( )( )( . t . s min),(AjicxtsiNixxvxxvxxxwijijjjiijjjttjjjssjAjiijij 第第73頁頁 ,)( ),( , 0),( ,)()( . t . s )()( max),(NiipAjirAjiwripjprcvspvtpijijijAjiijij無無限限制制 第第74頁頁第第75頁頁 求解下圖所示網(wǎng)絡(luò)中自

23、點求解下圖所示網(wǎng)絡(luò)中自點1到點到點4其值為其值為3的的最小費用流。其中每條弧上的第一個數(shù)表示最小費用流。其中每條弧上的第一個數(shù)表示單位流的費用，第二個數(shù)表示容量。單位流的費用，第二個數(shù)表示容量。stba1,21,21,23,43,1圖圖6.7.1第第76頁頁stba1,2,01,2,01,2,03,4,03,1,00000stba( ,) stba1,2,01,2,01,2,03,4,03,1,00111stba( ,) (,2)s第第77頁頁stba1,2,01,2,01,2,03,4,03,1,00220stba( ,) stba1,2,01,2,01,2,03,4,03,1,00231s

24、tba( ,) (,2)a(,2)s(,2)b(,2)a第第78頁頁stba1,2,21,2,21,2,03,4,03,1,00231stba( ,) stba1,2,21,2,21,2,23,4,03,1,00342stba( ,) (,1)b第第79頁頁stba1,2,21,2,21,2,23,4,03,1,00352stba( ,) stba1,2,21,2,21,2,13,4,13,1,1(,1)b(,1)s(,1)a第第80頁頁設(shè)設(shè)網(wǎng)網(wǎng)絡(luò)絡(luò)的的點點數(shù)數(shù)為為 n，弧弧數(shù)數(shù)為為 m，弧弧的的最最大大容容量量為為 w。 算算法法的的循循環(huán)環(huán)次次數(shù)數(shù)取取決決于于點點的的 p(i)值值修修正正

25、的的次次數(shù)數(shù)最最多多進(jìn)進(jìn)行行 mw 次次， 因因此此第第 2 步步的的計計算算量量為為)(2wmO。 如如果果最最大大流流值值為為 v，則則留留增增廣廣最最多多進(jìn)進(jìn)行行 v 次次， 所所以以第第 3 步步的的計計算算量量為為)(mvO。 第第 4 步步的的計計算算量量為為)(nmvO 所所以以，總總的的計計算算量量為為)(2mvwmO 。 第第81頁頁ia表示發(fā)點表示發(fā)點 i 可供應(yīng)的產(chǎn)品數(shù)量可供應(yīng)的產(chǎn)品數(shù)量),.,2 , 1(mi ； jb表示收點表示收點 j 所需的產(chǎn)品數(shù)量所需的產(chǎn)品數(shù)量),.,2 , 1(nj ； ijw表示從發(fā)點表示從發(fā)點 i 到收點到收點 j 的單位產(chǎn)品運輸費用；的單

26、位產(chǎn)品運輸費用； ijx表示從發(fā)點表示從發(fā)點 i 分配給收點分配給收點 j 的產(chǎn)品數(shù)量。的產(chǎn)品數(shù)量。 0),.,2 , 1( , ),.,2 , 1( , . t . s min,ijijijjiijjiijijxnjbxmiaxxw 第第82頁頁 ),.,2 , 1;,.,2 , 1( , . t . s maxnjmiwvuvbuaijjijjjiii 第第83頁頁第第84頁頁 求如圖所示運輸問題的最優(yōu)解求如圖所示運輸問題的最優(yōu)解14321328106355169147131299-30-30-20-454050圖圖6.7.4第第85頁頁2131234 15 20 30 20 10 30

27、初始原可行解初始原可行解 第第86頁頁213123486121014對偶解對偶解第第87頁頁w w8 -6 -10 -29 809 -12 513 -7 5114 29 -116 -5 -486121 u V第第88頁頁 15- 20 30+ 20- 10 302131234調(diào)整原始可行解調(diào)整原始可行解第第89頁頁213123403666101對偶解對偶解第第90頁頁8 26 -10 -9 909 -12 313 -7 5314 29 -316 -5 -66610-1 第第91頁頁 20- 45 15+ 5 10- 302131234調(diào)整原始可行解調(diào)整原始可行解第第92頁頁1021312340

28、33662對偶解對偶解第第93頁頁w w8 26 -10 -9 709 -12 313 -7 2314 59 -16 35 -366102 u V第第94頁頁v二分圖的對集二分圖的對集 基本概念基本概念 主要定理主要定理v二分圖的最大基數(shù)對集二分圖的最大基數(shù)對集 基本思想基本思想 算法步驟算法步驟 算例算例 算法復(fù)雜性算法復(fù)雜性v二分網(wǎng)絡(luò)的最大權(quán)對集分派問題二分網(wǎng)絡(luò)的最大權(quán)對集分派問題 規(guī)劃形式規(guī)劃形式 算法步驟算法步驟 算例算例第第95頁頁第第96頁頁第第97頁頁第第98頁頁第第99頁頁求下圖求下圖a a所示的二分圖所示的二分圖G G的最大基數(shù)對集，若初始解如下圖的最大基數(shù)對集，若初始解如下

29、圖b b所示所示1234567A98a1234567A98b第第100頁頁1234567A9831333標(biāo)號標(biāo)號1234567A98333517810標(biāo)號標(biāo)號1234567A98增廣路增廣路1234567A98增廣路增廣路第第101頁頁1234567A981257108標(biāo)號標(biāo)號1234567A98增廣路增廣路第第102頁頁若令若令mS |，nT |，且，且nm 。 在找到一個匈牙利樹或找到一條增廣路之前，在找到一個匈牙利樹或找到一條增廣路之前， 標(biāo)標(biāo)號程序最多進(jìn)行號程序最多進(jìn)行)(mnO次；次； 在求出所需的對集之前，初始對集最多能增廣在求出所需的對集之前，初始對集最多能增廣 m 次；次； 所以，總的計算量為所以，總的計算量為)(2nmO。 第第103頁頁設(shè)二分網(wǎng)絡(luò)是完全的設(shè)二分網(wǎng)絡(luò)是完全的),(