第九的基本概念及其矩陣表示

1、離散數(shù)學(xué)離散數(shù)學(xué)大連理工大學(xué)軟件學(xué)院大連理工大學(xué)軟件學(xué)院陳志奎陳志奎2第第9章章 圖的基本概念及其矩陣表示論圖的基本概念及其矩陣表示論3 圖論（圖論（Graph TheoryGraph Theory）是數(shù)學(xué)的一個）是數(shù)學(xué)的一個分支。它以圖為研究對象。圖論中的圖是分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構(gòu)成的由若干給定的點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點代表事物，用連間的某種特定關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有這種接兩點的線表示相應(yīng)兩個事物間具有這種關(guān)系。關(guān)系。

2、圖論起源于著名的柯尼斯堡七橋問題。圖論起源于著名的柯尼斯堡七橋問題。在柯尼斯堡的普萊格爾河上有七座橋?qū)⒑釉诳履崴贡さ钠杖R格爾河上有七座橋?qū)⒑又械膷u及島與河岸聯(lián)結(jié)起來，如下圖所示，中的島及島與河岸聯(lián)結(jié)起來，如下圖所示，A A、B B、C C，D D表示陸地。表示陸地。 4圖論的起源圖論的起源 哥尼斯堡七橋問題 ：17世紀的東普魯士有一座哥尼斯堡（Konigsberg）城，城中有一條普雷格爾（Pregel）河，全城共有七座橋?qū)⒑又械膷u及島與河岸聯(lián)結(jié)起來，如下圖所示，a,b,c,d表示陸地。 從四塊陸地的任何一塊出發(fā)，怎樣通過且僅通過每座橋一次，最終回到出發(fā)地點？5圖論的起源圖論的起源 1736年瑞

3、士大數(shù)學(xué)家列昂哈德歐拉（Leonhard Euler）解決了這一問題，他用了科學(xué)研究中最一般的方法抽象。用四個字母a,b,c,d表示四塊陸地，并用7條線表示7座橋，從而將七橋問題抽象為圖的問題，尋找經(jīng)過圖中每邊一次且僅一次的回路，后來人們把有這樣回路的圖稱為歐拉圖。6圖論的起源圖論的起源 歐拉證明了這個問題沒有解，并且推廣了這個問題，給出了對于一個給定的圖可以某種方式走遍的判定法則。這項工作使歐拉成為圖論的創(chuàng)始人。 歐拉被稱為圖論之父，1736年也被稱為“圖論元年”。 圖論部分共分為三章：圖的基本概念及其矩陣表示，幾種圖的介紹，樹。本章將首先討論圖論中的一些基本概念，繼之闡述圖的基本性質(zhì)，而后

4、介紹圖的矩陣表示方法。7主要內(nèi)容主要內(nèi)容 圖的基本概念圖的基本概念 子圖和圖的運算子圖和圖的運算 路徑、回路、連通性路徑、回路、連通性 圖的矩陣表示圖的矩陣表示 歐拉圖歐拉圖 哈密爾頓圖哈密爾頓圖 二部圖、平面圖二部圖、平面圖 網(wǎng)絡(luò)網(wǎng)絡(luò) 樹樹基礎(chǔ)知識特殊圖89.1圖的基本概念圖的基本概念 圖是由一些頂點和連接這些頂點的一些邊所組成的離散結(jié)構(gòu)。 根據(jù)連接頂點對的邊的種類和數(shù)目的不同，圖有多種類型。幾乎每一門可以想到的學(xué)科，都有用圖模型來解決的問題。9圖的種類圖的種類(1) 如果 ，則稱 為無向圖。(2) 如果 ，則稱 為有向圖。1212: ,Ev vvVvV,GV E :EVV,GV E 無論是

5、無向圖還是有向圖，都統(tǒng)稱為圖，其中V的元素稱為圖G的結(jié)點，E的元素稱為圖G的邊，圖G的結(jié)點數(shù)目稱為圖的階。 可以用幾何圖形表示上面定義的圖。用小圓圈可以用幾何圖形表示上面定義的圖。用小圓圈表示結(jié)點。在無向圖中，若表示結(jié)點。在無向圖中，若 ，就用連接，就用連接結(jié)點結(jié)點v1和和v2的無向線段表示邊的無向線段表示邊e。在有向圖中，。在有向圖中，若若 ，就用，就用v1指向指向v2的有向線段表示邊的有向線段表示邊e。 12( ) ,ev v12( ),ev v 10圖的基本概念圖的基本概念定義：定義： 設(shè)無向圖設(shè)無向圖 ， ， ,GV E 12,e e eE12,v vV(1)如果 ，則稱e與v1(或v

6、2)互相關(guān)聯(lián)。e連接v1和v2，v1和v2既是e的起點，也是e的終點，也稱v1和v2為點鄰接。 (2)如果兩條不同的邊e1和e2與同一個結(jié)點關(guān)聯(lián)，則稱e1和e2為邊鄰接。 12( ) ,ev v也就是說，共邊的點稱為點鄰接；共點的邊稱為邊鄰接。 11圖的基本概念圖的基本概念定義：設(shè)有向圖定義：設(shè)有向圖 。如。如果果 ，則稱，則稱e連接連接v1和和v2，e與與v1(或或v2)互互相關(guān)聯(lián)，分別稱相關(guān)聯(lián)，分別稱v1和和v2是是e的起點和終點，也稱的起點和終點，也稱v1和和v2鄰接。鄰接。 12,GV EeE v vV 12( ),ev v 例：無向圖例：無向圖e1連接v1和v2，v1和v2鄰接，e1

7、和e2鄰接。 12圖的基本概念圖的基本概念例：有向圖例：有向圖v2和v1分別是e1的起點和終點，v2與v1鄰接。 13圖的基本概念圖的基本概念定義：定義： 設(shè)圖設(shè)圖 ,e1和和e2是是G的兩條不同的邊。的兩條不同的邊。 ,GV E (1)如果與e1關(guān)聯(lián)的兩個結(jié)點相同，則稱e1為自圈(或稱環(huán)和回路)。 (2) 如果 ，則稱e1與e2平行。(3)如果圖G沒有自圈，也沒有平行邊，則稱G為簡單圖。 (4)如果圖G沒有自回路，有平行邊，則稱G為多重邊圖。(5)如果圖G既有自回路，又有平行邊，則稱G為偽圖。12( )( )ee14圖的種類圖的種類例：中國主要城市通訊圖例：中國主要城市通訊圖15圖的種類圖的

8、種類類型邊允許平行邊允許自環(huán)簡單圖無向否否多重圖無向是否偽圖無向是是有向圖有向否是有向多重圖有向是是16度度定義：定義： 。 (1)如果如果G是無向圖，是無向圖，G中與中與v關(guān)聯(lián)的邊和與關(guān)聯(lián)的邊和與v關(guān)關(guān)聯(lián)的自回路的數(shù)目之和稱為聯(lián)的自回路的數(shù)目之和稱為v的度的度(或次或次)，記，記為為(2) 。 (3)如果如果G是有向圖，是有向圖，G中以中以v為起點的邊的數(shù)目為起點的邊的數(shù)目稱為稱為v的出度，記為的出度，記為 ；G中以中以v為終點的為終點的邊的數(shù)目稱為邊的數(shù)目稱為v的入度，記為的入度，記為 ；v的出度的出度與入度之和稱為與入度之和稱為v的度，記為的度，記為 。 ( )Gdv( )Gdv( )G

