第6章圖與網絡分析ppt課件

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

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

3、支撐樹樹與支撐樹|6.4 最小樹問題最小樹問題|6.5 最短有向路問題最短有向路問題|6.6 最大流問題最大流問題|6.7 最小費用流問題最小費用流問題|6.8 最大對集問題最大對集問題|圖與網絡圖與網絡| 無向圖的基本概念無向圖的基本概念| 有向圖和網絡有向圖和網絡|關聯矩陣和鄰接矩陣關聯矩陣和鄰接矩陣| 關聯矩陣關聯矩陣| 鄰接矩陣鄰接矩陣| 主要結論主要結論|子圖子圖 1n1n 圖6.1.12n3n4n11e12e14e24e23e34e34e5n關聯：一條邊的端點稱為與這條邊的關聯關聯：一條邊的端點稱為與這條邊的關聯鄰接：與同一條邊關聯的端點稱為是鄰接的，同時如果兩條邊鄰接：與同一條邊

4、關聯的端點稱為是鄰接的，同時如果兩條邊 有一個公共端點，則稱這兩條邊是鄰接的有一個公共端點，則稱這兩條邊是鄰接的有限圖：任何圖有限圖：任何圖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、邊相連的圖二分圖二分圖 G=(N,E) G=(N,E)：存在的一個二分劃：存在的一個二分劃(S,T)(S,T)，使得，使得G G的的每條邊有一個端點在每條邊有一個端點在S S中，另一個端點在中，另一個端點在T T中中完全二分圖完全二分圖 G=(S,T,E) G=(S,T,E)：S S中的每個點與中的每個點與T T中的每個點中的每個點都相連的簡單二分圖都相連的簡單二分圖簡單圖簡單圖G G的補圖的補圖 : :與與G G有相同頂點集合的簡單圖，且補有相同頂點集合的簡單圖，且補圖中的兩個點相鄰當且僅當它們在圖中的兩個點相鄰當且僅當它們在G G中不相鄰中不相鄰圖6.1.3(b)(a)續(xù)23n1n4n2n

6、續(xù)37BADC2358設G是一個圖有向圖），若對G的每條邊弧都賦予一個實數，并稱為這條邊弧的權，則G連同它邊弧上的權稱為一個有向網絡或賦權有向圖，記為G=(N,E,W).1543212224443圖6.4.1續(xù)4無向完全圖：在無向圖中，如果任意兩個頂點之間無向完全圖：在無向圖中，如果任意兩個頂點之間存在邊。存在邊。 有向完全圖：在有向圖中，如果任意兩頂點之間都有向完全圖：在有向圖中，如果任意兩頂點之間都有存在方向互為相反的兩條弧。有存在方向互為相反的兩條弧。 含有含有n n個頂點的無向完全圖有多少條邊？個頂點的無向完全圖有多少條邊？含有含有n n個頂點的有向完全圖有多少條??？個頂點的有向完全圖

7、有多少條??？ 0123012n(n-1)/2n(n-1)續(xù)5續(xù)6右圖的關聯矩陣是右圖的關聯矩陣是 右圖的關聯矩陣是右圖的關聯矩陣是 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的鄰接矩陣是的鄰接矩陣是 01110101011101110101011105432154321 010000001100011043214321143213524圖6.1.7圖6

8、.1.8續(xù)9握手定理握手定理續(xù)10續(xù)11圖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.圖的連通點點i i和和j j點是連通的：點是連通的：G G中存在一條中存在一條ii，jj路路G G是連通的：是連通的：G G中任意兩點都是連通的中任意兩點都是連通的 連通分支：連通分支：G G的極大連通子圖的極大連通子圖 圖圖6.2.16.2.

9、1中中a a是連通圖；（是連通圖；（b b是一個具有是一個具有三個連通分支的非連通圖。三個連通分支的非連通圖。 圖6.2.2（a）（b）有向圖有向圖G G中的一條有向路：個點和弧的交錯序列中的一條有向路：個點和弧的交錯序列 (ni,aij,nj,nk,akl,nl) (ni,aij,nj,nk,akl,nl)， 記為記為(ni,nl)(ni,nl)有向路有向路 簡單有向路：弧不重的有向路簡單有向路：弧不重的有向路 初級有向路：點不重的有向路初級有向路：點不重的有向路 有向回路：至少包含一條弧且有向回路：至少包含一條弧且ni=njni=nj的的(ni,nj)(ni,nj)有向路有向路 簡單有向回

10、路：弧不重的有向回路簡單有向回路：弧不重的有向回路 初級有向回路：點不重的有向回路初級有向回路：點不重的有向回路如下圖：(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,5,3,1)是一條有向回路；(1,2,3,4,5,3,1)是一條簡單有向回路；(1,2,4,5,3,1)是一條初級有向回路。165432點點i i和點和點j j是強連通的：是強連通的：G G中存在一條中存在一條(i,j)(i,j)有向路有向路, ,也也存在一條存在一條(j,i)(j,i)有向

