1、1,第六章 圖論 （Graph Theory）,2,1. 圖論朔源 2. 圖的基本概念 3. 路與圈 4. 圖的矩陣表示 5. 帶權(quán)圖的最短路徑 6. Euler圖 7. Hamilton圖 8. 二分圖 9. 平面圖 10. 樹,3,1. 圖論朔源 圖論最早處理的問題是哥尼斯堡（konigsberg）城普雷格爾(pregel)河上的七橋問題。 問題：在十八世紀的東普魯士有個哥尼斯堡城（后屬于前蘇聯(lián)的立陶宛蘇維埃社會主義共和國，其名為加里寧格勒?，F(xiàn)屬于立陶宛共和國）。哥尼斯堡城位于普雷格爾河畔，河中有兩個島，城市中的各個部分由七座橋相連。,4,問題：從四塊陸地的任一塊出發(fā)，怎樣才能做到經(jīng)過每座

2、橋一次且僅一次，然后回到出發(fā)點。,5,1736年，瑞士數(shù)學(xué)家列昂哈德.歐拉( Leonhard.Euler ) 發(fā)表了他的著名論文“哥尼斯堡七座橋”。在這篇文章中他闡述了解決七橋問題的方法，引出了圖論的觀點，從而被譽為圖論之父，成為圖論的創(chuàng)始人。 哥尼斯堡七橋問題歸結(jié)為：在圖2 所示的圖中，從 A, B, C, D 任一點出發(fā)，通過每條邊一次且僅一次而返回出發(fā)點的回路是否存在？后人稱如此的問題為Euler環(huán)游。,6,歐拉斷言這樣的回路是不存在的。從圖2中的任一結(jié)點出發(fā)，為了要回到原來的出發(fā)點，要求與每個結(jié)點相關(guān)聯(lián)的邊數(shù)均為偶數(shù)。這樣才能保證從一條邊進入某結(jié)點后，可從另一條邊出去，而不經(jīng)過已走過

3、的邊。從一個結(jié)點的不同的兩條邊一進一出才能回到原出發(fā)點。而圖2中的A, B, C, D全是與奇數(shù)條邊相連，由此可知所要求的回路是不可能存在的。 歐拉給出了一個判定準則：若有Euler環(huán)游，則圖中每個結(jié)點都必須是偶結(jié)點(與偶數(shù)條邊相關(guān)聯(lián))；若不限定到回原出發(fā)點，則只能有兩個奇結(jié)點(與奇數(shù)條邊相關(guān)聯(lián))，一個起點，一個終點。 這是圖論的第一篇文獻。時年歐拉22歲。,注 列昂哈德.歐拉Leonhard . Euler （1707-1783） 瑞士數(shù)學(xué)家.后移居俄羅斯。27歲雙目失明，主要靠秘書幫助工作。,7,本世紀40年代的數(shù)學(xué)游戲：某人挑一擔(dān)菜、并帶一只狗、一只羊，要從河的北岸到南岸。由于船小，只允

4、許帶狗、羊、菜三者中的一種過河；當(dāng)人不在場時狗與羊、羊與菜不能呆在一起。問此人應(yīng)采取怎樣的辦法才能將這三樣?xùn)|西安全地帶過河去？ 方法一：不對稱狀態(tài)空間法 將人(person)、狗(dog)、羊(sheep)、菜(cabbage)中任意幾種在一起的情況看作是一種狀態(tài)，則北岸可能出現(xiàn)的狀態(tài)共有十六種，其中安全狀態(tài)有下面十種： (人，狗，羊，菜)，(空)； (P,D,S,C) ，() ； (人，狗，羊)， (菜)； (P,D,S,) ，(C) ； (人，狗，菜)，(羊)； (P,D,C) ，(S) ；,8,(人，羊，菜)，(狗)； (P,S,C) ，(D) ； (人，羊)，(狗，菜) ； (P,S)

5、 ，(D,C) 。 不安全的狀態(tài)有如下六種： (人)， (狗，羊，菜)； (P) ，(D,S,C) ； (人，菜)， (狗，羊) ； (P,C) ，(D,S) ； (人，狗)， (羊，菜) ； (P,D) ，(S,C) 。 可將十種安全狀態(tài)表示成十個結(jié)點，而渡河的全過程則看作是狀態(tài)間的轉(zhuǎn)移。這樣，上述問題就轉(zhuǎn)化為求一條從(人，狗，羊，菜)或 (P,D,S,C) 狀態(tài)到(空) 或()狀態(tài)的路徑。圖3中黑色箭頭所表示的路徑就是其中的一條。 另一條從(P,D,S,C)到()狀態(tài)的路徑不同的部分由圖3中紅色箭頭所示的路徑給出。,9,方法二：對稱狀態(tài)空間法 方法一僅考慮了河北岸的狀態(tài)，沒有考慮河南岸的狀

6、態(tài)。 現(xiàn)在將用字符串表示的兩岸狀態(tài)放入一個二元組中，以表示兩岸狀態(tài)的變化，其前者表示河北岸的狀態(tài)，后者表示河南岸的狀態(tài)。其圖示見下面圖4。它具有對稱性是明顯的(狀態(tài)的對稱性，圖的對稱性，路徑的對稱性)。,10,注：上述問題統(tǒng)稱“渡河問題”。 “三對忌妒的夫婦渡河問題”參見離散數(shù)學(xué)基礎(chǔ)美C.L.Liu著 劉振宏譯 P162； “三個傳教士與三個吃人肉的野人渡河問題”參見Prolog高級程序設(shè)計美L.斯特林 E.夏皮羅著 劉家佺鄧佑譯 鄭守淇校P197； 渡河問題的條件也是可變的。比如夫婦的對數(shù)可以是四對，五對；渡河能力或渡河工具小船的容量也是可變的。,11,2. 圖的基本概念 圖的定義 圖論的概

7、念術(shù)語 子圖與補圖 結(jié)點的度 圖的同構(gòu),12,定義1.(圖的定義一) 圖G = (V, E)是一個系統(tǒng) ，其中 (1)V是一個有限集合；V中的每一元素vV都稱為圖G的一個結(jié)點(node ,vertex)， V稱為圖G的結(jié)點集； (2)E是一個有限集合； E中的每一元素eE都稱為圖G的一條邊(edge) ； E稱為圖G的邊集。 注：此定義的優(yōu)點是簡單，適應(yīng)面廣；缺點是沒有規(guī)定清楚點、線之間的關(guān)系。 圖示：圖與畫的聯(lián)系。,例1.有四個城市v1， v2， v3， v4，其中v1與v2間有公路e1相連， v1與v4間有公路e2相連，v2與v3間有公路e3相連。 上述事實可用圖G = (V, E)表示。