9、dv注意，在計算無向圖中結(jié)點的度時，自回路注意，在計算無向圖中結(jié)點的度時，自回路要考慮兩遍，因為自回路也是邊。要考慮兩遍，因為自回路也是邊。 ,GV E( )Gdv17度度例：計算下圖中各結(jié)點的度。例：計算下圖中各結(jié)點的度。 v1 v2 v3123( )4 , ()()2GGGdvdvdv123142341234( )()()2( )0,()3()()()1( )2()()3()4DDDDDDDDDDDDdvdvdvdvdvdvdvdvdvdvdvdv18度度定理：在無向圖中，所有節(jié)點的度數(shù)之和等于邊定理：在無向圖中，所有節(jié)點的度數(shù)之和等于邊數(shù)的數(shù)的2倍。倍。 證：因為每條邊給圖G帶來兩度，設(shè)

10、圖G有m條邊，所以圖G共有2m度，等于圖G的所有結(jié)點的度數(shù)之和。 定理：在有向圖中，所有頂點的度數(shù)之和等于定理：在有向圖中，所有頂點的度數(shù)之和等于邊的邊的2倍；所有頂點的入度之和等于所有節(jié)點的倍；所有頂點的入度之和等于所有節(jié)點的出度之和，都等于邊數(shù)。出度之和，都等于邊數(shù)。度 例：結(jié)點的度。1920結(jié)點結(jié)點定義：度數(shù)為奇數(shù)的結(jié)點稱為奇結(jié)點，度數(shù)定義：度數(shù)為奇數(shù)的結(jié)點稱為奇結(jié)點，度數(shù)為偶數(shù)的結(jié)點稱為偶結(jié)點。為偶數(shù)的結(jié)點稱為偶結(jié)點。 定理：任何圖都有偶數(shù)個奇結(jié)點。定理：任何圖都有偶數(shù)個奇結(jié)點。 1Vv v為奇點2Vv v為偶點12( )( )( )2v Vv Vv Vd vd vd vm2( )v

11、Vd v1( )v Vd v1V定義：定義： 度為度為0的結(jié)點稱為孤立結(jié)點，度為的結(jié)點稱為孤立結(jié)點，度為1的結(jié)點稱為端點。的結(jié)點稱為端點。 21一些特殊的簡單圖一些特殊的簡單圖零圖：結(jié)點都是孤立結(jié)點的圖稱為零圖。零圖：結(jié)點都是孤立結(jié)點的圖稱為零圖。平凡圖：一階零圖稱為平凡圖。平凡圖：一階零圖稱為平凡圖。圈圖（圈圖（Cn(n3)）：是由）：是由n個頂點個頂點v1,v2,vn以及以及邊邊v1,v2,v2,v3,vn-1,vn,vn,v1組成的。組成的。22一些特殊的簡單圖一些特殊的簡單圖輪圖：對輪圖：對來說，當給圈圖來說，當給圈圖Cn添加一個頂點，添加一個頂點，并且把這個新頂點與并且把這個新頂點與

12、Cn里的里的n個頂點逐個連接，個頂點逐個連接，可以得到輪圖可以得到輪圖Wn。23一些特殊的簡單圖一些特殊的簡單圖正則圖：正則圖： 所有結(jié)點的度均為自然數(shù)所有結(jié)點的度均為自然數(shù)d的無向的無向圖稱為圖稱為d度正則圖。度正則圖。24一些特殊的簡單圖一些特殊的簡單圖nI完全無向圖：設(shè)完全無向圖：設(shè) ，如果，如果n階簡單無向圖階簡單無向圖G是是n-1度正則圖，則稱度正則圖，則稱G為完全無向圖，記為為完全無向圖，記為Kn。注意：完全無向圖的任意兩個不同結(jié)點都鄰接。注意：完全無向圖的任意兩個不同結(jié)點都鄰接。一至五階完全無向圖 25一些特殊的簡單圖一些特殊的簡單圖注意：完全有向圖的任意兩個不同結(jié)點之間都注意：

13、完全有向圖的任意兩個不同結(jié)點之間都有一對方向相反的有向邊相連接。有一對方向相反的有向邊相連接。 完全有向圖：設(shè)完全有向圖：設(shè) ，每個結(jié)點的出度和入度均，每個結(jié)點的出度和入度均為為n-1的的n階簡單有向圖稱為完全有向圖。階簡單有向圖稱為完全有向圖。nI 一至三階完全有向圖一至三階完全有向圖 26一些特殊的簡單圖一些特殊的簡單圖27特殊類型的圖的一些應(yīng)用特殊類型的圖的一些應(yīng)用局域網(wǎng)：在一座大樓里，像小型計算機和個人局域網(wǎng)：在一座大樓里，像小型計算機和個人電腦這樣的計算機，以及像打印機這樣的外設(shè)，電腦這樣的計算機，以及像打印機這樣的外設(shè)，可以用局域網(wǎng)來連接。有三種常見的局域網(wǎng)拓可以用局域網(wǎng)來連接。有

14、三種常見的局域網(wǎng)拓撲結(jié)構(gòu)。撲結(jié)構(gòu)。28圖的同構(gòu)圖的同構(gòu) 從圖的定義可以看出，圖的最本質(zhì)的內(nèi)容是結(jié)點和邊的關(guān)聯(lián)關(guān)系。兩個表面上看起來不同的圖，可能表達相同的結(jié)點和邊的關(guān)聯(lián)關(guān)系。29圖的同構(gòu)圖的同構(gòu) 實際中，利用圖的同構(gòu)可以研究是否有可能用同樣的方式畫兩個圖。例如化學(xué)里，表示過去已知化合物的圖可以用來判定想象中的新化合物是否已經(jīng)研究過了。30圖的同構(gòu)圖的同構(gòu)定義：設(shè)圖定義：設(shè)圖 和和 。如果存。如果存在雙射在雙射 和雙射和雙射 , 使得對于任意使得對于任意的的 ， 都滿足都滿足 , ,GV E,GV E:f VV:g EEeE12,v vV12121212(),()( ),(),()( ),f v