11、路有向路G G是強連通的：是強連通的：G G中任意兩點都是強連通的中任意兩點都是強連通的 G G的強連通分支：的強連通分支：G G的極大連通子圖的極大連通子圖圖圖6.2.46.2.4中，（中，（a a是一個強連通分支，（是一個強連通分支，（b b是一個是一個具有三個強連通分支的非強連通圖。具有三個強連通分支的非強連通圖。(a)(b)圖6.2.4如何編寫判斷一個圖有向圖能否強如何編寫判斷一個圖有向圖能否強連通的算法呢？連通的算法呢？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

12、.61 1、樹及其性質、樹及其性質-樹的性質-支撐樹及其性質|最小樹及其性質最小樹及其性質|求最小樹的求最小樹的KruskalKruskal算法算法 | 算法步驟算法步驟| 算例算例| 算法復雜性算法復雜性 |求最小樹的求最小樹的DijkstraDijkstra算法又稱算法又稱PrimPrim算法）算法）| 算法步驟算法步驟| 算例算例| 算法復雜性算法復雜性DCBEAF251234192646382517例：例：用用Kruskal算法求解下圖所示網絡的最小樹，其中每條算法求解下圖所示網絡的最小樹，其中每條邊上的數表示該邊的權值。邊上的數表示該邊的權值。 1543212224443圖6.4.1

13、154321154321215432122154321223本算法遺留問題：本算法復雜性是如何算出來的？如何判斷加入一條邊后是否構成回路？“點的重新標號是什么意思？按什么數據結構存儲和如何編程才能使得此算法節(jié)省時間？注：在許多教科書上此算法叫Prim算法U=A U=A，F 例：例：DCBEAF251234192646381725U=A，F，C U=A，F，C，D U=A，F，C，D，E U=A，F，C，D，E，B 例：例：DCBEAF251234192646381725(A, )(A, 34)(A, )(A, 46)(A, 19)(A, )例：例：DCBEAF25123419264638172

14、5(A, )(A, 34)(F, 26)(F, 25)(A, 19)(F,25)(C,17)例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)例：例：DCBEAF251234192646381725(A, )(E, 12)(F, 26)(F, 25

15、)(A, 19)(C,17)1543212224443圖6.4.1用用Dijkstra算法求解下圖所示網絡的最小樹，其中每條邊上的算法求解下圖所示網絡的最小樹，其中每條邊上的數表示該邊的權值。數表示該邊的權值。1543212224443154321222444315432122244431543212224443|最短有向路方程最短有向路方程|求最短有向路的求最短有向路的Dijkstra算法算法| 算法步驟算法步驟| 算例算例| 算法復雜性算法復雜性注：本算法僅適用于弧的權值為正數的有向網絡！ 用用Dijkstra算法求解下圖所示有向網絡中自點算法求解下圖所示有向網絡中自點1到到其他各點的最短