8、圖G中結(jié)點集 V=v1 , v2 , v3 , v4，邊集 E=e1 , e2 , e3。,13,定義2. (圖的定義二) 圖G = (V, E)是一個系統(tǒng)，其中 (1)V 是一有限集合； V中的每一元素vV都稱為圖G的一個結(jié)點(node ,vertex)； V稱為圖G的結(jié)點集； (2)E VV是一有限集合，一個V上的關(guān)系； E中的每一元素(u,v)E都稱為圖G的一條邊(edge) (這里u, vV)； E稱為圖G的邊集。 注：此定義的優(yōu)點是簡單，規(guī)定了清楚的點、線之間的關(guān)系，很適合簡單圖、特別是有向圖（比如第二章的關(guān)系圖、哈斯圖）；缺點是無法表示平行邊，因此不適合多重圖（比如上節(jié)的七橋圖）。

9、 例2.有四個程序，它們之間存在如下的調(diào)用關(guān)系：P1 能調(diào)用P2 ， P2能調(diào)用P3 ，P2能調(diào)用P4 。 上述事實也可用一圖G = (V, E)來表示。圖中結(jié)點集V=v1 , v2 , v3 , v4 ，邊集E=(v1, v2), (v2, v3), (v2, v4) 。,14,定義3. (圖的定義三) 圖G = (V, E)是一個系統(tǒng)，其中 (1)V 是一有限集合； V中的每一元素vV都稱為圖G的一個結(jié)點(node ,vertex)； V稱為圖G的結(jié)點集； (2)是一有限集合； 中的每一元素都稱為圖G中的一個標號(label)； 稱為圖G的標號集； (3)E VV是一有限集合，一個三元關(guān)系

10、； E中的每一元素(u, ,v)E都稱為圖G的一條邊(edge) 或弧(arc),此邊起自u而終于v ；稱u是此邊的起點，稱是此邊的標號，稱v是此邊的終點 ，起點和終點統(tǒng)稱為邊的端點(這里u, vV , )； E稱為圖G的邊集。,15,注： 此定義是由美國哈佛大學(xué)愛倫堡教授給出的； 此定義規(guī)定了嚴格的點、線之間的關(guān)系，適應(yīng)面很廣、特別適合多重圖（比如上節(jié)的七橋圖）；缺點是邊表示比較復(fù)雜，簡單圖一般不采用。 標號實際上是為了區(qū)別兩點間的平行邊而設(shè)的；標號集的大小一般就是圖中平行邊的最大條數(shù)(圖的重數(shù)，參見下面概念)。 當(dāng)圖的重數(shù)為1，即圖無平行邊時(簡單圖，參見下面概念)，有 =1，各邊標號一樣

11、，全為1 ，這時可取掉各邊標號及標號集，定義3就變成了定義2；所以定義3適合于圖的一般情況，特別是(有平行邊的)多重圖，而定義2適合于(無平行邊的)簡單圖。 例3.七橋圖(見圖3),按定義3，可用一圖G = (V, , E)來表示。 圖中結(jié)點集V=v1 , v2 , v3 , v4，,16,圖中標號集= 1 , 2， 圖中邊集 E=(v1, 1, v3), (v1, 2, v3), (v1, 1, v4) ,(v1, 2, v4), (v1, 1, v2), (v2, 1, v3), (v2, 1, v4)， 它的圖示如圖3所示。 圖論的基本概念性術(shù)語和一些特殊圖： (1)(n,m)圖: |V

12、| = n,|E| = m，即有n個結(jié)點和m條邊的圖稱 為 ( n, m ) 圖。 (2)無向邊：(undirected edges簡edges)在定義3下，若邊 (u, , v)與邊(v, ,u)表示同一條邊，則稱此邊為無向邊。,17,(3)無向圖： (undirected graph簡graph) 所有的邊都是無向邊的圖稱為無向圖。記為G。 (4)有向邊：(directed arc簡arc或arrow) 在定義3下，若邊(u, , v)與邊(v, ,u)表示不同的邊， 則稱此邊為有向邊。 (5)有向圖： (directed graph簡digraph) 所有的邊都是有向邊的圖稱為有向圖。記

13、為D。 (6)混和圖： (mixed graph) 既有有向邊又有無向邊的圖稱為混和圖。 (7)空圖：(empty graph) V=(當(dāng)然 E=)，即沒有一個結(jié)點的圖稱為空圖。 (8)零圖：(null graph) E=，即沒有一條邊的圖稱為零圖。,18,(9)平凡圖： (trivial graph) |V| = 1，即只有一個結(jié)點的圖稱為平凡圖。 (10)二邊相鄰： (adjacent) 在圖中，若兩條邊有一公共端點，則稱此二邊相鄰。 (11)二結(jié)點相鄰： (adjacent) 若兩個結(jié)點是同一條邊的兩個端點，則稱此二結(jié) 點相鄰。 (12)一結(jié)點與一邊相關(guān)聯(lián)： (incident) 若一結(jié)