15、f vev vf vf vev v 若 若(g(e)則稱G與G同構(gòu)，記作 ，并稱f和g為G和G之間的同構(gòu)映射，簡稱同構(gòu)。 GG31圖的同構(gòu)圖的同構(gòu) 換一種更簡單的方法來描述：設(shè)圖和圖，若存在從到的雙射函數(shù)f，對于V中所有的結(jié)點a和b來說，在G中有a到b的邊當且僅當在G中有f(a)和f(b)的邊，就說G與G同構(gòu)。,GV E ,GVE 也就是說，兩個同構(gòu)的圖有同樣多的結(jié)點和邊，并且映射f保持結(jié)點間的鄰接關(guān)系，映射g保持邊之間的鄰接關(guān)系。 圖同構(gòu)的直觀含義，是將其中一個圖經(jīng)過旋轉(zhuǎn)、平移、拉伸等變形后與另一個圖完全重合。32圖的同構(gòu)圖的同構(gòu)例：求證下圖和同構(gòu)。例：求證下圖和同構(gòu)。證明：兩個圖點、邊的數(shù)

16、目都相同。設(shè)函數(shù)f為f(u1)=v1,f(u2)=v4,f(u3)=v3,f(u4)=v2。G中相鄰的點是u1與u2，u2與u4，u4與u3，u3與u1，對應(yīng)的像點f(u1)=v1與f(u2)=v4,f(u2)=v4與f(u4)=v2, f(u4)=v2與f(u3)=v3,f(u3)=v3與f(u1)=v1在H中相鄰。因此，二圖同構(gòu)。33圖的同構(gòu)圖的同構(gòu)兩個圖同構(gòu)必須滿足的必要條件是：(1)頂點個數(shù)相同(2)邊數(shù)相同(3)度數(shù)相同的頂點個數(shù)相同(4)K度頂點的導(dǎo)出子圖同構(gòu)判定圖的同構(gòu)比較難，但是卻可以通過上述四點證明圖不同構(gòu)。34圖的同構(gòu)圖的同構(gòu)例：判斷下列兩圖是否同構(gòu)。例：判斷下列兩圖是否同

17、構(gòu)。35圖的同構(gòu)圖的同構(gòu)例：判斷下列兩圖是否同構(gòu)。例：判斷下列兩圖是否同構(gòu)。36 上面兩個圖不是同構(gòu)的，因為左圖中度結(jié)點都和兩個度結(jié)點相關(guān)聯(lián)，而右圖中的度結(jié)點和一個度結(jié)點相關(guān)聯(lián)還和一個度結(jié)點相關(guān)聯(lián)。37圖的同構(gòu)圖的同構(gòu)例：判斷下列兩圖是否同構(gòu)。例：判斷下列兩圖是否同構(gòu)。38 上面兩個圖是同構(gòu)的。我們只要構(gòu)造雙射函數(shù) f:a1,b1,c1,d1,e1,f1a2,b2,c2,d2,e2,f2 并且f(a1)=f2 ,f(b1)=b2 ,f(c1)=c2 f(d1)=d2 ,f(e1)=a2 ,f(f1)=e2 f是個雙射函數(shù),并且保持了邊的鄰接關(guān)系39圖的同構(gòu)圖的同構(gòu) 判定兩個圖是否同構(gòu)，已知的最

18、好算法具有指數(shù)的最壞情形時間復(fù)雜度（對圖的結(jié)點來說）。不過，解決這個問題的線性平均情形時間復(fù)雜度的算法已經(jīng)找到，而且有希望找到判定兩個圖是否同構(gòu)的多項式最壞情形時間復(fù)雜度算法。一個名叫NAUTY的最佳算法，目前可以在個人電腦上秒之內(nèi)判定帶有100個結(jié)點的兩個圖是否同構(gòu)。40圖模型圖模型 圖可以用在各種模型里，用于不同的行業(yè)。棲息地重疊圖：頂點表示物種，若兩個物種競爭棲息地重疊圖：頂點表示物種，若兩個物種競爭（他們共享某些食物來源），則用無向邊連接表示（他們共享某些食物來源），則用無向邊連接表示他們的頂點。他們的頂點。41圖模型圖模型熟人圖：可以用模型表示人與人之間的各種關(guān)熟人圖：可以用模型表示

19、人與人之間的各種關(guān)系。頂點表示人，當兩個人互相認識時，用一系。頂點表示人，當兩個人互相認識時，用一條無向邊連接這兩個人。據(jù)估計，世界上所有條無向邊連接這兩個人。據(jù)估計，世界上所有人的熟人圖有超過人的熟人圖有超過60億個頂點和可能超過億個頂點和可能超過1萬萬億條邊。億條邊。好萊塢圖：好萊塢圖用頂點表示演員，當兩個好萊塢圖：好萊塢圖用頂點表示演員，當兩個頂點的演員共同出演一部電影時，就用一條無頂點的演員共同出演一部電影時，就用一條無向邊連接這兩個頂點。根據(jù)無聯(lián)網(wǎng)電影數(shù)據(jù)庫，向邊連接這兩個頂點。根據(jù)無聯(lián)網(wǎng)電影數(shù)據(jù)庫，在在2001年年11月，好萊塢圖有月，好萊塢圖有574724個頂點和超個頂點和超過過

20、1600萬條邊，這些頂點所表示的演員出現(xiàn)在萬條邊，這些頂點所表示的演員出現(xiàn)在292609部電影中。部電影中。4243圖模型圖模型循環(huán)賽圖：每個隊其其他所有隊各有一次的比賽稱循環(huán)賽圖：每個隊其其他所有隊各有一次的比賽稱為循環(huán)賽。其中每個頂點表示每個隊，若為循環(huán)賽。其中每個頂點表示每個隊，若a隊擊敗隊擊敗b隊，則有一條從隊，則有一條從a指向指向b的有向邊。的有向邊。44圖模型圖模型合作圖：合作圖可以用來為學(xué)術(shù)論文的合作者關(guān)合作圖：合作圖可以用來為學(xué)術(shù)論文的合作者關(guān)系建立模型。頂點表示某個文章的某個作者系建立模型。頂點表示某個文章的某個作者（人），如果兩個人合作論文，則用無向邊連接（人），如果兩個人

21、合作論文，則用無向邊連接這兩個人。已經(jīng)發(fā)現(xiàn)在數(shù)學(xué)研究論文上合作的合這兩個人。已經(jīng)發(fā)現(xiàn)在數(shù)學(xué)研究論文上合作的合作圖有超過作圖有超過337000個頂點和個頂點和496000條邊。條邊。網(wǎng)絡(luò)圖：互聯(lián)網(wǎng)可以用有向圖來建模，用頂點表網(wǎng)絡(luò)圖：互聯(lián)網(wǎng)可以用有向圖來建模，用頂點表示網(wǎng)頁，若有從網(wǎng)頁示網(wǎng)頁，若有從網(wǎng)頁a指向網(wǎng)頁指向網(wǎng)頁b的鏈接，則做一的鏈接，則做一條從條從a指向指向b的有向邊。網(wǎng)絡(luò)圖幾乎是連續(xù)變化的，的有向邊。網(wǎng)絡(luò)圖幾乎是連續(xù)變化的，幾乎每秒都有新頁面產(chǎn)生而又有其他頁面被刪除。幾乎每秒都有新頁面產(chǎn)生而又有其他頁面被刪除。目前網(wǎng)絡(luò)圖有超過目前網(wǎng)絡(luò)圖有超過10億個頂點和幾百億條邊。許億個頂點和幾百億

22、條邊。許多研究者正在研究網(wǎng)絡(luò)圖的性質(zhì)，以便更好的理多研究者正在研究網(wǎng)絡(luò)圖的性質(zhì)，以便更好的理解網(wǎng)絡(luò)的特性。解網(wǎng)絡(luò)的特性。45圖模型圖模型優(yōu)先圖與并發(fā)處理：通過并發(fā)的執(zhí)行某些語句，優(yōu)先圖與并發(fā)處理：通過并發(fā)的執(zhí)行某些語句，計算機程序可能執(zhí)行的更快。但重要的是，要計算機程序可能執(zhí)行的更快。但重要的是，要避免語句執(zhí)行時還要用到尚未執(zhí)行語句的結(jié)果。避免語句執(zhí)行時還要用到尚未執(zhí)行語句的結(jié)果。語句與前面語句的相關(guān)性可以表示成有向圖。語句與前面語句的相關(guān)性可以表示成有向圖。用頂點表示某個語句，若在用頂點表示某個語句，若在a語句執(zhí)行完之前不語句執(zhí)行完之前不能執(zhí)行能執(zhí)行b語句，則引出一個從語句，則引出一個從a到

23、到b的有向邊，這的有向邊，這樣的圖稱為優(yōu)先圖。樣的圖稱為優(yōu)先圖。46圖模型圖模型479.2子圖和圖的運算子圖和圖的運算 定義：設(shè)定義：設(shè) 和和 為圖。為圖。 ,GV E ,GVE (1)如果 ，則稱G是G的子圖，記作 ，并稱G是G的母圖。(2)如果 ，則稱G是G的真子圖，記作 。(3)如果 ，則稱G是G的生成子圖。 ,VV EEGG,VV EEGG,VV EE平凡生成子圖：對于圖，平凡生成子圖：對于圖，G本身以本身以及零圖都是及零圖都是G的平凡生成子圖。的平凡生成子圖。,GV E ,GV 48子圖子圖定義：定義： 設(shè)圖設(shè)圖 ， 且且 。以。以V為結(jié)為結(jié)點集合，以起點和終點均在點集合，以起點和終

24、點均在V中的邊的全體為邊集中的邊的全體為邊集合的合的G的子圖，稱為由的子圖，稱為由V導(dǎo)出的導(dǎo)出的G的子圖，記為的子圖，記為GV。若。若 ，導(dǎo)出子圖，導(dǎo)出子圖 ，記為，記為 。 ,GV E VVV VVG VVG V 是從G中去掉V中的結(jié)點以及與這些結(jié)點關(guān)聯(lián)的邊而得到的圖G的子圖。 G V定義：設(shè)圖定義：設(shè)圖 ， 且且 ， 。以。以 為結(jié)點集合，以為結(jié)點集合，以 為邊集合的為邊集合的G的子圖稱為由的子圖稱為由E導(dǎo)出的子圖。導(dǎo)出的子圖。 ,GV E EEE |()()Vv vVe eEve 與 關(guān)聯(lián)VE49子圖子圖 從圖示看，圖G的子圖是圖G的一部分，G的真子圖的邊數(shù)比G的邊數(shù)少，G的生成子圖與G

25、有相同的結(jié)點，G的導(dǎo)出子圖 是G的以 為結(jié)點集合的最大子圖。 G VV例：例：(b)是(a)的子圖、真子圖和生成子圖，(c)是(a)的由1,2,3,4導(dǎo)出的子圖。 子圖5051圖的運算圖的運算定義：設(shè)圖定義：設(shè)圖 和和 同為無向圖同為無向圖或同為有向圖?；蛲瑸橛邢驁D。 , ,GV E,GV E(1)如果對于任意 具有 ，則稱G 和 是可運算的。(2)如果 ，則稱G和 是不相交的。(3)如果 ，則稱G和 是邊不相交的。 eEE( )( )eeGVVEE GEE G52圖的運算圖的運算設(shè)圖 和 為可運算的。 1111,GV E 2222,GV E (1)稱以 為結(jié)點集合，以 為邊集合的G1和G2的

26、公共子圖為G1和G2的交，記為 。 (2)稱以 為邊集合，以與這些邊關(guān)聯(lián)的結(jié)點集合為點集的G1和G2的公共母圖為G1和G2的并，記為 。 (3)稱以 為結(jié)點集合，以 為邊集合的 的子圖為G1和G2的環(huán)和，記為 。 12EE12VV12GG12EE12VV12EE12GG12GG12GG圖的運算圖的運算5354圖的運算圖的運算并不是任何兩個圖都有交、并和環(huán)和。如上圖 ，(a)和(b)沒有交和并，因為邊e1在(a)中連接v1和v2，而在(b)中連接v2和v3。 55圖的運算圖的運算定理：定理： 設(shè)圖設(shè)圖 和和 為可運算的。為可運算的。 1111,GV E 2222,GV E (1)如果 ，則存在唯

27、一的 。(2)存在唯一的 和 。12VV 12GG12GG12GG證：設(shè)證：設(shè)G1和和G2同為有向圖，若同為無向圖也可同為有向圖，若同為無向圖也可同樣證明。同樣證明。 (1)定義 為：對任意的 ， 。顯然， .設(shè)圖 和 均為G1和G2的交。因為 ，對任意 .因為 ，對任意 。這表明 。因此， 。 121212:() ()EEVVVV12eEE12( )( )( )eee121212(),(),VVEEGG 1212,GVV EE 1212,GVV EE1GG121,( )( )eEEee1GG121,( )( )eEEeeGG56圖的運算圖的運算證：證： （2）定義）定義 如下：如下： 121

28、212() ()EEVVVV12( )( )( )eee121eEeEE顯然， 。設(shè) 和 均為G1和G2的并。因為 且 ，所以對任意 ， ，這表明 ，因此 。 121212,VV EEGG 1212,GVV EE1212,GVV EE1GG1GG1eE1( )( )( )eeeGG對于存在唯一的 可同樣證明。 12GG57圖的運算圖的運算定義：定義： 設(shè)圖設(shè)圖 ,記記 為為 ，對任意，對任意 ，記，記 為為 。 ,GV EEE ,/()V EEEEGEeE GeGe 是從G中去掉E中的邊所得到的G的子圖。GE定義：設(shè)圖定義：設(shè)圖 和和 同為無向圖同為無向圖或同為有向圖，并且邊不相交，記或同為有

29、向圖，并且邊不相交，記 為為 。 ,GV E ,GVE GGGE 是由G增加E中的邊所得到的圖，其中 指出E中的邊與結(jié)點的關(guān)聯(lián)關(guān)系。GE58圖的運算圖的運算59上面的例子中，(a)和(b)分別為G1和G2 ,則圖c,d,e分別是 (G1 G2)-v5,v6,(G1 G2)-g,h, G2 +E其中g(shù)=g,v1,v3圖的運算圖的運算609.3路徑、回路和連通性路徑、回路和連通性 61路徑和回路路徑和回路例：分析下列無向圖例：分析下列無向圖在該無向圖中， 是路徑，但不是簡單路徑； 是簡單路徑，但不是基本路徑； 是閉路徑，但不是簡單閉路徑。另外，如果從路徑 中去掉閉路徑 就得到基本路徑 。 2342

30、3v bv dv ev bv2334v bv cv dv333v cv cv133v gv cv33v cv13v gv62路徑和回路路徑和回路例：分析下列有向圖例：分析下列有向圖在該有向圖中， 是路徑，但不是簡單路徑； 是簡單路徑，但不是基本路徑。從 中去掉閉路徑1a1就得到基本路徑1c4。可以看出，從2至1存在多條路徑，但從1至2沒有路徑。 1 4 1 4c b c1 1 4a c1 1 4a c63路徑和回路路徑和回路注意：注意：單獨一個結(jié)點單獨一個結(jié)點v也是路徑，它是長度為也是路徑，它是長度為0的基本路徑。的基本路徑。因此，任何結(jié)點到其自身總存在路徑。因此，任何結(jié)點到其自身總存在路徑。

31、在無向圖中，若從結(jié)點在無向圖中，若從結(jié)點v至結(jié)點至結(jié)點v存在路徑，則從存在路徑，則從v至至v必存在路徑。而在有向圖中，從結(jié)點必存在路徑。而在有向圖中，從結(jié)點v至至v結(jié)點存結(jié)點存在路徑，而從在路徑，而從v至至v卻不一定存在路徑。卻不一定存在路徑。 設(shè)路徑 和 ，用P1P2記路徑 10 1 11nnnPv evve v1111nmmmPv e vvev0 1 11111nnnmmmv evve v e vvev路徑和回路路徑和回路64例：例：“擺渡問題擺渡問題”：一個人帶有一條狼、一頭羊和：一個人帶有一條狼、一頭羊和一捆白菜，要從河的左岸渡到右岸去，河上僅有一一捆白菜，要從河的左岸渡到右岸去，河上

32、僅有一條小船，而且只有人能劃船，船上每次只能由人帶條小船，而且只有人能劃船，船上每次只能由人帶一件東西過河。另外，不能讓狼和羊、羊和菜單獨一件東西過河。另外，不能讓狼和羊、羊和菜單獨留下。問怎樣安排擺渡過程？留下。問怎樣安排擺渡過程？65路徑和回路路徑和回路解：河左岸允許出現(xiàn)的情況有以下解：河左岸允許出現(xiàn)的情況有以下10種情況：人狼種情況：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我們把這菜、羊及空（各物品已安全渡河），我們把這10種種狀態(tài)視為狀態(tài)視為10個點，若一種狀態(tài)通過一次擺渡后變?yōu)閭€點，若一種狀態(tài)通過