16、有向路。其中每條弧上的數表示其他各點的最短有向路。其中每條弧上的數表示其權值。其權值。16534251225343647圖圖6.5.1165342512253436471653425122534364705340354（1 1） （2 2）1653425122534364716534251225343647050343104588（3 3） （4 4）1653425122534364716534251225343647003434588858（5 5） （6 6）DEBCA501030101002060(A, )(A, 10)(A, 30)(A, 100)(0, 0）當前狀態(tài)下當前狀態(tài)下v到此

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

18、(0, 0）(D, 50)(C, 60)加加入入邊邊信信息息的的存存儲儲后后的的算算法法DEBCA501030101002060(A, 10)(A, 30)(0, 0）(D, 50)(C, 60)加加入入邊邊信信息息的的存存儲儲后后的的算算法法如果大家想知道怎樣求所有點對之間的最短路算法請大家看相關的參考資料|最大流最小割定理最大流最小割定理| 基本概念基本概念| 主要結論主要結論|最大流算法最大流算法| | 算法步驟算法步驟| 算例算例| 算法復雜性算法復雜性定定理理6.6.1（增增廣廣路路定定理理）一一個個可可行行流流是是最最大大流流當當且且僅僅當當不不存存在在 關關于于它它的的從從s到到

19、t的的增增廣廣路路。 定定理理6.6.2（整整流流定定理理）如如果果網網絡絡中中所所有有弧弧容容量量是是整整數數，則則存存在在 值值為為整整數數的的最最大大流流。 定定理理6.6.3（最最大大流流最最小小割割定定理理）一一個個(s,t)-流流的的最最大大值值等等于于(s,t)-割割 的的最最小小容容量量。 求解下圖所示有向網絡中自點求解下圖所示有向網絡中自點1到點到點6的最大流。的最大流。其中每條弧上的數表示其容量。其中每條弧上的數表示其容量。1653428695625378圖圖6.6.41653428,66,49,75,26,62,15,13,27,08,61653428,66,49,75,

20、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|最小費用流算法最小費用流算法| 規(guī)劃形式規(guī)劃形式| 算法步驟算法步驟| 算例算例| 算法復雜性算法復雜性|最特殊的最小費用流運輸問題最特殊的最小費用流運輸問題| 規(guī)劃形式規(guī)劃形式| 算法步驟算法步驟| 算例算例 ),( ,0 , , , 0)( )(

21、)( . t . s min),(AjicxtsiNixxvxxvxxxwijijjjiijjjttjjjssjAjiijij ,)( ),( , 0),( ,)()( . t . s )()( max),(NiipAjirAjiwripjprcvspvtpijijijAjiijij無無限限制制 求解下圖所示網絡中自點求解下圖所示網絡中自點1到點到點4其值為其值為3的的最小費用流。其中每條弧上的第一個數表示最小費用流。其中每條弧上的第一個數表示單位流的費用，第二個數表示容量。單位流的費用，第二個數表示容量。stba1,21,21,23,43,1圖圖6.7.1stba1,2,01,2,01,2,

22、03,4,03,1,00000stba( ,) stba1,2,01,2,01,2,03,4,03,1,00111stba( ,) (,2)sstba1,2,01,2,01,2,03,4,03,1,00220stba( ,) stba1,2,01,2,01,2,03,4,03,1,00231stba( ,) (,2)a(,2)s(,2)b(,2)astba1,2,21,2,21,2,03,4,03,1,00231stba( ,) stba1,2,21,2,21,2,23,4,03,1,00342stba( ,) (,1)bstba1,2,21,2,21,2,23,4,03,1,00352stb

23、a( ,) stba1,2,21,2,21,2,13,4,13,1,1(,1)b(,1)s(,1)a設設網網絡絡的的點點數數為為 n，弧弧數數為為 m，弧弧的的最最大大容容量量為為 w。 算算法法的的循循環(huán)環(huán)次次數數取取決決于于點點的的 p(i)值值修修正正的的次次數數最最多多進進行行 mw 次次， 因因此此第第 2 步步的的計計算算量量為為)(2wmO。 如如果果最最大大流流值值為為 v，則則留留增增廣廣最最多多進進行行 v 次次， 所所以以第第 3 步步的的計計算算量量為為)(mvO。 第第 4 步步的的計計算算量量為為)(nmvO 所所以以，總總的的計計算算量量為為)(2mvwmO 。

24、ia表示發(fā)點表示發(fā)點 i 可供應的產品數量可供應的產品數量),.,2 , 1(mi ； jb表示收點表示收點 j 所需的產品數量所需的產品數量),.,2 , 1(nj ； ijw表示從發(fā)點表示從發(fā)點 i 到收點到收點 j 的單位產品運輸費用；的單位產品運輸費用； ijx表示從發(fā)點表示從發(fā)點 i 分配給收點分配給收點 j 的產品數量。的產品數量。 0),.,2 , 1( , ),.,2 , 1( , . t . s min,ijijijjiijjiijijxnjbxmiaxxw ),.,2 , 1;,.,2 , 1( , . t . s maxnjmiwvuvbuaijjijjjiii 求如圖所

25、示運輸問題的最優(yōu)解求如圖所示運輸問題的最優(yōu)解14321328106355169147131299-30-30-20-454050圖圖6.7.42131234 15 20 30 20 10 30 初始原可行解 213123486121014對偶解對偶解w w8 -6 -10 -29 809 -12 513 -7 5114 29 -116 -5 -486121 u V 15- 20 30+ 20- 10 302131234調整原始可行解調整原始可行解213123403666101對偶解對偶解8 26 -10 -9 909 -12 313 -7 5314 29 -316 -5 -66610-1 20

26、- 45 15+ 5 10- 302131234調整原始可行解調整原始可行解102131234033662對偶解對偶解w w8 26 -10 -9 709 -12 313 -7 2314 59 -16 35 -366102 u Vv二分圖的對集二分圖的對集v 基本概念基本概念v 主要定理主要定理v二分圖的最大基數對集二分圖的最大基數對集v 基本思想基本思想v 算法步驟算法步驟v 算例算例v 算法復雜性算法復雜性v二分網絡的最大權對集分派問題二分網絡的最大權對集分派問題v 規(guī)劃形式規(guī)劃形式v 算法步驟算法步驟v 算例算例求下圖求下圖a a所示的二分圖所示的二分圖G G的最大基數對集，若初始解如下圖的最大基數對集，若初始解如下圖b b所示所示1234567A98a1234567A98b1234567A9831333標號標號1234567A98333517810標號標號1234567A98增廣路增廣路1234567A98增廣路增廣路1234567A981257108標號標號1234567A98增廣路增廣路若令若令mS |，nT |，且，且nm 。 在找到一個匈牙利樹或找到一條增廣路之前，在找到