離散數(shù)學(xué)第6章.ppt

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

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

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

4、許帶狗、羊、菜三者中的一種過河；當(dāng)人不在場(chǎng)時(shí)狗與羊、羊與菜不能呆在一起。問此人應(yīng)采取怎樣的辦法才能將這三樣?xùn)|西安全地帶過河去？ 方法一：不對(duì)稱狀態(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)表示成十個(gè)結(jié)點(diǎn)，而渡河的全過程則看作是狀態(tài)間的轉(zhuǎn)移。這樣，上述問題就轉(zhuǎn)化為求一條從(人，狗，羊，菜)或 (P,D,S,C) 狀態(tài)到(空) 或()狀態(tài)的路徑。圖3中黑色箭頭所表示的路徑就是其中的一條。 另一條從(P,D,S,C)到()狀態(tài)的路徑不同的部分由圖3中紅色箭頭所示的路徑給出。,9,方法二：對(duì)稱狀態(tài)空間法 方法一僅考慮了河北岸的狀態(tài)，沒有考慮河南岸的狀

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

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

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

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

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

11、，全為1 ，這時(shí)可取掉各邊標(biāo)號(hào)及標(biāo)號(hào)集，定義3就變成了定義2；所以定義3適合于圖的一般情況，特別是(有平行邊的)多重圖，而定義2適合于(無平行邊的)簡(jiǎn)單圖。 例3.七橋圖(見圖3),按定義3，可用一圖G = (V, , E)來表示。 圖中結(jié)點(diǎn)集V=v1 , v2 , v3 , v4，,16,圖中標(biāo)號(hào)集= 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個(gè)結(jié)點(diǎn)和m條邊的圖稱 為 ( n, m ) 圖。 (2)無向邊：(undirected edges簡(jiǎn)edges)在定義3下，若邊 (u, , v)與邊(v, ,u)表示同一條邊，則稱此邊為無向邊。,17,(3)無向圖： (undirected graph簡(jiǎn)graph) 所有的邊都是無向邊的圖稱為無向圖。記為G。 (4)有向邊：(directed arc簡(jiǎn)arc或arrow) 在定義3下，若邊(u, , v)與邊(v, ,u)表示不同的邊， 則稱此邊為有向邊。 (5)有向圖： (directed graph簡(jiǎn)digraph) 所有的邊都是有向邊的圖稱為有向圖。記

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

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

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

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