33、一次擺渡后變?yōu)榱硪环N狀態(tài)，則在兩種狀態(tài)（點）之間畫一直線，另一種狀態(tài)，則在兩種狀態(tài)（點）之間畫一直線，得到上圖。得到上圖。這樣擺渡問題就轉(zhuǎn)化成在圖中找出以這樣擺渡問題就轉(zhuǎn)化成在圖中找出以“人狼羊菜人狼羊菜”為起點，以為起點，以“空空”為終點的簡單路。容易看出，只為終點的簡單路。容易看出，只有兩條簡單路符合要求，即：有兩條簡單路符合要求，即：（1）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空；人羊、空；（2）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。人羊、空。對于簡單路（對于簡單路（1）的安排為：人帶

34、羊過河；人回來；）的安排為：人帶羊過河；人回來；帶狼過河；放下狼再將羊帶回；人再帶菜過河；人帶狼過河；放下狼再將羊帶回；人再帶菜過河；人回來；帶羊過河。回來；帶羊過河。對于簡單路（對于簡單路（2）的安排為：人帶羊過河；人回來；）的安排為：人帶羊過河；人回來；帶菜過河；放下菜再將羊帶回；人再帶狼過河；人帶菜過河；放下菜再將羊帶回；人再帶狼過河；人回來；帶羊過河。回來；帶羊過河。上述的兩種方案都是去上述的兩種方案都是去4次、回次、回3次，且不會再有比次，且不會再有比這更少次數(shù)的渡河辦法了。這更少次數(shù)的渡河辦法了。66路徑和回路路徑和回路定理：定理： 設(shè)設(shè)v和和v是圖是圖G中的結(jié)點。如果存在從中的結(jié)

