圖論的matlab算法

1、第六講 圖論初步 6.1 引言圖論是運籌學的一個經典和重要的分支,它起源于歐拉(Euler 對七橋問題的抽象和論證。 1936年, 匈牙利數學家柯尼希(Knig出版了圖論的第一部專著有限圖與無限圖理論 ,豎立了圖論發(fā)展的第一 座里程碑。此后,圖論進入發(fā)展與突破的快車道,所研究的問題涉及經濟管理、工業(yè)工程、交通運輸、計 算機科學與信息技術、通訊與網絡技術等諸多領域。近幾十年來,由于計算機技術和科學的飛速發(fā)展,大 大地促進了圖論研究和應用,圖論的理論和方法已經滲透到物理、化學、通訊科學、建筑學、生物遺傳學、 心理學、經濟學、社會學等學科中。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯系。如

2、果我們用點表示這些具體事物,用 連接兩點的線段(直的或曲的表示兩個事物的特定的聯系,就得到了描述這個“圖”的幾何形象。圖論 為任何一個包含了一種二元關系的離散系統(tǒng)提供了一個數學模型,借助于圖論的概念、理論和方法,可以 對該模型求解。一名貨柜車司機奉命在最短的時間內將一車貨物從甲地運往乙地。從甲地到乙地的公路網縱橫交錯, 因此有多種行車路線,這名司機應選擇哪條線路呢?假設貨柜車的運行速度是恒定的,那么這一問題相當 于需要找到一條從甲地到乙地的最短路。一名郵遞員負責投遞某個街區(qū)的郵件。如何為他(她設計一條最短的投遞路線(從郵局出發(fā),經過 投遞區(qū)內每條街道至少一次,最后返回郵局?由于這一問題是我國管

3、梅谷教授 1960年首先提出的,所 以國際上稱之為中國郵遞員問題。一名推銷員準備前往若干城市推銷產品。如何為他(她設計一條最短的旅行路線(從駐地出發(fā),經 過每個城市恰好一次,最后返回駐地?這一問題的研究歷史十分悠久,通常稱之為旅行商問題。一家公司經理準備安排 N 名員工去完成 N 項任務,每人一項。由于各員工的特點不同,不同的員工 去完成同一項任務時所獲得的回報是不同的。如何分配工作方案可以使總回報最大?某種原材料有 M 個產地, 現在需要將原材料從產地運往 N 個使用這些原材料的工廠。 假定 M 個產地 的產量和 N 家工廠的需要量已知, 單位產品從任一產地到任一工廠的運費已知, 那么如何安

4、排運輸方案可 以使總運輸成本最低? 6.2 圖的基本概念若用小圓點表示點集 V (G 中的點,連線表示邊集 E (G 中的邊,則可用圖形將圖表示出來,稱之為 圖的圖形。我們常用圖的圖形代表圖本身。(e 1 = v 1v 2, (e 2 = v 2v 3, (e 3 = v 2v 3, (e 4 = v 3v 4, (e 5 = v 4v 4, 無環(huán)且無重邊的圖稱之為 簡單圖 。任意兩點均相鄰的簡單圖稱之為 完全圖 。 如果圖 G 的各條邊都被賦予了方向, 則稱圖 G 為 有向圖 。 如果圖 G 的每條邊 e 都附有一個實數 w (e , 則稱圖 G 為 賦權圖 ,實數 w (e 稱為邊 e 的

5、權(值 。 如果簡單圖 G 的每個頂點都有相同的度數 d ,則稱 G 為 d 次 正則圖 。mvdnii2(1=。一個圖除了可以用圖形表示之外,還可用矩陣來表示。用矩陣表示圖有利于計算機處理。設圖 G = V , E , V = v 1, v 2, , v n , E = e 1, e 2, , e m 。無向圖的 關聯矩陣 M (G = (m ij 是一個 n m 矩陣,其中=不相關聯與 若 , 相關聯 與 若 , 0 1j i j i ij e v e v m ; 有向圖的 關聯矩陣 M (G = (m ij 是一個 n m 矩陣,其中=不相關聯 與 若 , 的終點 是 若 , -的起點

6、是 若 , 0 1 1j i j i j i ij e v e v e v m 。無向圖的 鄰接矩陣 A (G = (a ij 是一個 n 階方陣,其中 a ij 為連接點 v i 與點 v j 之間邊的數目;有向圖的 鄰接矩陣 A (G = (a ij 是一個 n 階方陣,其中 a ij 為從點 v i 與出發(fā)到點 v j 終止的邊的數目; 簡單賦權有向圖 的鄰接矩陣 A (G = (a ij 是一個 n 階方陣,其中=E v v ji w E v v w a j i j i ij 0 若 , 若 , 是它的權值 且 若 , 。 無向賦權圖的 邊權矩陣 W (G = (w ij 是一個 3m

7、 方陣,其中 w 1j 為第 j 條邊的起點的標號, w 2j 為第 j 條邊的終點的標號, w 3j 為第 j 條邊的權值。定義 設 G = V (G , E (G , G 與 H = V (H , E (H , H 為兩個圖。若 V (H V (G , E (H E (G ,且 H 是 G 在 E (H 上的限制,則稱 H 是 G 的 子圖 。若 H 是 G 的子圖,且 V (H = V (G ,則稱 H 是 G 的 生成 子圖 。若 V (H V (G , V (H ,且對于 v i , v j V (H , v i v j E (G v i v j E (H ,則稱 H 是 G 的 導

8、出子圖 。 = v 1e 1v 2e 2 v k e k v k +1,若滿足 e i 的端點為 v i 與 v i +1, i = 1, 2, , k ,則稱 為一條從起點 v 1到終點 v k +1的長為 k 的 通路 。邊不重復的通路稱為 簡單通路 ;除起點與終點可以相同外,任意兩點都不同的通路,稱為 基本通路 , 基本通路簡稱為 路 。顯然,基本通路必為簡單通路。稱起點與終點相同的通路為 回路 ;邊不重復的回路稱為 簡單回路 ;起點與終點相同的長為正的基本通 路稱為 基本回路 ,也稱為 圈 。如不引起混淆(如在簡單圖中 ,通路與回路均可用點序列來表達。1 = v 1v 2v 3, 2

9、= v 1v 2v 3v 4v 2, 3 = v 1v 2v 3v 2v 3v 4,則 1, 2, 3分別是長為 2, 4, 5的通路。其中 1與 2為簡單通路, 1為基本通路。又取C 1 = v 1v 2v 3v 4v 2v 5v 1, C 2 = v 1v 2v 5v 1,則 C 1是長為 6的簡單回路, C 2是長為 3的圈。 尋求從一固定起點 u 0到其余各點的最短路的最有效算法之一是 Dijkstra (迪克斯特拉算法, 1959年 由 Dijkstra 提出。這個算法是一種迭代算法,它依據的是一個重要而明顯的性質:最短路是一條路 , 最短 路上的任一子段也是最短路 。Dijkstr

10、a 算法的基本思想是:按距 u 0從近到遠為順序,依次求得 u 0到圖 G 的各頂點的最短路和距離, 直至頂點 v 0(或直至圖 G 的所有頂點 。Dijkstra 算法問題:設簡單賦權圖 G = V , E 有 n 個頂點,求 G 中 u 0點到其它各點的距離及最短路。為避免重復并保留每一步的計算信息,對 v V ,定義兩個標號:l (v 頂點 v 的標號,表示從頂點 u 0到 v 的一條路的權值;z (v 頂點 v 的父節(jié)點標號,用以確定最短路的路線。第一步 賦初值:令 l (u 0 = 0,對所有 v V u 0,令 l (v = , z (v = u 0; S 0 = u 0, i =

11、 0。第二步 若 i = n 1,停止;否則令i= V S i ,進行下一步。第三步 更新標號:對每個 v i,令l (v =,(,(min vuwulvliiSu ii+;如果 l (v l (u i + w (u i v ,則 z (v = u i ,否則 z (v 不變。第四步 計算 (min vliv ,并用 u i +1記達到最小值的頂點,置 S i +1 = S i u i +1, i = i +1,轉第二步。算法終止后, u 0到 v 的距離由 l (v 的終值給出,從 v 的父節(jié)點標號 z (v 追溯到 u 0,就得到 u 0到 v 的 最短路的路線。 (2 用 u 0 = v

12、 1對各頂點的標號進行更新。 i = 1。0= v 2, v3, v4, v5, v6, v 0,由算法有:l (v 2 = , 0+7 = 7, l (v 3 = , 0+4 = 4, l (v 4 = , 0+ = , l (v 5 = , 0+ = ,l (v 6 = , 0+2 = 2。1= v 2, v3, v4, v5, v 1,由算法有:2= v 2, v4, v5, v 2,由算法有:l (v 2 = 7, 3+3 = 6, l (v 4 = 7, 3+1 = 4, l (v 5 = 7, 3+ = 7。3= v 2, v5, v 3,由算法有:l (v 2 = 6, 4+ =

13、 6, l (v 5 = 7, 4+2 = 6。4= v 2, v 4= v 2,由算法有:l (v 2 = 6, 6+ = 6。注 : 迭代的終止條件也可使用 S n 1 = v 1, , v n ,或者 1n = 。 若尋找 v 1到某點 v 的最短路的路由,則由 v 開始追溯父節(jié)點直至 v 1。再如, v 1到 v 2的最短路為:v 1v 6v 3v 2。 若求 v 1到某點 v 的距離,則直接由 l (v 的終值確定。 (a (b (c (d (e (f (g (h (i (j尋求賦權圖中各對頂點之間最短路,顯然可以調用 Dijkstra 算法。具體方法是:每次以不同的頂點作 為起點,

14、用 Dijkstra 算法求出從該起點到其余頂點的最短路徑,反復執(zhí)行 n 次這樣的操作,就可得到每對 頂點之間的最短路。但這樣做需要大量重復計算,效率不高。 R. W. Floyd(弗洛伊德另辟蹊徑,提出了 比這更好的算法,操作方式與 Dijkstra 算法截然不同。Floyd 算法的基本思想是:從圖的帶權鄰接矩陣 A = a (i , j n n 開始,在 A 中用插入頂點的方法依次構 造出 n 個矩陣 D (1、 D (2、 D (n ,使最后得到的矩陣 D (n 成為 圖的距離矩陣 ,即 矩陣 D (n 的 i 行 j 列元 素便是 i 號頂點到 j 號頂點的距離 。 構造 D (i 的

15、同時, 也引入一個 路由矩陣 P (i 來記錄兩點間的最短路徑。構造矩陣 D (k , k = 1, 2, , n ,采用如下的遞推公式:D (0 = d ij (0 n n = A :是帶權鄰接矩陣, d ij (0 表示從 v i 到 v j 的、中間不插入任何點的路徑,即邊 v i v j 的 權值;D (1 = d ij (1 n n ,其中 d ij (1 = min dij (0, d i 1(0 + d1 j (0 :d ij (1 表示從 v i 到 v j 的、中間最多只允許 v 1作為 插入點的路徑中最短路的長度;D (2 = d ij (2 n n ,其中 d ij (2

16、 = min dij (1, d i 2(1 + d2 j (1 :d ij (2 表示從 v i 到 v j 的、中間最多只允許 v 1和 v 2作為插入點的路徑中最短路的長度; D (n = d ij (n n n ,其中 d ij (n = min dij (n 1 , d i , n 1 (n 1 + d n 1, j(n 1 :d ij (n 表示從 v i 到 v j 的、中間最多只允 許 v 1, v 2, , v n 1作為插入點的路徑中最短路的長度,即 v i 和 v j 之間的距離。建立路由矩陣 P (k , k = 1, 2, , n ,采用如下的遞推公式: P (0 =

17、 p ij (0 n n :p ij (0 表示從 v i 到 v j 的要經過點 v j ;每求得一個 D (k 時,按下列方式產生相應的新的 P (k = p ij (k n n ,其中+=否則 若 , , 1(1( 1( 1( (k ijk kj k ik k ij k ijp d d d k p 。即當 v k 被插入到 v i 與 v j 之間的最短路時,被記錄在 P (k 中。依次求 D (n 時求得 P (n ,可由 P (k 來查找任何兩點之間最短路的路由。Floyd 算法問題:設簡單賦權圖 G = V , E 有 n 個頂點,求 G 中任意兩點 v i 和 v j 之間的距離

18、及最短路。 輸入帶權鄰接矩陣 A = a (i , j n n 。第一步 賦初值:對所有 i 和 j , d (i , j = a (i , j ;當 a (i , j = 時, path (i , j = 0,否則 path (i , j = j , k = 1。第二步 更新 d (i , j , path (i , j :對所有 i 和 j ,若 d (i , k + d (k , j d (i , j ,則轉第三步;否則 d (i , j = d (i , k + d (k , j , path (i , j = path (i , k , k = k +1,繼續(xù)執(zhí)行第三步。第三步 重復

19、第二步直到 k = n +1。 在此: d (i , j :d ij (k 。 path (i , j :p ij (k ;對應于 d ij (k 的路徑上 i 的后繼點,最終的取值為 i 到 j 的最短路徑上 i 的后繼點。 例如,若=5331154555443245552522221path 則頂點 1到頂點 3的最短路徑為 1253。這是因為:path(1, 3 = 2,意味著頂點 1的后繼點為 2;又path(2, 3 = 5, 意味著頂點 2的后繼點為 5; 同理, 因 path(5, 3 = 3, 從而頂點 5的后繼點為 3。 故 1253便是頂點 1到頂點 3的最短路徑。根據 D

20、ijkstra 算法和 Floyd 算法的步驟,4和5中分別給出了相應的 Matlab 程序。 Dijkstra 算法的 Matlab 實現 % Dijkstra算法% 輸入帶權鄰接矩陣 w n = size(w,1;w1 = w(1,:;% 賦初值for i = 1:nl(i = w1(i;z(i = 1;ends = ;s(1 = 1;u = s(1;k = 1;l;z;while k l(u+w(u,i l(i = l(u+w(u,i; z(i = u;endendendendl;z;% 求 v*ll = l;for i = 1:nfor j = 1:kif i=s(jll(i = ll

21、(i;elsell(i = inf;endendendlv = inf;for i = 1:nif ll(i lvlv = ll(i;v = i;endendlv;v; s(k+1 = v; k = k+1; u = s(k;end l zFloyd 算法的 Matlab 實現 % Floyd算法% 輸入帶權鄰接矩陣 a n = size(a,1 D = a;path = zeros(n,n; for i = 1:n for j = 1:nif D(i,j=inf path(i,j = j; end end endfor k = 1:n for i = 1:nfor j = 1:nif D(i

22、,k+D(k,j D(i,j D(i,j = D(i,k+D(k,j; path(i,j = path(i,k; end end end end D path0551inf 2502inf inf inf 5201infinf 1inf 1034inf inf inf 3072inf inf 470。(1 運行 Dijkstra 算法的程序,輸出結果為l = 0 6 3 4 6 2; z = 1 3 6 3 4 1。于是,由 l 和 z 可以得到 v 1到其余各點的距離和最短路的路由。例如, v 1到 v 5的距離由 l(5 = 6給出;其最短路的路由根據 z(5 = 4, z(4 = 3,

23、z(3 = 6, z(6 = 1得到:v 1v 6v 3v 4v 5。(2 運行 Floyd 算法的程序,輸出結果為D = 0 6 3 4 6 2 6 0 3 4 6 4 3 3 0 1 3 1 4 4 1 0 2 2 6 6 3 2 0 4 2 4 1 2 4 0 path = 1 6 6 6 6 6 3 2 3 3 3 3 6 2 3 4 4 6 3 3 3 4 5 3 4 4 4 4 5 4 1 3 3 3 3 6 例如, v 1到 v 5的距離由 D(1, 5 = 6給出;其最短路的路由根據 path(1, 5 = 6, path(6, 5 = 3, path(3, 5 = 4, pa

24、th(4, 5 = 5得到:v 1v 6v 3v 4v 5。解:輸入帶權鄰接矩陣 0inf 100inf 65700infinf inf inf 20030inf 80inf inf 0infinf inf inf 500。(1 運行 Dijkstra 算法的程序,輸出結果為l = 0 50 230 250 130; z = 1 1 5 3 2。于是,由 l 和 z 可以得到節(jié)點 1到其余各點的距離和最短路的路由。例如, 節(jié)點 1到節(jié)點 4的距離由 l(4 = 250給出; 其最短路的路由根據 z(4 = 3, z(3 = 5, z(5 = 2, z(2 = 1得到:12534。(2 運行 F

25、loyd 算法的程序,輸出結果為D = 0 50 230 250 130 path = 1 2 2 2 2 145 0 180 200 80 5 2 5 5 5 155 30 0 20 90 4 2 3 4 4 135 185 170 0 70 5 5 5 4 5 65 115 100 120 0 1 1 3 3 5 例如, 節(jié)點 1到節(jié)點 4的距離由 D(1, 4 = 250給出; 其最短路的路由根據 path(1, 4 = 2, path(2, 4 = 5, path(5, 4 = 3, path(3, 4 = 4得到:12534。 6.4 樹及其算法樹(tree 在圖論中是相當重要的一類

26、圖,它非常類似于自然界中的樹。樹的性質非常好,應用相當 廣泛1。 G 1G 2G 3(有圈 G 4(不連通(1G 是樹;(2G 中任意兩個不同點之間存在唯一的路;(3G 連通,刪去任一條邊均不連通;(4G 連通,且 n = m + 1;(5G 無圈,且 n = m + 1;(6G 無圈,添加任一條邊可得唯一的圈。 (a (b (c (d證明 給定連通圖 G ,若 G 無圈,則 G 本身就是自己的生成樹。若 G 有圈,則任取 G 中一個圈 C , 記刪去 C 中一條邊后所得之圖為 G 。顯然 G 中圈 C 已經不存在,但 G 仍然連通。若 G 中還有圈,再 重復以上過程,直到得到一個無圈的連通圖

27、 H 。易知 H 是 G 的生成樹。證畢。一個簡單連通圖只要不是樹,其生成樹就不唯一,而且非常多。一般地, n 個頂點地完全圖,其不同 地生成樹個數為 n n 2。因而,尋求一個給定賦權圖的最小生成樹,一般是不能用窮舉法的。例如, 30個頂 點的完全圖有 3028個生成樹, 3028有 42位,即使用最現代的計算機,在我們的有生之年也是無法窮舉的。 所以,窮舉法求最小生成樹是無效的算法,必須尋求有效的算法。在求最小生成樹的有效算法中,最著名的兩個是 Kruskal (克羅斯克爾算法和 Prim (普瑞姆算法, 其迭代過程都是基于貪婪法來設計的。1.求最小生成樹的 Kruskal 算法Krusk

28、al 算法的直觀描述假設 T 0是賦權圖 G 的最小生成樹, T 0中的邊和頂點均涂成紅色,初始時 G 中的邊均為白色。 將所有頂點涂成紅色; 在白色邊中挑選一條權值最小的邊,使其與紅色邊 不形成圈 ,將該白色邊涂紅; 重復直到有 n 1條紅色邊,這 n 1條紅色邊便構成最小生成樹 T 0的邊集合。 (a(b (c (dKruskal 算法的基本思想設 T 0和 C (T 0 分別為圖 G 的最小生成樹的邊集及其權值,初始狀態(tài)均為空,算法結束時 T 0包含最小 生成樹的所有邊, C (T 0 表示最小生成樹的權值。 令 VS 是一個不相交的節(jié)點的集合, 初始狀態(tài)時 VS = v 1, v 2,

29、 , v n 。 算法的主要步驟是每次從邊集 E 中選出一條未處理的有最小權值的邊 (u , v 進行分析, 如 果 u 和 v 同屬于 VS 的一個元素集, 則將邊 (u , v 刪除, 如果 u 和 v 分屬于 VS 的兩個元素集, 則將邊 (u , v 加入到 T 0中,并將這兩個元素集合并為一個元素集,然后再從 E 中另選權值最小的邊進行處理,直至找 到一棵最小生成樹為止。Kruskal 算法的步驟第一步 T 0, C (T 0 0, VS ,將 E 中的邊按權值從小到大排成序列 Q 。 第二步 對所有 v V , VS v ,即 VS = v 1, v 2, , v n 。 第三步

30、如果 |VS | = 1,輸出 T 0和 C (T 0 ,停止。否則進行下一步。 第四步 從 Q 中取出權值最小的邊 (u , v ,并從 Q 中刪除 (u , v 。邊 (a , b (c , e (a , e (b , c (d , g (a , c (d , f (f , g (c , d (a , g (e , g (d , e 權4 5 7 9 12 15 16 20 25 28 30 32步驟選出邊 ew (e 操作C (T 0a , b 加到T 0中a , b , c , d , e , f , g (a , b c , e 加到 T 0中 a , b , c , e , d ,

31、 f , g a , b , (c , e a , e 加到 T 0中 a , b , c , e , d , f , g a , b , (c , e , (a , e b , c 刪除 a , b , c , e , d , f , g a , b , (c , e , (a , e d , g 加到 T 0中 a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g a , c 刪除 a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g d , f 加到 T 0中

32、a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g , (d , f f , g 刪除 a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g , (d , f , (c , d 44 c , d 加到 T 0中a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g , (d , f , (c , d 69 2.求最小生成樹的 Prim 算法Prim 算法的直觀描述假設 T 0是賦權圖 G 的最小生成樹。任

33、選一個頂點將其涂紅,其余頂點為白點;在一個端點為紅色, 另一個端點為白色的邊中,找一條權最小的邊涂紅,把該邊的白端點也涂成紅色;如此,每次將一條邊和 一個頂點涂成紅色,直到所有頂點都成紅色為止。最終的紅色邊便構成最小生成樹 T 0的邊集合。 (a (b (cPrim 算法的基本思想設 T 0和 C (T 0 分別為圖 G 的最小生成樹的邊集及其權值,初始狀態(tài)均為空,算法結束時 T 0包含最小 生成樹的所有邊, C (T 0 表示最小生成樹的權值。先指定一個頂點為初始訪問點,記做 v 0,將 v 0加到“通 過點”的集合 V 中,然后找出跨接在“通過點”集合 V 與“未通過點”集合 V V 之間

34、權最小的邊 e 作 為“通過邊”加入 T 0中,并將 e 在 V V 中的端點轉到 V 中。重復上述過程直至 V = V 為止。Kruskal 算法的步驟第一步 T 0, C (T 0 0, V v 0。第二步 對每一個點 v V V , L (v c (v , v 0 (如果 (v , v 0 E ,則 c (v , v 0 = 。 第三步 如果 V = V ,輸出 T 0, C (T 0 ,停止。否則進行下一步。 第四步 在 V V 中找一點 u ,使L (u = minL (v | v V V ,并將 V 中與 u 鄰接的點記為 w , e = (w , u 。第五步 T 0T 0e ,

35、 C (T 0 C (T 0 + C (e , V V v 0。第六步 對所有 v V V ,如 c (v , u L (v ,則 L (v c (v , u ,否則 L (v 不變。第七步 轉第三步。步驟 u L (b L (c L (d L (e L (f L (g e V T 0C (T 01 a 7 a 02 b -9 7 a , b a , b a , b3 e -a , e a , b , e a , b , (a , e4 c -25 -c , e a , b , e , c a , b , (a , e , (c , e5 d -c , d a , b , e , c , d a , b , (a , e , (c , e , (c , d6 g -16 -(d , g a , b , e , c , d , g a , b , (a , e ,