17、；缺點(diǎn)是關(guān)聯(lián)函數(shù)表示比較煩瑣，簡(jiǎn)單圖一般不采用。 例4.七橋圖(見圖10),按定義4， 可用一圖G = (V,E, )來表示。 圖中結(jié)點(diǎn)集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)是兩個(gè)(有向的或無向的)圖。 (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=時(shí)，稱G為G的平凡子圖(trivial-)；即，圖G 本身和G的零圖是G的平凡子圖。 例5.圖G及其子圖、生成子圖、 真子圖、平凡子圖。,圖11,24,定義6.商圖(quotient graph) 設(shè)G = (V,E)是一(有向的或無向的) 圖，RVV是一結(jié)點(diǎn)集V上的等價(jià)關(guān)系。 那么， 定義圖G關(guān)于等價(jià)關(guān)系R的商圖為簡(jiǎn)單圖 GR = (VR, ER)其中： VR=V/ R=vRvV是V關(guān)于等價(jià)關(guān)系R的商集； ER =(uR, vR)u

19、R VRvRVR(uuR)(vvR) (u,v)E) 。 例6.在圖12中，圖G如(1)圖所示； 其關(guān)于等價(jià)關(guān)系R1 (以劃分v1, v5, v9,v2, v6, v10,v3, v7, v11,v4, v8, v12給出)的商圖GR1如(2)圖所示； 關(guān)于等價(jià)關(guān)系R2 (以劃分v1, v5,v2, v3, v6,v4, v7, v8,v9, v10 , v11, v12給出)的商圖GR2如(3)圖所示；,25,關(guān)于等價(jià)關(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.補(bǔ)圖(complement graph) 設(shè)G = (V,E)為一簡(jiǎn)單圖，G* = (V,E*)是與圖G相應(yīng)的完全圖。 定義圖G的補(bǔ)圖 = (V, ) ，其中： = E* E。 例7.圖G 及其相應(yīng)的完全圖、補(bǔ)圖 分別如下圖13所示：,27,(21)結(jié)點(diǎn)的出度： (out-degree) 有向圖中以結(jié)點(diǎn)v為起點(diǎn)的有向邊的條數(shù)稱為結(jié)點(diǎn)v的出度。記為 。 (22)結(jié)點(diǎn)的進(jìn)度： (入度(in-degree) 有向圖中以結(jié)點(diǎn)v為終點(diǎn)的有向邊的條數(shù)稱為結(jié)點(diǎn)v的進(jìn)度。記為 。 (23)結(jié)點(diǎn)的度： (degree) 圖中與結(jié)點(diǎn)v關(guān)聯(lián)的邊的條數(shù)稱為結(jié)點(diǎn)v的度。記為d

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

22、 是 k-正則的，或k度正則的。 顯然，這時(shí) (G)=(G)= k 。,29,(30)懸掛點(diǎn)： (hang vertex) 度數(shù)為1的結(jié)點(diǎn)稱為懸掛點(diǎn)。 (31)懸掛邊： (hang edge) 與懸掛點(diǎn)關(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é)點(diǎn)： v1, v6 ； 偶結(jié)點(diǎn)：v2, v3, v4 , v5 ； 懸掛點(diǎn)： v6 ； 懸掛邊

23、： (v2, v6) 。 有如下結(jié)論： (1)所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的二倍； 7+4+4+2+0+1=29 (2)所有結(jié)點(diǎn)的進(jìn)度之和等于出度之和等于邊數(shù)； 4+2+1+1+0+1=3+2+3+1+0+0=9 (3)所有奇結(jié)點(diǎn)的度數(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é)點(diǎn)：v1, v2, v3, v6 ； 偶結(jié)點(diǎn)：v4 , v5 ； 懸掛點(diǎn)： v6 ； 懸掛邊： (v2, v6) 。 并且有如下結(jié)論： (1)所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)

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

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

26、數(shù)。 推論1.(握手引理) 在一次集會(huì)上和奇數(shù)個(gè)人握過手的人的數(shù)目是偶數(shù)。 證. 用結(jié)點(diǎn)表示人，用邊表示兩人相互握過手，從而便可得到一個(gè)圖。這個(gè)圖表達(dá)了參加集會(huì)的人之間彼此握手打招呼的情況。于是直接應(yīng)用定理2，即可知推論的結(jié)論成立。,35,36,定義8.圖的同構(gòu)(isomorphism of graphs) (1)稱G=(V,E)及G=(V,E)二圖同構(gòu)，記為GG存在 著兩個(gè)雙射函數(shù)及， : V V ， : EE ，使得 (u,v)=(u,v) (u)=u (v)=v (*) (2)稱G=(V,E,)及G=(V,E,)二圖同構(gòu)，記為GG存在著兩個(gè)雙射函數(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) 這實(shí)際上就是圖的同態(tài)公式； 圖的同構(gòu)遠(yuǎn)比代數(shù)系統(tǒng)的同構(gòu)復(fù)雜。這是因?yàn)閳D的同構(gòu)在同態(tài)公式中牽扯著兩個(gè)(甚至三個(gè),考慮定義三)雙射函數(shù)的交叉關(guān)系，而代數(shù)系統(tǒng)的同構(gòu)在同態(tài)公式中只有一個(gè)雙射函數(shù)。因此圖的同構(gòu)問題不象代數(shù)系統(tǒng)的同構(gòu)問題那樣有許多進(jìn)展、有幾個(gè)

28、定理好用，迄今為止，沒有任何進(jìn)展，沒有任何定理可用，僅僅只能用定義；,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)； 從而及是兩個(gè)雙射函數(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) ； 從而及是兩個(gè)雙射函數(shù)，且滿足同態(tài)公式(*)，因此(a)和(b)二圖是同構(gòu)的。,40,兩個(gè)圖能否同構(gòu)，從直觀的意義上講是能否將其中的一個(gè)圖示通過某些“變形”后使它成為另一個(gè)圖示的形狀。在上面的例子中，將(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) ； 從而及是兩個(gè)雙射函數(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) ； 從而及是兩個(gè)雙射函數(shù)，且滿足同態(tài)公式(*)，因此(a)和(b)二圖是同構(gòu)的。,44,若兩個(gè)圖同構(gòu)，則它們必須滿足： (1)結(jié)點(diǎn)個(gè)數(shù)相等； (2)邊數(shù)相等； (3)對(duì)應(yīng)結(jié)點(diǎn)的進(jìn)度、出度、度數(shù)均相等； (4)度數(shù)相同的結(jié)點(diǎn)個(gè)數(shù)相等； (5)平行邊對(duì)應(yīng)，重?cái)?shù)相等； (6)自環(huán)對(duì)應(yīng)；懸掛點(diǎn)對(duì)應(yīng)；孤立點(diǎn)對(duì)應(yīng)； (7)結(jié)點(diǎn)間的相鄰關(guān)系對(duì)