35、點。如果存在從v至至v的路徑，則存在從的路徑，則存在從v至至v的基本路徑。的基本路徑。 證：設(shè)當從證：設(shè)當從v至至v存在長度小于存在長度小于 的路徑時，從的路徑時，從v至至v必存在基本路徑。必存在基本路徑。如果存在路徑如果存在路徑 ，其中，其中 ，并且，并且有有i和和j滿足滿足 且且 ，則，則 是從是從v至至v的長度為的長度為l-j+i的路徑。根據(jù)歸納假設(shè)，存的路徑。根據(jù)歸納假設(shè)，存在從在從v至至v的基本路徑。的基本路徑。 0 1 11lllv evv ev0,lvv vv0ijl ijvv0 1 1111ijjlllv evvevv evl67路徑和回路路徑和回路定理：定理：n階圖中的基本路

36、徑的長度小于或等于階圖中的基本路徑的長度小于或等于n-1。 證：在任何基本路徑中，出現(xiàn)于序列中的各結(jié)點都證：在任何基本路徑中，出現(xiàn)于序列中的各結(jié)點都是互不相同的。在長度為是互不相同的。在長度為l的任何基本路徑中，不的任何基本路徑中，不同的結(jié)點數(shù)目是同的結(jié)點數(shù)目是l+1。因為集合。因為集合V僅有僅有n個不同的結(jié)個不同的結(jié)點，所以任何基本路徑的長度不會大于點，所以任何基本路徑的長度不會大于n-1。對于。對于長度為長度為l的基本循環(huán)來說，序列中有的基本循環(huán)來說，序列中有l(wèi)個不同的結(jié)點。個不同的結(jié)點。因為是因為是n階圖，所以任何基本循環(huán)的長度，都不會階圖，所以任何基本循環(huán)的長度，都不會超過超過n，綜上

37、所述，在，綜上所述，在n階圖中，基本路徑的長度不階圖中，基本路徑的長度不會超過會超過n-1。 68路徑和回路路徑和回路路徑可以表示很多圖模型中的有用信息：熟人關(guān)系圖中的通路（最小世界原理）合作圖中的通路（數(shù)學(xué)家的埃德斯數(shù)）好萊塢圖中的通路（演員的培根數(shù)（著名演員凱文.培根）69路徑和回路路徑和回路定理：設(shè)定理：設(shè)v是圖是圖G的任意結(jié)點，的任意結(jié)點，G是回路或有向回路，是回路或有向回路，當且僅當當且僅當G的階與邊數(shù)相等，并且在的階與邊數(shù)相等，并且在G中存在這樣中存在這樣一條從一條從v到到v的閉路徑，使得除了的閉路徑，使得除了v在該閉路徑中出在該閉路徑中出現(xiàn)兩次外，其余結(jié)點和每條邊都在該閉路徑上恰