14、點是一邊的一個端點，則稱此結(jié)點與該 邊相 關(guān)聯(lián)。 (13)孤立點： (isolated vertex) 不與任何邊相關(guān)聯(lián)的結(jié)點稱為孤立點。 (14)自環(huán)： (loop ) 兩個端點相同的邊稱為自環(huán)。,19,(15)平行邊： (parallel edges ) 有相同端點(相同的起點，相同的終點)的兩條邊稱為平行邊。 (16)重數(shù)： (multiplicity) 兩結(jié)點間平行邊的條數(shù)稱為平行邊的重數(shù)。 (17)多重圖： (multiply graph) 具有平行邊的圖稱為多重圖；多重圖的重數(shù)是圖中平行邊重數(shù)的最大者。 (18)簡單圖： (單圖、單純圖(simple graph) 無平行邊、無自環(huán)

15、的圖稱為簡單圖。 (19)圖的階： (order) 圖中結(jié)點的個數(shù)|V|稱為圖的階。,20,(20)完全圖： (complete graph) 每一對不同的結(jié)點間都有一條邊的簡單圖稱為完全圖。 n個結(jié)點m條邊的無向完全圖： n個結(jié)點m條邊的有向完全圖：m=n(n-1) n個結(jié)點的無向完全圖記為：Kn,21,定義4. (圖的定義四) 圖G=(V,E, )是一個系統(tǒng)，其中 (1)V 是一有限集合； V中的每一元素vV都稱為圖G的一個結(jié)點(node ,vertex)； V稱為圖G的結(jié)點集； (2)E是一個有限集合； E中的每一元素eE都稱為圖G的一條邊(edge) ； E稱為圖G的邊集。 (3)是邊

16、到結(jié)點集的一個關(guān)聯(lián)函數(shù)，即 :E2V (無向圖) 或 :E VV (有向圖) 。 將E中的每條邊eE與結(jié)點集V中的一個二元子集u,v2V (或u,vV)相關(guān)聯(lián)或與結(jié)點集V上的一個二元組(u,v)VV相關(guān)聯(lián)，即 (e)=u,v (無向圖) 或 (e)= (u,v) (有向圖) ，稱u是此邊的起點，稱v是此邊的終點 ，結(jié)點u和v統(tǒng)稱為邊的端點。,22,注： 此定義是對美國庫曼教授所給定義的一個修正； 此定義的優(yōu)點是適應(yīng)面較廣，尤其是將邊看作是和結(jié)點同樣的獨立的研究對象，邊不再是由結(jié)點表示的一個附屬對象，用函數(shù)概念規(guī)定了點、線之間的嚴格關(guān)聯(lián)關(guān)系，這樣一來，就便于邊概念的進一步推廣（比如引出超圖概念）

17、；缺點是關(guān)聯(lián)函數(shù)表示比較煩瑣，簡單圖一般不采用。 例4.七橋圖(見圖10),按定義4， 可用一圖G = (V,E, )來表示。 圖中結(jié)點集V=v1 , v2 , v3 , v4， 圖中邊集E=e1,e2, e3,e4,e5,e6,e7， 圖中關(guān)聯(lián)函數(shù) :E2V 使 (e1)=v1,v3, (e2)=v1,v3, (e3)=v1,v2,(e4)=v1,v4, (e5)=v1,v4, (e6)=v2,v3, (e7)=v2,v4。,23,定義5.子圖(subgraph) 設(shè)G=(V, E)和G=(V, E)是兩個(有向的或無向的)圖。 (1) 若VV且E E，則稱G為G的子圖； (2) 若VV且

18、E E，則稱G為G的真子圖(proper-)； (3) 若V=V且E E，則稱G為G的生成子圖(spanning-)； (4)當(dāng)V=V且E=E ，或 V=V且E=時，稱G為G的平凡子圖(trivial-)；即，圖G 本身和G的零圖是G的平凡子圖。 例5.圖G及其子圖、生成子圖、 真子圖、平凡子圖。,圖11,24,定義6.商圖(quotient graph) 設(shè)G = (V,E)是一(有向的或無向的) 圖，RVV是一結(jié)點集V上的等價關(guān)系。 那么， 定義圖G關(guān)于等價關(guān)系R的商圖為簡單圖 GR = (VR, ER)其中： VR=V/ R=vRvV是V關(guān)于等價關(guān)系R的商集； ER =(uR, vR)u

19、R VRvRVR(uuR)(vvR) (u,v)E) 。 例6.在圖12中，圖G如(1)圖所示； 其關(guān)于等價關(guān)系R1 (以劃分v1, v5, v9,v2, v6, v10,v3, v7, v11,v4, v8, v12給出)的商圖GR1如(2)圖所示； 關(guān)于等價關(guān)系R2 (以劃分v1, v5,v2, v3, v6,v4, v7, v8,v9, v10 , v11, v12給出)的商圖GR2如(3)圖所示；,25,關(guān)于等價關(guān)系R3 (以劃分v1,v2, v3,v4,v5, v6, v7,v8,v9, v10, v1,v12給出)的 商圖GR3如(4)圖所 示(稱為由一條邊 e=(v9, v10)

20、所導(dǎo)出的 商圖，記為Ge)；,26,定義7.補圖(complement graph) 設(shè)G = (V,E)為一簡單圖，G* = (V,E*)是與圖G相應(yīng)的完全圖。 定義圖G的補圖 = (V, ) ，其中： = E* E。 例7.圖G 及其相應(yīng)的完全圖、補圖 分別如下圖13所示：,27,(21)結(jié)點的出度： (out-degree) 有向圖中以結(jié)點v為起點的有向邊的條數(shù)稱為結(jié)點v的出度。記為 。 (22)結(jié)點的進度： (入度(in-degree) 有向圖中以結(jié)點v為終點的有向邊的條數(shù)稱為結(jié)點v的進度。記為 。 (23)結(jié)點的度： (degree) 圖中與結(jié)點v關(guān)聯(lián)的邊的條數(shù)稱為結(jié)點v的度。記為d

21、eg(v)。 (24)奇結(jié)點： (odd vertex) 度數(shù)為奇數(shù)的結(jié)點稱為奇結(jié)點。 (25)偶結(jié)點： (even vertex) 度數(shù)為偶數(shù)的結(jié)點稱為偶結(jié)點。,28,(26)圖G的最小度： (minimal degree) 圖G中各結(jié)點度數(shù)的最小者。記為 (G) 。 (27)圖G的最大度： (maximum degree) 圖G中各結(jié)點度數(shù)的最大者。記為 (G) 。 (28)正則圖： (regular graph) 若圖G中各結(jié)點的度數(shù)都相等，則稱圖G 是正則圖。 顯然，這時 (G)=(G) 。 (29)k-正則的： (k- regular) 若圖G中各結(jié)點的度數(shù)都相等，且為k ，則稱圖G

22、 是 k-正則的，或k度正則的。 顯然，這時 (G)=(G)= k 。,29,(30)懸掛點： (hang vertex) 度數(shù)為1的結(jié)點稱為懸掛點。 (31)懸掛邊： (hang edge) 與懸掛點關(guān)聯(lián)的邊稱為懸掛邊。 例8.在右面的有向圖中，其中： =3, =4 ,deg(v1)=7 ； =2, =2 ,deg(v2)=4 ； =3, =1 ,deg(v3)=4 ； =1, =1 ,deg(v4)=2 ； =0, =0 ,deg(v5)=0 ； =0, =1 ,deg(v6)=1 ；,30,奇結(jié)點： v1, v6 ； 偶結(jié)點：v2, v3, v4 , v5 ； 懸掛點： v6 ； 懸掛邊

23、： (v2, v6) 。 有如下結(jié)論： (1)所有結(jié)點的度數(shù)之和等于邊數(shù)的二倍； 7+4+4+2+0+1=29 (2)所有結(jié)點的進度之和等于出度之和等于邊數(shù)； 4+2+1+1+0+1=3+2+3+1+0+0=9 (3)所有奇結(jié)點的度數(shù)之和是偶數(shù)； 7+1=8 。,31,例9.在下面的無向圖中，其中： deg(v1)=5,deg(v2)=3,deg(v3)=3, deg(v4)=2,deg(v5)=0,deg(v6)=1 ； 奇結(jié)點：v1, v2, v3, v6 ； 偶結(jié)點：v4 , v5 ； 懸掛點： v6 ； 懸掛邊： (v2, v6) 。 并且有如下結(jié)論： (1)所有結(jié)點的度數(shù)之和等于邊數(shù)

24、的二倍； 5+3+3+2+0+1=27 (2)所有奇結(jié)點的度數(shù)之和是偶數(shù)； 5+3+3+1=12 。,32,定理1. 設(shè) G = (V, E) 是 (n,m) 圖，則 (1)無向圖G中，所有結(jié)點的度之和等于邊數(shù)的二倍；即 dev(vi)=2m 。 (2)有向圖G中，所有結(jié)點的進度之和等于出度之和等于邊數(shù)；即 。 證.(采用數(shù)錢法) (1)因為無向圖G中的每條無向邊都與兩個結(jié)點相關(guān)聯(lián)，所以每條邊都能給G中結(jié)點的度數(shù)貢獻2，因而G中所有的m條邊能給G中結(jié)點的度數(shù)總計貢獻2m，故G中所有結(jié)點的度數(shù)之和為2m，即 dev(vi)=2m 。,33,(2)對于有向圖G ，每條有向邊都與一個終點和一個 起點

25、相關(guān)聯(lián)，因此每條有向邊都能給G中結(jié)點的進度貢獻1，給出度貢獻1，因而G中所有的m條邊能給G中結(jié)點的進度總計貢獻m，給出度總計貢獻m，故G中所有結(jié)點的進度之和等于出度之和等于邊數(shù)m ，即 。 定理2.任何圖中所有奇結(jié)點的度數(shù)之和是偶數(shù)。 證.設(shè)圖中共有n個結(jié)點；其中奇結(jié)點的個數(shù)為n1 ，并且不妨設(shè)奇結(jié)點為u1, u2, un1 ；偶結(jié)點的個數(shù)為n2 (當(dāng)然有n1+ n2=n) ，并且不妨設(shè)偶結(jié)點為w1, w2, , wn2 ， 其對應(yīng)的度數(shù)為2k1, 2k2, , 2kn2 ；于是有奇結(jié)點度數(shù)之和,34,=2m-(2k1+2k2+ +2kn2)(定理1) =2m-(k1+k2+ +kn2) 是偶

26、數(shù)。 推論1.(握手引理) 在一次集會上和奇數(shù)個人握過手的人的數(shù)目是偶數(shù)。 證. 用結(jié)點表示人，用邊表示兩人相互握過手，從而便可得到一個圖。這個圖表達了參加集會的人之間彼此握手打招呼的情況。于是直接應(yīng)用定理2，即可知推論的結(jié)論成立。,35,36,定義8.圖的同構(gòu)(isomorphism of graphs) (1)稱G=(V,E)及G=(V,E)二圖同構(gòu)，記為GG存在 著兩個雙射函數(shù)及， : V V ， : EE ，使得 (u,v)=(u,v) (u)=u (v)=v (*) (2)稱G=(V,E,)及G=(V,E,)二圖同構(gòu)，記為GG存在著兩個雙射函數(shù)及， : V V ， : EE ，使得

27、(e)=e(e)=u,v(e)=u,v(u)=u(v)=v 或 (e)=e(e)=(u,v)(e)=(u,v) (u)=u (v)=v,37,注： 此定義(1)中(*)式也可改寫為： (u,v)= (u), (v) (*) 此定義(2)中(*)式也可改寫為： (e)=u,v (e)=(u), (v) 或 (e)=(u,v) (e)=(u), (v) 這實際上就是圖的同態(tài)公式； 圖的同構(gòu)遠比代數(shù)系統(tǒng)的同構(gòu)復(fù)雜。這是因為圖的同構(gòu)在同態(tài)公式中牽扯著兩個(甚至三個,考慮定義三)雙射函數(shù)的交叉關(guān)系，而代數(shù)系統(tǒng)的同構(gòu)在同態(tài)公式中只有一個雙射函數(shù)。因此圖的同構(gòu)問題不象代數(shù)系統(tǒng)的同構(gòu)問題那樣有許多進展、有幾個

28、定理好用，迄今為止，沒有任何進展，沒有任何定理可用，僅僅只能用定義；,38,例10.圖19中的(a)和(b)二無向圖是同構(gòu)的。 (采用變形法)其同構(gòu)函數(shù)為及，使得 (u1)=v1 , (u2)=v2 , (u3)=v3 , (u4)=v4 ； (u1,u2)=(v1, v2) , (u1,u3)=(v1, v3) , (u1,u4)=(v1, v4) , (u2,u3)=(v2, v3) ,(u2,u4)=(v1, v2) , (u3,u4)=(v3, v4)； 從而及是兩個雙射函數(shù)，且滿足同態(tài)公式(*)，因此(a)和(b)二圖是同構(gòu)的。,39,例11.圖20中的(a)和(b)二無向圖是同構(gòu)的

29、。 (采用抻路蹦圈法)其同構(gòu)函數(shù)為及，使得 (v1)=a, (v2)=c, (v3)=e, (v4)=b, (v5)=d ； (v1,v3)=(a, e) , (v1,v4)=(a, b) , (v2,v4)=(c, b) , (v2,v5)=(c, d) ,(v3,v5)=(e, d) ； 從而及是兩個雙射函數(shù)，且滿足同態(tài)公式(*)，因此(a)和(b)二圖是同構(gòu)的。,40,兩個圖能否同構(gòu)，從直觀的意義上講是能否將其中的一個圖示通過某些“變形”后使它成為另一個圖示的形狀。在上面的例子中，將(a)圖示作如下變形蹦圈后就可得到(b)圖示：,41,例12.圖22中的(a)和(b)二無向圖是同構(gòu)的。,

30、42,(采用抻路蹦圈法)其同構(gòu)函數(shù)為及，使得 (u1)=v1, (u2)=v5, (u3)=v3, (u4)=v6, (u5)= v2, (u6)= v4； (u1,u4)=(v1,v6) , (u1,u5)=(v1,v2) , (u1,u6)=(v1,v4) , (u2,u4)=(v5,v6) , (u2,u5)=(v5,v2) , (u2,u6)=(v5,v4) , (u3,u4)=(v3,v6) , (u3,u5)=(v3,v2) , (u3,u6)=(v3,v4) ； 從而及是兩個雙射函數(shù)，且滿足同態(tài)公式(*)，因此(a)和(b)二圖是同構(gòu)的。,43,例13.圖23中的(a)和(b)二

31、有向圖是同構(gòu)的。 (采用抻路蹦圈法)其同構(gòu)函數(shù)為及，使得 (u1)=v1, (u2)=v2, (u3)=v4, (u4)=v3； (u1,u2)=(v1,v2) , (u1,u4)=(v1,v3) , (u2,u3)=(v2,v4) , (u4,u3)=(v3,v4) ； 從而及是兩個雙射函數(shù)，且滿足同態(tài)公式(*)，因此(a)和(b)二圖是同構(gòu)的。,44,若兩個圖同構(gòu)，則它們必須滿足： (1)結(jié)點個數(shù)相等； (2)邊數(shù)相等； (3)對應(yīng)結(jié)點的進度、出度、度數(shù)均相等； (4)度數(shù)相同的結(jié)點個數(shù)相等； (5)平行邊對應(yīng)，重數(shù)相等； (6)自環(huán)對應(yīng)；懸掛點對應(yīng)；孤立點對應(yīng)； (7)結(jié)點間的相鄰關(guān)系對

32、應(yīng)；邊間的相鄰關(guān)系對應(yīng)；結(jié)點與邊的關(guān)聯(lián)關(guān)系對應(yīng)； (8)圈對應(yīng)；路對應(yīng)； (9)對應(yīng)圈的長度相等；對應(yīng)路的長度相等； ,45,例14.圖24中(a)、(b)兩圖不同構(gòu)。,46,Ulam猜想(1960). 1960年 Ulam提出如下關(guān)于圖同構(gòu)的著名猜想，至今無人能夠證明或否定。 設(shè)G=(V,E)及G=(V,E)是兩個圖，其結(jié)點集分別為 V=v1, v2, , vn 及 V=v1, v2, , vn (n3) ，則 (iN)(1in)(Hi Hi) (G G) ，即 若G和G 的n 對特殊真子圖對應(yīng)同構(gòu)，則G和G同構(gòu)。 這里：Hi =Gvi= (Vi,Ei), Vi =Vvi, Ei =(u,v

33、) (u,v)E u vi v vi； Hi =G vi= (Vi,Ei), Vi =V vi, Ei =(u,v) (u,v)Eu viv vi。,47,3.路與圈 定義與實例 基本概念 可達性 圖的連通性,48,3.路與圈 定義1.途徑(way) 設(shè)G=(V,E,)是一圖。G的有限非空點邊交錯序列 w=v0, e1, v1, e2, v2, , ek, vk 若滿足條件: (1)(ei)=vi-1, vi(或(vi-1, vi) (1ik) (2)當(dāng)ei和ei+1不是自環(huán)時，有ei+1 ei (1in)(無向圖)，則稱其為G的一條從v0到vk的途徑。v0稱為途徑w的起點，vk稱為途徑w的終

34、點，k稱為途徑w的長度。 注：當(dāng)G=(V,E)是一簡單圖時，在實際應(yīng)用中，常用純邊列或純點列的方式表示途徑： (1) w=(e1,e2, ,ek) ； (2)w=(v0, v1), (v1, v2), ,(vk-1, vk) ； (3)w=(v0, v1, v2, ,vk-1, vk) 。,49,途徑w實際上是一個動態(tài)的過程；其在圖G上的靜態(tài)軌跡是圖G的一個子圖G(w)=(V(w),E(w),(w)，其中： V(w)=v0, v1, v2, ,vk(去掉重復(fù)) E(w)=e1,e2, ,ek (去掉重復(fù)) (w): E(w)2V(w) (無向圖) 或 :E(w)V(w)V(w) (有向圖) 使

35、得 (w)(ei)=vi-1, vi(或(vi-1, vi) (1in) (去掉重復(fù)) 。 途徑定義1中條件(1)、(2)的情況如下圖1所示：,50,定義2.路(path)、圈(cycle) 設(shè)G=(V,E)是一圖，w=(v0, v1, v2, ,vk-1, vk)是一途徑。 (1)若v0 vk，則稱此途徑w是從v0到vk的一條路；記為 P=(v0, v1, v2,vk-1, vk)，并稱k為路P的長度(即|P|=k)。 (2)若v0= vk ，則稱此途徑w是一個圈；記為 C=(v0, v1, v2,vk-1, vk)，并稱k為圈C的長度(即|C|=k)。 定義3.可達性(reachablil

36、ity)、連通性(connectivity) 設(shè)G=(V,E)是一無向圖，u ,vV (1)若存在著從結(jié)點u到結(jié)點v的一條路P，則稱從結(jié)點u到結(jié)點v是可達的； (2)若圖G中任何兩結(jié)點都是可達的，則稱此圖G是連通的。否則，稱圖G是非連通的。,51,注一： 可達概念可以看作結(jié)點間的一個二元關(guān)系可達關(guān)系； 在無向圖中，規(guī)定任一結(jié)點自己到自己總是可達的，即可 達關(guān)系具有自反性； 在無向圖中，可達性是相互的，從結(jié)點u可達結(jié)點v，則從 結(jié)點v也可達結(jié)點u ，即可達關(guān)系是對稱的； 可達關(guān)系是傳遞的，即若從結(jié)點u可達結(jié)點v，又從結(jié)點v可 達結(jié)點w，則從結(jié)點u也可達結(jié)點w ； 一般地，當(dāng)從結(jié)點u可達結(jié)點v時，

37、它們之間不一定只有一 條路，可能會有若干條路。 稱從結(jié)點u到結(jié)點v的所有 路中長度最短的那一條為短程線，并將短程線的長度叫做 從結(jié)點u到結(jié)點v的距離，用d(u, v)表示。 規(guī)定： (1) d(u, u)=0 ； (2) 若結(jié)點u到結(jié)點v不可達，則d(u, v)= 。 短程線不一定是唯一的,有時可能會有好幾條； 按照通常的理解，距離概念一般都具有下列性質(zhì)：,52,(1) 非負性：d(u, v)0 ； (2) 對稱性；d(u, v)= d(v, u) ； (3) 三角不等式： d(u, v)+ d(v, w) d(u, w) 對無向圖，上述性質(zhì)全成立； 對有向圖來說，第二條，對稱性質(zhì)不成立。 注

38、二：連通性是有強弱之分的； (1)若圖G中任二結(jié)點間都至少存在著一條路可達，則稱圖 G是1-連通的； (2)若圖G中任二結(jié)點間都至少存在著k條不同的路可達，則 稱圖G是k-連通的(k2)； 通常所說的連通性實際上是指1-連通。 1-連通的連通 性較差，重要的信道圖網(wǎng)絡(luò)，比如軍事信道圖網(wǎng)絡(luò)，其連 通性至少在2-連通以上。,53,例1.在圖2中由結(jié)點v1到結(jié)點v3的路有： P1=(v1,v2,v3) P2=(v1,v4,v3) P3=(v1,v2,v4,v3) P4=(v1,v2,v4,v1,v2,v3) P5=(v1,v2,v4,v1,v4,v3) P6=(v1,v1,v2,v3) 在圖2中，由

39、結(jié)點v1到v1的圈有： C1=(v1,v1) C2=(v1,v2,v1) C3=(v1,v2,v3,v1) C4=(v1,v4,v3,v1) C5=(v1,v2,v3,v2,v1) C6=(v1,v2,v3,v2,v3,v1) ,54,例2.路的概念可以用來描述很多東西，如： (1)在Pascal語言中，一個復(fù)合語句以BEGIN開始，END結(jié)束，其中若干個語句用分號隔開。所以，執(zhí)行一個Pascal語言中的一條復(fù)合語句，可以認為是從圖3(a)中的BEGIN開始到END結(jié)束走完一條路。 (2)Pascal語言中的“標識符”可以認為是圖3(b)中從“入口”到“出口”的一條路。 (3)一個二進制數(shù)可以

40、認為是圖3(c)中從“入口”到“出口”的一條路。,55,注：實際上，分程序是如下的點列： 而不是邊列。 各種程序設(shè)計語言的文法都可用圖來表示，而且比通常所用的Backus元語言表示的更好、更直觀。 定義4.簡單路(simple path)簡單圈(simple cycle) 無重復(fù)邊的路稱為簡單路； 無重復(fù)邊的圈稱為簡單圈。 定義5.初級路(elementary path)初級圈(elementary cycle) 無重復(fù)點的路稱為初級路； 無重復(fù)點的圈稱為初級圈。,56,例4.在圖4中由結(jié)點v1到結(jié)點v5的路有： P1=(v1,v2,v5) ； P2=(v1,v2,v6,v2,v5)； P3=

41、(v1,v4,v5,v6,v2 ,v6,v2,v5) 。,57,定理1.設(shè)G=(V,E)為一簡單圖，若|V|= n ，則 (1)G中任一初級路的長度均不超過n-1； (2)G中任一初級圈的長度均不超過n。 證. (1)首先，在任一初級路中，各結(jié)點都是互不相同的；其次，在任一長度為k的初級路中，不同結(jié)點的個數(shù)必然為k+1。由于圖G中只有n個不同的結(jié)點，所以G中任一初級路的長度不會超過n-1 。 (2)在任一長度為k的初級圈中，其不同的結(jié)點的個數(shù)也為k。而圖G中僅有n個不同的結(jié)點，故任一初級圈的長度不會超過n。,58,例5.分油問題(三倒油葫蘆)： 有三個油桶a,b,c分別可裝8斤,5斤,3斤油。

42、假設(shè)a桶已裝滿了油，在沒有其它度量工具的情況下，如何將油平分？ 解.首先，由于沒有其它工具，只能利用這三只油桶來回傾倒，以達到分油的目的；為了分得準確，規(guī)定倒油時必須將油桶倒?jié)M或倒空。 其次， 用二元組(b,c)來表示b,c兩個桶中裝油的各種可能狀態(tài)，由于0b5, 0c3，故(b,c)共有24種不同的狀態(tài)。每一種狀態(tài)用一結(jié)點表示，兩結(jié)點間有邊相連當(dāng)且僅當(dāng)這兩種狀態(tài)可通過倒油的方法互相轉(zhuǎn)換。起始狀態(tài)為(0,0) ，終結(jié)狀態(tài)為(4,0) ，其它為中間狀態(tài)。 同時，為了盡快將油分好，要求中間狀態(tài)不重復(fù)出現(xiàn)。這樣，分油問題就轉(zhuǎn)化為：在具有24個形如(b,c)的結(jié)點的圖中，尋找由結(jié)點(0,0)到結(jié)點(4

43、,0)的初級路。 這樣的初級路有兩條，如圖5中的(a),(b)所示。(a),(b)可合并為(c)。,59,60,61,定義6.連通支(分圖(connected component) 無向圖中極大的連通子圖稱為一個連通支。 例6.在圖6中有三個連通支(分圖)；因此不是連通圖。,62,定義7.強連通 單向連通 弱連通 設(shè)G=(V,E)是一有向圖。如果G中 (1)任意兩結(jié)點間都是相互可達的，則稱圖G是強連通的(strongly connected)； (2)任意兩結(jié)點間至少有一結(jié)點可達另一結(jié)點，則稱圖G是單向連通的(single directed connected)； (3)略去邊的方向后，任意兩

44、結(jié)點間都是可達的(即圖G的無向圖是連通的)，則稱圖G是弱連通的(weakly connected)。 注：強連通單向連通；反之？單向連通弱連通；反之？ 例7.圖7。,63,定義8.強分圖 單向分圖 弱分圖 設(shè)G=(V,E)是一簡單有向圖。 (1)稱G的極大的強連通子圖為G的強連通支(強分圖(strongly fragments)； (2)稱G的極大的單向連通子圖為G的一個單向連通支(單向分圖(single directed fragments)； (3)稱G的一個極大的弱連通子圖為G的一個弱連通支(弱分圖(weakly fragments)。,例8.圖8。,64,注：有向圖中的強連通性建立了圖

45、G的結(jié)點集V上的一個等價關(guān)系，因而誘導(dǎo)出了圖G的結(jié)點集V上的一個劃分，圖G的每一個強連通支就是一個“劃分塊”；但是卻不能在圖G的邊集E上建立一個劃分； 如在例8的圖中，邊(3,4)和(6,5)不屬于G中任何一個強分圖。 有向圖中的弱連通性在圖G的結(jié)點集V上以及邊集E上都建立了一個等價關(guān)系，因而在圖G的結(jié)點集V上以及邊集E上都誘導(dǎo)出了一個劃分，圖G的每一個弱連通支就是一個“劃分塊”； 有向圖中的單向連通性，由于單向可達關(guān)系不具有對稱性，所以這種關(guān)系并不能在圖G的結(jié)點集V上及邊集E上建立一個等價關(guān)系，因而也不能在圖G的結(jié)點集V上及邊集E上誘導(dǎo)出一個劃分，圖G的每一個單向連通支也就不會是(由某種等價

46、關(guān)系所確定的)一個“劃分塊。,65,定理2.在簡單有向圖中， (1)每一個結(jié)點及每一條邊都恰在一弱連通支中； (2)每一個結(jié)點都恰在一個強連通支中； (3)每一個結(jié)點、每一條邊都至少屬于一個單向連通支。 例9.圖的強連通性概念在檢測死鎖問題上的應(yīng)用。 計算機操作系統(tǒng)在同一時間內(nèi)要處理許多程序請求(索取)資源(如CPU、內(nèi)存、外存、輸入輸出設(shè)備、編譯程序等等)的信息(命令)。但這些程序在占有一些資源的同時，又都要請求一些資源。在同一時間，既不釋放占有的資源，又不放棄資源的請求。在程序動態(tài)執(zhí)行的過程中，有時就可能會產(chǎn)生沖突。如程序P1已占有資源R1，又要請求資源R2；而程序P2已占有資源R2 ，又

47、要請求資源R1，這時兩個程序都無法進行工作。 稱計算機的這種狀況為“死鎖”狀態(tài)。計算機操作系統(tǒng)中有專門的進程來負責(zé)動態(tài)的檢測和處理死鎖狀態(tài)。,66,資源分配圖G是一個有向圖，它表達了時刻t系統(tǒng)中申請資源的分配狀態(tài)。在圖G中結(jié)點表示系統(tǒng)的資源，邊表示程序占有資源和請求資源的情況。當(dāng)程序Pk占有資源Ri而要申請資源Rj時，則從結(jié)點Ri到結(jié)點Rj連一條有向邊，并表記上Pk。 現(xiàn)設(shè)時刻t運行的程序集合為 P1, P2, P3, P4 ，時刻t資源集合 為R1, R2, R3, R4。 時刻t系統(tǒng)中資源的分配狀況 如右表1所示。,表1,67,其資源分配圖是有向圖G，如圖9所示。 產(chǎn)生死鎖的特征： 時刻t

48、系統(tǒng)產(chǎn)生死鎖 資源分配圖G中含有 強連通支(有向圈) 例10.圖的強連通性概念在檢測遞歸調(diào)用問題上的應(yīng)用。 程序設(shè)計中，程序設(shè)計人員一個很重要的任務(wù)是需要弄清一個程序中的調(diào)用關(guān)系是否具有遞歸性。但在多個過程中，其遞歸性往往不是很清楚的。,68,過程調(diào)用圖G是一個有向圖，它表達了程序中過程間的調(diào)用狀態(tài)。在圖G中結(jié)點表示程序的過程，邊表示過程間的調(diào)用情況。當(dāng)過程Pi調(diào)用過程Pj時，則從結(jié)點Pi到結(jié)點Pj連一條有向邊。 現(xiàn)設(shè)程序P中的過程集合為 P=P1, P2, P3, P4 , P5 。 程序P中過程間的調(diào)用關(guān)系為 C=(P1, P2), (P2, P4), (P3, P1), (P4, P5)

49、, (P5, P2)。 其過程調(diào)用圖G是有向圖G， 如圖10所示。 含有遞歸的特征： 程序中含有過程遞歸調(diào)用過程調(diào)用圖G中含有強連通支(有向圈)。,69,4.圖的矩陣表示 鄰接矩陣 關(guān)聯(lián)矩陣 可達矩陣 Warshall算法 可達矩陣與圖的連通性,70,4.圖的矩陣表示 定義1.鄰接矩陣(adjacency matrix 或 connection matrix) 設(shè)G=(V,E)是一簡單圖(有向或無向)，V=n ，并且設(shè)V=v1,v2,vn已被強行命名。則 定義n階方陣 A=(aij) nn ，其中 為圖G的鄰接矩陣。,例1.有向圖G的圖示如圖1所示。 V =v1,v2, v3, v4已強行命名

50、。,71,例2.無向圖G的圖示如圖2所示。 V =v1,v2, v3, v4 , v5, v6已強行命名。 注： 圖G是無向圖其鄰接矩陣是對稱矩陣。,72,結(jié)論： (1)每個簡單(有向或無向)圖都與一 個主角線元素全為零的01方陣對應(yīng)；每個主角線元素全為零的01方陣都與一 個簡單圖對應(yīng)； (2)對于一個(n,m)-圖來說，由于n個結(jié)點有n!種強行命名法，故應(yīng)有n!個鄰接矩陣。 從線性代數(shù)的知識可知：矩陣的行與列順序?qū)φ{(diào)，是對矩陣進行了所謂的基本初等變換。而 對矩陣施行基本初等變換，不會改變矩陣的本質(zhì)性質(zhì)即這n!個主角線元素全為零的01方陣都表示同一個圖； (3)兩個簡單圖同構(gòu)其鄰接矩陣經(jīng)過行與

51、列的順序?qū)φ{(diào)后，相同； (4)一圖G是零圖其鄰接矩陣A是全0矩陣；,73,(5)圖G是完全圖其鄰接矩陣A除主對角線外均是1； (6)在有向圖G的鄰接矩陣A中 其行和等于對應(yīng)結(jié)點的出度。即 其列和等于對應(yīng)結(jié)點的進度。即 同一編號的行和列的和相加等于對應(yīng)結(jié)點的度。即 全部1的個數(shù)等于邊數(shù)。即 ； (7)在無向圖G的鄰接矩陣A中 其行和等于對應(yīng)結(jié)點的度。即 其列和等于對應(yīng)結(jié)點的度。即 全部1的個數(shù)等于邊數(shù)的2倍。即。,74,定義2.關(guān)聯(lián)矩陣(incidence matrix) 設(shè)G=(V,E)是一簡單圖(有向或無向)，|V|=n，|E|=m ，并且設(shè)V=v1,v2,vn ， E=e1,e2,em已被

52、強行命名。則 定義nm階矩陣B=(bij) nm為圖G的關(guān)聯(lián)矩陣。其中：(1)若G是有向圖，則 (2)若G是無向圖，則,75,例3.有向圖G的圖示如圖3。 V =v1,v2, v3, v4, E=e1,e2, e3, e4, e5, e6, e7 已強行命名。 則圖G的關(guān)聯(lián) 矩陣為 注：有向圖的關(guān)聯(lián)矩陣的特點是每列一個正1，一個負1。這正好對應(yīng)相應(yīng)邊的起點和終點。,76,例4.無向圖G的圖示如圖4所示。 V =v1,v2, v3, v4 , v5, v6已強行命名。 則圖G的鄰接矩陣為 注：無向圖的關(guān)聯(lián)矩陣的特點是每列兩個1。這正好對應(yīng)相應(yīng)邊的兩個端點。,77,定義3.可達矩陣(reachab

53、le matrix) 設(shè)G=(V,E)是一簡單圖(有向或無向)，|V|=n ，并且設(shè)V=v1,v2,vn已被強行命名。則 定義n階方陣 R=(rij) nn ，其中 為圖G的可達矩陣。 注：(1)對于有向圖 從結(jié)點vi可達結(jié)點vj從結(jié)點vi到結(jié)點vj至少有一條有向路 從結(jié)點vi不可達結(jié)點vj從結(jié)點vi到結(jié)點vj沒有有向路 (2)對于無向圖 從結(jié)點vi可達結(jié)點vj從結(jié)點vi到結(jié)點vj至少有一條路 從結(jié)點vi不可達結(jié)點vj從結(jié)點vi到結(jié)點vj沒有路。,78,例5.有向圖G的圖示如圖5。 V =v1,v2, v3, v4已強行命名。 則圖G的可達矩陣為 可達矩陣的計算 直接從圖的圖示求其可達矩陣，一

54、般情況下是一件很困難的事，因為需要找出任二結(jié)點間的一條(有向、無向)路?？蛇_矩陣的計算是要從圖的鄰接矩陣求出其可達矩陣。,79,定義4.鄰接矩陣的布爾冪 設(shè)G=(V,E)是一簡單圖(有向或無向)， n階方陣A是圖G 的鄰接矩陣。則 遞歸的定義鄰接矩陣A的布爾冪 (1)A(1)=A； (2)A(m+1)= A(m)A； 其中： (1in,1jn) 。 注：這里和都是二元布爾運算：布爾乘和布爾和。 其運算表如下：,80,可達矩陣的計算方法一：(矩陣冪算法) 可達矩陣 R=A A(2) A(3) A(n) 注： 這里是矩陣的布爾和運算。 兩個矩陣的布爾和運算就是其對應(yīng)元素做二元布爾和運算。 例6.用

55、矩陣冪算法求圖5所示的有向圖G的可達矩陣。 圖G的鄰接矩陣及其矩陣冪為,81,有向圖G的可達矩陣 R=AA(2)A(3) A(4) = 。 矩陣冪算法的計算工作量： 從表2可得矩陣冪算法的(時間)復(fù)雜性是n4級的； (空間)復(fù)雜性是n3級的。,82,可達矩陣的計算方法二：Warshall算法(1962年) No1.R:=A No2.k:=1 No3.i:=1 No4.for k:=1 step 1 until n do rij := rij(rikrkj) No5.i:=i+1;if in then goto No4 No6.k:=k+1;if kn then goto No3 No7.if

56、kn then exit 注： 這里，在第k步,如果 記rij為rij (k) ，R為R(k)，則有 rij (k) := rij (k-1) (rik (k-1) rkj (k-1) )； 于是 有 rij (k) =1 從結(jié)點vi到結(jié)點vj有直接邊或者有通過結(jié)點v1,v2, ,vk的路 而這點正是Warshall算法正確性的要點； Warshall算法實際上是一個無層次的、前步結(jié)果即用、一步輸出結(jié)果的迭代過程。這里的分層是人為的、免強的、不自然的。,83,例7.用Warshall算法求圖5所示的有向圖G的可達矩陣。 圖G的鄰接矩陣及各層可達矩陣冪為 Warshall算法的計算工作量： 從表

57、3可得Warshall算法的(時間)復(fù)雜性是n3級的； (空間)復(fù)雜性是n2級的。比矩陣冪算法降低約一個冪級！,84,可達矩陣與圖的連通性 (1)有向圖G強連通可達矩陣R是全1矩陣； (2)有向圖G單向連通RRT除主對角線外均是1； (3)有向圖G弱連通由矩陣A1=AAT所確定的可達矩 陣R是全1矩陣； (4)有向圖G中有有向圈可達矩陣R的某些主對角線元素rii =1；,表,85,5.帶權(quán)圖的最短路徑 定義 Dijkstra算法 算法思想及實質(zhì) 計算實例,86,5. 帶權(quán)圖的最短路徑 定義1.帶權(quán)圖(weighted digraph) 設(shè)G=(V,E)是一簡單圖。稱一元函數(shù) w:ER+ 為圖G 的權(quán)函數(shù)，使得 對于每一條邊eE，均有一正實數(shù)w(e)R+與之對應(yīng) 并稱圖G 為帶有權(quán)w的圖，簡稱為帶權(quán)圖。并記為G=(V,E, w)。 例1.圖1所示的圖G 是一帶