32、應(yīng)；邊間的相鄰關(guān)系對(duì)應(yīng)；結(jié)點(diǎn)與邊的關(guān)聯(lián)關(guān)系對(duì)應(yīng)； (8)圈對(duì)應(yīng)；路對(duì)應(yīng)； (9)對(duì)應(yīng)圈的長(zhǎng)度相等；對(duì)應(yīng)路的長(zhǎng)度相等； ,45,例14.圖24中(a)、(b)兩圖不同構(gòu)。,46,Ulam猜想(1960). 1960年 Ulam提出如下關(guān)于圖同構(gòu)的著名猜想，至今無人能夠證明或否定。 設(shè)G=(V,E)及G=(V,E)是兩個(gè)圖，其結(jié)點(diǎn)集分別為 V=v1, v2, , vn 及 V=v1, v2, , vn (n3) ，則 (iN)(1in)(Hi Hi) (G G) ，即 若G和G 的n 對(duì)特殊真子圖對(duì)應(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.路與圈 定義與實(shí)例 基本概念 可達(dá)性 圖的連通性,48,3.路與圈 定義1.途徑(way) 設(shè)G=(V,E,)是一圖。G的有限非空點(diǎn)邊交錯(cuò)序列 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)時(shí)，有ei+1 ei (1in)(無向圖)，則稱其為G的一條從v0到vk的途徑。v0稱為途徑w的起點(diǎn)，vk稱為途徑w的終

34、點(diǎn)，k稱為途徑w的長(zhǎng)度。 注：當(dāng)G=(V,E)是一簡(jiǎn)單圖時(shí)，在實(shí)際應(yīng)用中，常用純邊列或純點(diǎn)列的方式表示途徑： (1) w=(e1,e2, ,ek) ； (2)w=(v0, v1), (v1, v2), ,(vk-1, vk) ； (3)w=(v0, v1, v2, ,vk-1, vk) 。,49,途徑w實(shí)際上是一個(gè)動(dòng)態(tài)的過程；其在圖G上的靜態(tài)軌跡是圖G的一個(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的長(zhǎng)度(即|P|=k)。 (2)若v0= vk ，則稱此途徑w是一個(gè)圈；記為 C=(v0, v1, v2,vk-1, vk)，并稱k為圈C的長(zhǎng)度(即|C|=k)。 定義3.可達(dá)性(reachablil

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

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

38、二：連通性是有強(qiáng)弱之分的； (1)若圖G中任二結(jié)點(diǎn)間都至少存在著一條路可達(dá)，則稱圖 G是1-連通的； (2)若圖G中任二結(jié)點(diǎn)間都至少存在著k條不同的路可達(dá)，則 稱圖G是k-連通的(k2)； 通常所說的連通性實(shí)際上是指1-連通。 1-連通的連通 性較差，重要的信道圖網(wǎng)絡(luò)，比如軍事信道圖網(wǎng)絡(luò)，其連 通性至少在2-連通以上。,53,例1.在圖2中由結(jié)點(diǎn)v1到結(jié)點(diǎn)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é)點(diǎn)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語言中，一個(gè)復(fù)合語句以BEGIN開始，END結(jié)束，其中若干個(gè)語句用分號(hào)隔開。所以，執(zhí)行一個(gè)Pascal語言中的一條復(fù)合語句，可以認(rèn)為是從圖3(a)中的BEGIN開始到END結(jié)束走完一條路。 (2)Pascal語言中的“標(biāo)識(shí)符”可以認(rèn)為是圖3(b)中從“入口”到“出口”的一條路。 (3)一個(gè)二進(jìn)制數(shù)可以

40、認(rèn)為是圖3(c)中從“入口”到“出口”的一條路。,55,注：實(shí)際上，分程序是如下的點(diǎn)列： 而不是邊列。 各種程序設(shè)計(jì)語言的文法都可用圖來表示，而且比通常所用的Backus元語言表示的更好、更直觀。 定義4.簡(jiǎn)單路(simple path)簡(jiǎn)單圈(simple cycle) 無重復(fù)邊的路稱為簡(jiǎn)單路； 無重復(fù)邊的圈稱為簡(jiǎn)單圈。 定義5.初級(jí)路(elementary path)初級(jí)圈(elementary cycle) 無重復(fù)點(diǎn)的路稱為初級(jí)路； 無重復(fù)點(diǎn)的圈稱為初級(jí)圈。,56,例4.在圖4中由結(jié)點(diǎn)v1到結(jié)點(diǎn)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)為一簡(jiǎn)單圖，若|V|= n ，則 (1)G中任一初級(jí)路的長(zhǎng)度均不超過n-1； (2)G中任一初級(jí)圈的長(zhǎng)度均不超過n。 證. (1)首先，在任一初級(jí)路中，各結(jié)點(diǎn)都是互不相同的；其次，在任一長(zhǎng)度為k的初級(jí)路中，不同結(jié)點(diǎn)的個(gè)數(shù)必然為k+1。由于圖G中只有n個(gè)不同的結(jié)點(diǎn)，所以G中任一初級(jí)路的長(zhǎng)度不會(huì)超過n-1 。 (2)在任一長(zhǎng)度為k的初級(jí)圈中，其不同的結(jié)點(diǎn)的個(gè)數(shù)也為k。而圖G中僅有n個(gè)不同的結(jié)點(diǎn)，故任一初級(jí)圈的長(zhǎng)度不會(huì)超過n。,58,例5.分油問題(三倒油葫蘆)： 有三個(gè)油桶a,b,c分別可裝8斤,5斤,3斤油。

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

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

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

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

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

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