38、出現(xiàn)兩次外，其余結(jié)點和每條邊都在該閉路徑上恰出現(xiàn)一次?，F(xiàn)一次。證：見書上。證：見書上。70路徑和回路路徑和回路71路徑和回路路徑和回路72路徑和回路路徑和回路例：判斷圖例：判斷圖 (a)有沒有有向回路。有沒有有向回路。73連通性連通性定義：設(shè)定義：設(shè)v1和和v2是圖是圖G的結(jié)點。如果在的結(jié)點。如果在G中存在中存在從從v1至至v2的路徑，則稱在的路徑，則稱在G中從中從v1可達可達v2或或v1和和v2是連通的，否則稱在是連通的，否則稱在G中從中從v1不可達不可達v2。對于圖對于圖G的結(jié)點，用的結(jié)點，用R(v)表示從表示從v可達的全體結(jié)可達的全體結(jié)點的集合。點的集合。 注意：在無向圖中，若從注意：在

39、無向圖中，若從v1可達可達v2，則從，則從v2必必可達可達v1；而在有向圖中，從；而在有向圖中，從v1可達可達v2不能保證不能保證從從v2必可達必可達v1。無論無向圖還是有向圖，任何。無論無向圖還是有向圖，任何節(jié)點到自身都是可達的。節(jié)點到自身都是可達的。 74連通性連通性75連通性連通性76連通性連通性77連通圖連通圖78連通圖連通圖無向圖 是連通的，當且僅當對于任意 ， 。 ,GV E vV( )R vV79連通圖連通圖由于可達性的非對稱性，有向圖的連通概念要復(fù)雜得多，這里需要用到基礎(chǔ)圖的概念。 80連通圖連通圖定義：設(shè)定義：設(shè)G是有向圖。是有向圖。 (1)如果G中任意兩個結(jié)點都互相可達，則

40、稱G是強連通的。(2)如果對于G的任意兩結(jié)點，必有一個結(jié)點可達另一個結(jié)點，則稱G是單向連通的。(3)如果G的基礎(chǔ)圖是連通的，則稱G是弱連通的。81子圖和分支子圖和分支定義：設(shè)定義：設(shè)G是是G的具有某種性質(zhì)的子圖，并且對于的具有某種性質(zhì)的子圖，并且對于G的具有該性質(zhì)的任意子圖的具有該性質(zhì)的任意子圖G，只要，只要GG，就有就有G=G，則稱，則稱G相對于該性質(zhì)是相對于該性質(zhì)是G的極大子圖。的極大子圖。 定義：定義： 無向圖無向圖G的極大連通子圖稱為的極大連通子圖稱為G的分支的分支 。定義：設(shè)定義：設(shè)G是有向圖：是有向圖：（1）G的極大強連通子圖稱為G的強分支。（2）G的極大單向連通子圖稱為G的單向分

41、支。（3）G的極大弱連同子圖稱為G的弱分支。82子圖和分支子圖和分支定理：連通無向圖恰有一個分支。非連通無向定理：連通無向圖恰有一個分支。非連通無向圖有一個以上分支。圖有一個以上分支。 定理：強連通（單向連通，弱連通）有向圖恰定理：強連通（單向連通，弱連通）有向圖恰有一個強分支（單向分支，弱分支）；非強連有一個強分支（單向分支，弱分支）；非強連通（非單向連通，非弱連通）有向圖有一個以通（非單向連通，非弱連通）有向圖有一個以上強分支（單向分支，弱分支）。上強分支（單向分支，弱分支）。 83子圖和分支子圖和分支例：例：有4個強分支，即 123123112 , ,v v ve e eev v2233

42、31456, , , , ,ev vev vvvv 每個結(jié)點恰處于一個強分支中，而邊 不在任何強分支中。G有兩個單向分支，即 和 。顯然， 處于兩個單向分支中，G只有一個弱分支，即其本身。 456,e e e6 Gv56 ,G v v5v84子圖和分支子圖和分支 注意：注意： 無向圖的每個結(jié)點和每條邊都恰在一個連無向圖的每個結(jié)點和每條邊都恰在一個連通分支中；有向圖中，并不是每個邊都恰通分支中；有向圖中，并不是每個邊都恰在一個強分支中。在一個強分支中。 在簡單有向圖中，每個結(jié)點每條邊都恰在在簡單有向圖中，每個結(jié)點每條邊都恰在一個弱分支中。一個弱分支中。 在簡單有向圖中，每個結(jié)點每條邊至少位在簡單

43、有向圖中，每個結(jié)點每條邊至少位于一個單項分支中。于一個單項分支中。85由結(jié)點集合v1，v2，v3，v4，v5，v6和v7形成的誘導(dǎo)子圖都是強分圖;由結(jié)點集合v1，v2，v3，v4，v5，v7，v4，v5和v6，v5所成的誘導(dǎo)子圖都是單向分圖；由結(jié)點集合v1，v2，v3，v4，v5，v6，v7形成的誘導(dǎo)子圖是弱分圖。子圖和分支子圖和分支86資源分配圖資源分配圖 下面給出簡單有向圖的一個應(yīng)用資源分配圖。 在多道程序的計算機系統(tǒng)中，可以同時執(zhí)行多個程序。實際上，程序共享計算機系統(tǒng)中的資源，如磁帶機、磁盤設(shè)備、CPU、主存貯器和編譯程序等。操作系統(tǒng)對這些資源負責分配給各個程序。當一個程序要求使用某種資

44、源，它要發(fā)出請求，操作系統(tǒng)必須保證這一請求得到滿足。87死鎖狀態(tài)死鎖狀態(tài) 對資源的請求可能發(fā)生沖突。如程序A控制著資源r1，請求資源r2；但程序B控制著資源r2，請求資源r1。這種情況稱為處于死鎖狀態(tài)。然而沖突的請求必須解決，資源分配圖有助發(fā)現(xiàn)和糾正死鎖。88假設(shè)條件假設(shè)條件 假設(shè)某一程序?qū)σ恍┵Y源的請求，在該程序運行完之前必須都得到滿足。在請求的時間里，被請求的資源是不能利用的，程序控制著可利用的資源，但對不可利用的資源則必須等待。89分析分析 令Pt = p1，p2，pm表示計算機系統(tǒng)在時間t的程序集合，Qt Pt是運行的程序集合，或者說在時刻t至少分配一部分所請求的資源的程序集合。Rt