48、系統(tǒng)產(chǎn)生死鎖 資源分配圖G中含有 強(qiáng)連通支(有向圈) 例10.圖的強(qiáng)連通性概念在檢測(cè)遞歸調(diào)用問題上的應(yīng)用。 程序設(shè)計(jì)中，程序設(shè)計(jì)人員一個(gè)很重要的任務(wù)是需要弄清一個(gè)程序中的調(diào)用關(guān)系是否具有遞歸性。但在多個(gè)過程中，其遞歸性往往不是很清楚的。,68,過程調(diào)用圖G是一個(gè)有向圖，它表達(dá)了程序中過程間的調(diào)用狀態(tài)。在圖G中結(jié)點(diǎn)表示程序的過程，邊表示過程間的調(diào)用情況。當(dāng)過程Pi調(diào)用過程Pj時(shí)，則從結(jié)點(diǎn)Pi到結(jié)點(diǎn)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中含有強(qiáng)連通支(有向圈)。,69,4.圖的矩陣表示 鄰接矩陣 關(guān)聯(lián)矩陣 可達(dá)矩陣 Warshall算法 可達(dá)矩陣與圖的連通性,70,4.圖的矩陣表示 定義1.鄰接矩陣(adjacency matrix 或 connection matrix) 設(shè)G=(V,E)是一簡(jiǎn)單圖(有向或無向)，V=n ，并且設(shè)V=v1,v2,vn已被強(qiáng)行命名。則 定義n階方陣 A=(aij) nn ，其中 為圖G的鄰接矩陣。,例1.有向圖G的圖示如圖1所示。 V =v1,v2, v3, v4已強(qiáng)行命名

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

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

52、強(qiáng)行命名。則 定義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 已強(qiáng)行命名。 則圖G的關(guān)聯(lián) 矩陣為 注：有向圖的關(guān)聯(lián)矩陣的特點(diǎn)是每列一個(gè)正1，一個(gè)負(fù)1。這正好對(duì)應(yīng)相應(yīng)邊的起點(diǎn)和終點(diǎn)。,76,例4.無向圖G的圖示如圖4所示。 V =v1,v2, v3, v4 , v5, v6已強(qiáng)行命名。 則圖G的鄰接矩陣為 注：無向圖的關(guān)聯(lián)矩陣的特點(diǎn)是每列兩個(gè)1。這正好對(duì)應(yīng)相應(yīng)邊的兩個(gè)端點(diǎn)。,77,定義3.可達(dá)矩陣(reachab

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

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

55、矩陣冪算法求圖5所示的有向圖G的可達(dá)矩陣。 圖G的鄰接矩陣及其矩陣冪為,81,有向圖G的可達(dá)矩陣 R=AA(2)A(3) A(4) = 。 矩陣冪算法的計(jì)算工作量： 從表2可得矩陣冪算法的(時(shí)間)復(fù)雜性是n4級(jí)的； (空間)復(fù)雜性是n3級(jí)的。,82,可達(dá)矩陣的計(jì)算方法二：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é)點(diǎn)vi到結(jié)點(diǎn)vj有直接邊或者有通過結(jié)點(diǎn)v1,v2, ,vk的路 而這點(diǎn)正是Warshall算法正確性的要點(diǎn)； Warshall算法實(shí)際上是一個(gè)無層次的、前步結(jié)果即用、一步輸出結(jié)果的迭代過程。這里的分層是人為的、免強(qiáng)的、不自然的。,83,例7.用Warshall算法求圖5所示的有向圖G的可達(dá)矩陣。 圖G的鄰接矩陣及各層可達(dá)矩陣冪為 Warshall算法的計(jì)算工作量： 從表

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