45、= r1，r2，rn是系統(tǒng)在時刻t的資源集合。資源分配圖Gt = 是有向圖，它表示了時間t系統(tǒng)中資源分配狀態(tài)。把每個資源ri看作圖中一個結(jié)點，其中i=1，2，n。表示有向邊，E當且僅當程序pkPt已分配到資源ri且等待資源rj。90分析（續(xù)）分析（續(xù)）例如，令Rt=r1，r2，r3，r4，Qt=p1，p2，p3，p4。資源分配狀態(tài)是：p1占用資源r4且請求資源r1，p2占用資源r1且請求資源r2和r3，p3占用資源r2且請求資源r3，p4占用資源r3且請求資源r1和r4，于是，可得到資源分配圖Gt=如圖16.2.7所示。能夠證明，在時刻t計算機系統(tǒng)處于死鎖狀態(tài)iff資源分配圖Gt中包含強連通圖

46、。91前例資源分配圖前例資源分配圖92割集割集有時刪除一個結(jié)點和它所關(guān)聯(lián)的邊，就產(chǎn)生帶有比原圖更多的連通分支的子圖。把這樣的結(jié)點稱為割點。有時刪除一條邊，就產(chǎn)生帶有比原圖更多的連通分支的子圖，把這樣的邊叫做割邊或者橋。939.4圖的矩陣表示圖的矩陣表示 鄰接矩陣鄰接矩陣定義： 設(shè) 是一個簡單有向圖，其中的結(jié)點集合 ，并且假定各結(jié)點已經(jīng)有了從結(jié)點v1到vn的次序。試定義一個nn的矩陣A，使得其中的元素 , ,GV E12 ,nVv vvi j1 ,vvEjvvEija當i (1)0 當則稱這樣的矩陣A是圖G的鄰接矩陣。 94鄰接矩陣鄰接矩陣定義：元素或為定義：元素或為0或為或為1的任何矩陣，都稱

47、為比特矩的任何矩陣，都稱為比特矩陣或布爾矩陣。陣或布爾矩陣。 鄰接矩陣也是布爾矩陣，第i行上值為1的元素的個數(shù)，等于結(jié)點vi的出度；第j列上值為1的元素的個數(shù)，等于結(jié)點vj的入度。 95鄰接矩陣鄰接矩陣圖的鄰接矩陣不具有唯一性。對于給定簡單有向圖 來說，其鄰接矩陣依賴于集合V中的各元素間的次序關(guān)系。,GV E 給定兩個有向圖和相對應(yīng)的鄰接矩陣，如果首先在一個圖的鄰接矩陣中交換一些行，而后交換相對應(yīng)的各列，從而有一個圖的鄰接矩陣，能夠求得另外一個圖的鄰接矩陣，則事實上這樣的兩個有向圖，必定是互為同構(gòu)的。 96鄰接矩陣鄰接矩陣例：寫出下圖的鄰接矩陣，并計算各個節(jié)點的出度例：寫出下圖的鄰接矩陣，并計

48、算各個節(jié)點的出度和入度。和入度。解：首先給各結(jié)點安排好一個解：首先給各結(jié)點安排好一個次序，譬如說是次序，譬如說是 。得出鄰接矩陣如下：得出鄰接矩陣如下： 12345,v v v v v12345123450100000100010111000011010vvvvvvvAvvv97鄰接矩陣鄰接矩陣上例中，如果重新把各結(jié)點排列成 ，就能寫出另外一個矩陣如下： 52341,v v v v v52341523410101100100110100000101000vvvvvvvAvvv 98鄰接矩陣鄰接矩陣 對于給定圖G，顯然不會因結(jié)點編序不同而使其結(jié)構(gòu)會發(fā)生任何變化，即圖的結(jié)點所有不同編序?qū)嶋H上仍表示

49、同一個圖。換句話說，這些結(jié)點的不同編序的圖都是同構(gòu)的，并且它們的n！個鄰接矩陣都是相似的。 今后將略去這種由于V中結(jié)點編序而引起鄰接矩陣的任意性。而取該圖的任一個鄰接矩陣作為該圖的矩陣表示。99鄰接矩陣鄰接矩陣由鄰接矩陣判斷有向圖的性質(zhì)：如果有向圖是自反的，則鄰接矩陣的主對角線上的各元素，必定都是1。如果有向圖是反自反的，則鄰接矩陣的主對角線上的各元素，必定都是0。對于對稱的有向圖來說，其鄰接矩陣也是對稱的，也就說，對于所有的i和j而言，都應(yīng)有aij=aji。如果給定有向圖是反對稱的，則對于所有的i和j和ij而言，aij=1 蘊含aji=0。 100鄰接矩陣鄰接矩陣可以把簡單有向圖的矩陣表示的

50、概念，推廣到簡單無向圖、多重邊圖和加權(quán)圖。對于簡單無向圖來說，這種推廣會給出一個對稱的鄰接矩陣，在多重邊圖或加權(quán)圖的情況下，可以令 ijijaw其中的wij，或者是邊 的重數(shù)，或者是邊 的權(quán)。另外，若 ，則 。,ijv v,ijv v,ijv vE0ijw 在零圖的鄰接矩陣中，所有元素都應(yīng)該是0，亦即其鄰接矩陣是個零矩陣。101鄰接矩陣鄰接矩陣逆圖的鄰接矩陣：如果給定的圖 是一個簡單有向圖，并且其鄰接矩陣是A，則圖G的逆圖的鄰接矩陣 是A的轉(zhuǎn)置 。對于無向圖或者對稱的有向圖來說，應(yīng) 有 。 ,GV E GTATAA102 在圖上的意義在圖上的意義TBAA定義矩陣 。設(shè) 是鄰接矩陣中的第i行和第

51、j列上的 元素， 是矩陣中的第i行和第j列上的元素(i,j)。于是，對于 來說，有 TBAAija( , )i jijb,1,2,3,i jn1nijikjkkba a如果邊 ，則有 ，如果邊 ，則有 。對于某一個確定的k來說，如 果 和 都是給定圖的邊，則在表示 的上述求和表達式中，應(yīng)該引入基值1。從結(jié)點vi和vj二者引出的邊，如果能共同終止于一些結(jié)點的話，那么這樣的一些結(jié)點的數(shù)目，就是元素 的值。 ,ikv vE1ika ,jkv vE1jka,ikv v,jkv vijbijb103 在圖上的意義在圖上的意義TBAA例：如圖，求例：如圖，求TAA解：解：簡單算法：原矩陣A中，第i行和第j

52、行相交，有幾個1，AAT的第i行第j列就是幾。矩陣的主對角線的元素對應(yīng)了各個節(jié)點的出度。12345123450100000100010111000011010vvvvvvvAvvv12345123450001110101010000010100100TvvvvvvvAvvv1010101000103020001110213TAA104 在圖上的意義在圖上的意義TCA A設(shè) 是鄰接矩陣A中的(i,j)元素； 是矩陣C中的元素。于是，對于 ijaijc1,2, ,in1nijkikjkCa a對于某一個確定的k來說，如果 都是給定圖的邊，則在上式中應(yīng)引入基值1。可得從圖中的一些點所引出的邊，如果能

53、夠同時終止于結(jié)點vi和vj的話，那么這樣的一些結(jié)點的數(shù)目，就是元素Cij的值。 ,kikjv vv v 105 在圖上的意義在圖上的意義例：如圖，求例：如圖，求TA A解：解：簡單算法：原矩陣A中，第i列和第j列相交，有幾個1，ATA的第i行第j列就是幾。矩陣的主對角線的元素對應(yīng)了各個節(jié)點的入度。TCA A12345123450100000100010111000011010vvvvvvvAvvv12345123450001110101010000010100100TvvvvvvvAvvv2101013021001001202101011TA A106鄰接矩陣的冪鄰接矩陣的冪對于 來說，考察鄰

54、接矩陣A的冪An可知，鄰接矩陣A中的第i行和第j列上的元素值1，說明了圖G中存在一條邊，也就是說，存在一條從結(jié)點vi到vj長度為1的路徑。試定義矩陣A2，使得A2中的各元素 為 2,3,4,n 2ija12nijikkjkaa a元素值 等于從vi到vj長度為2的不同路徑的數(shù)目。顯然，矩陣中主對角線上的元素 的值，表示了結(jié)點 上長度為2的循環(huán)的個數(shù)。矩陣A3中的元素值(i,j)依次類推。2ija2iia(1,2, )iv in107鄰接矩陣的冪鄰接矩陣的冪例：例：2300100010110101121110,211101311101000001001110002111AA45211101311

55、11311123321,233213634301011211102222135232AA108鄰接矩陣的冪鄰接矩陣的冪定理：設(shè)定理：設(shè) 是一簡單有向圖，并且是一簡單有向圖，并且A是是G的的鄰接矩陣。對于鄰接矩陣。對于 來說，矩陣來說，矩陣Am中的元中的元素素(i,j)的值，等于從的值，等于從vi到到vj長度為長度為m的路徑數(shù)目。的路徑數(shù)目。 ,GV E 1,2,3,m 證：對于證：對于m進行歸納證明。當進行歸納證明。當m=1時，由鄰接矩陣時，由鄰接矩陣的定義中能夠得到的定義中能夠得到Am=A。設(shè)矩陣。設(shè)矩陣Ak中的元素中的元素(i,j)值值 是是 ，且對于，且對于m=k來說結(jié)論為真。因來說結(jié)論

56、為真。因為為 ，所以應(yīng)有，所以應(yīng)有 kija1kkAA A11nijikkjkkkaaa 是從結(jié)點是從結(jié)點vi出發(fā)，經(jīng)過結(jié)點出發(fā)，經(jīng)過結(jié)點vk到到vj的長的長度為度為k+1的各條路徑的數(shù)目。這里的各條路徑的數(shù)目。這里vk是倒數(shù)第是倒數(shù)第二個結(jié)點。因此，二個結(jié)點。因此， 應(yīng)是從結(jié)點應(yīng)是從結(jié)點vi出發(fā)，經(jīng)出發(fā)，經(jīng)過任意的倒數(shù)第二個結(jié)點到過任意的倒數(shù)第二個結(jié)點到vj的長度為的長度為k+1的的路徑總數(shù)。因此，對于路徑總數(shù)。因此，對于m=k+1，定理成立。，定理成立。 kikkjaa1kija109鄰接矩陣的冪鄰接矩陣的冪根據(jù)上述定理，可得出結(jié)論：能使矩陣Am中的元素(i,j)值是非零的最小正整數(shù)m，就

57、是距離 。對于 和 來說，如果矩陣 中的(i,j)元素值和(j,i)元素值都為0，那么就不會有任何路徑連通結(jié)點vi和vj。因此，結(jié)點vi和vj必定是屬于圖G的不同分圖。 ,ijd v v1,2,1mnijmA110鄰接矩陣的冪鄰接矩陣的冪例：給定一個簡單有向圖例：給定一個簡單有向圖 ，如下圖所示，如下圖所示，其中的結(jié)點集合其中的結(jié)點集合 。試求出圖。試求出圖G的鄰接的鄰接矩陣矩陣A和和A的冪的冪A2，A3,A4。 ,GV E 12345 ,Vv v v v v0100010100010000000100010A111鄰接矩陣的冪解：20101000200010100000100001A3020

58、0020200020000000100010A42020004000202000001000001A112可達性矩陣可達性矩陣 給定一個簡單有向圖 ，并且設(shè)結(jié) 點 ?？芍?，由圖G的鄰接矩陣A能夠直接確定G中是否存在一條從vi到vj的邊。設(shè) ，由矩陣 能夠求得從結(jié)點vi到vj長度為r的路徑數(shù)目。試構(gòu)成矩陣 , ,GV E,ijv vVrIkA2kkBAAA矩陣Bk的(i,j)元素值表示了從結(jié)點vi到vj長度小于或等于r的路徑數(shù)目。當圖中的結(jié)點數(shù)目為n時，矩陣Bn都能夠提供足夠的信息，以表明從圖中的任何結(jié)點到其它結(jié)點的可達性。 113可達性矩陣可達性矩陣定義：定義： 給定一個簡單有向圖給定一個簡單

59、有向圖 ，其中，其中|V|=n，并且假定并且假定G中的各結(jié)點是有序的。試定義一個中的各結(jié)點是有序的。試定義一個nn的路徑矩陣的路徑矩陣P，使得其元素為，使得其元素為 ,GV E 1 0 ijijijvvPvv如果從 到 至少存在一條路徑如果從 到 不存在任何路徑 路經(jīng)矩陣P僅表明了圖中的任何結(jié)點偶對之間是否至少存在一條路徑，以及在任何結(jié)點上存在循環(huán)與否；它并不能指明存在的所有路徑。 114可達性矩陣可達性矩陣例：試構(gòu)成下列有向圖的路徑矩陣例：試構(gòu)成下列有向圖的路徑矩陣P。 解：設(shè)鄰接矩陣解：設(shè)鄰接矩陣A=A1。在前面的。在前面的例中，已經(jīng)求出過矩陣的冪例中，已經(jīng)求出過矩陣的冪A2，A3和和A4

60、, A5。求出矩陣。求出矩陣B5和路徑矩和路徑矩陣陣P如下：如下： 5363431 1 1 1 1586531 1 1 1 1,9148951 1 1 1 1232221 1 1 1 16116641 1 1 1 1BP115可達性矩陣可達性矩陣注意：注意：對于具有對于具有n個結(jié)點的圖而言，長度為個結(jié)點的圖而言，長度為n的路徑不可能的路徑不可能是基本路徑。是基本路徑。 假定圖中的每一個結(jié)點，從它本身出發(fā)總是可達的，假定圖中的每一個結(jié)點，從它本身出發(fā)總是可達的，由矩陣由矩陣Bn-1構(gòu)成路徑矩陣構(gòu)成路徑矩陣P，或由矩陣，或由矩陣Bn構(gòu)成路徑構(gòu)成路徑矩陣矩陣P，這兩種方法都可以采納。，這兩種方法都可