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

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

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

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

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

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

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

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

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

9、dv注意，在計(jì)算無(wú)向圖中結(jié)點(diǎn)的度時(shí)，自回路注意，在計(jì)算無(wú)向圖中結(jié)點(diǎn)的度時(shí)，自回路要考慮兩遍，因?yàn)樽曰芈芬彩沁?。要考慮兩遍，因?yàn)樽曰芈芬彩沁叀?,GV E( )Gdv17度度例：計(jì)算下圖中各結(jié)點(diǎn)的度。例：計(jì)算下圖中各結(jié)點(diǎn)的度。 v1 v2 v3123( )4 , ()()2GGGdvdvdv123142341234( )()()2( )0,()3()()()1( )2()()3()4DDDDDDDDDDDDdvdvdvdvdvdvdvdvdvdvdvdv18度度定理：在無(wú)向圖中，所有節(jié)點(diǎn)的度數(shù)之和等于邊定理：在無(wú)向圖中，所有節(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的數(shù)的2倍。倍。 證：因?yàn)槊織l邊給圖G帶來(lái)兩度，設(shè)

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

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

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

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

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

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

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

17、構(gòu)。35圖的同構(gòu)圖的同構(gòu)例：判斷下列兩圖是否同構(gòu)。例：判斷下列兩圖是否同構(gòu)。36 上面兩個(gè)圖不是同構(gòu)的，因?yàn)樽髨D中度結(jié)點(diǎn)都和兩個(gè)度結(jié)點(diǎn)相關(guān)聯(lián)，而右圖中的度結(jié)點(diǎn)和一個(gè)度結(jié)點(diǎn)相關(guān)聯(lián)還和一個(gè)度結(jié)點(diǎn)相關(guān)聯(lián)。37圖的同構(gòu)圖的同構(gòu)例：判斷下列兩圖是否同構(gòu)。例：判斷下列兩圖是否同構(gòu)。38 上面兩個(gè)圖是同構(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是個(gè)雙射函數(shù),并且保持了邊的鄰接關(guān)系39圖的同構(gòu)圖的同構(gòu) 判定兩個(gè)圖是否同構(gòu)，已知的最

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

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

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

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

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

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

24、點(diǎn)均在V中的邊的全體為邊集中的邊的全體為邊集合的合的G的子圖，稱(chēng)為由的子圖，稱(chēng)為由V導(dǎo)出的導(dǎo)出的G的子圖，記為的子圖，記為GV。若。若 ，導(dǎo)出子圖，導(dǎo)出子圖 ，記為，記為 。 ,GV E VVV VVG VVG V 是從G中去掉V中的結(jié)點(diǎn)以及與這些結(jié)點(diǎn)關(guān)聯(lián)的邊而得到的圖G的子圖。 G V定義：設(shè)圖定義：設(shè)圖 ， 且且 ， 。以。以 為結(jié)點(diǎn)集合，以為結(jié)點(diǎn)集合，以 為邊集合的為邊集合的G的子圖稱(chēng)為由的子圖稱(chēng)為由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é)點(diǎn)，G的導(dǎo)出子圖 是G的以 為結(jié)點(diǎn)集合的最大子圖。 G VV例：例：(b)是(a)的子圖、真子圖和生成子圖，(c)是(a)的由1,2,3,4導(dǎo)出的子圖。 子圖5051圖的運(yùn)算圖的運(yùn)算定義：設(shè)圖定義：設(shè)圖 和和 同為無(wú)向圖同為無(wú)向圖或同為有向圖?；蛲瑸橛邢驁D。 , ,GV E,GV E(1)如果對(duì)于任意 具有 ，則稱(chēng)G 和 是可運(yùn)算的。(2)如果 ，則稱(chēng)G和 是不相交的。(3)如果 ，則稱(chēng)G和 是邊不相交的。 eEE( )( )eeGVVEE GEE G52圖的運(yùn)算圖的運(yùn)算設(shè)圖 和 為可運(yùn)算的。 1111,GV E 2222,GV E (1)稱(chēng)以 為結(jié)點(diǎn)集合，以 為邊集合的G1和G2的

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

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

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

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

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

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

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

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

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

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

36、徑的長(zhǎng)度小于或等于階圖中的基本路徑的長(zhǎng)度小于或等于n-1。 證：在任何基本路徑中，出現(xiàn)于序列中的各結(jié)點(diǎn)都證：在任何基本路徑中，出現(xiàn)于序列中的各結(jié)點(diǎn)都是互不相同的。在長(zhǎng)度為是互不相同的。在長(zhǎng)度為l的任何基本路徑中，不的任何基本路徑中，不同的結(jié)點(diǎn)數(shù)目是同的結(jié)點(diǎn)數(shù)目是l+1。因?yàn)榧?。因?yàn)榧蟅僅有僅有n個(gè)不同的結(jié)個(gè)不同的結(jié)點(diǎn)，所以任何基本路徑的長(zhǎng)度不會(huì)大于點(diǎn)，所以任何基本路徑的長(zhǎng)度不會(huì)大于n-1。對(duì)于。對(duì)于長(zhǎng)度為長(zhǎng)度為l的基本循環(huán)來(lái)說(shuō)，序列中有的基本循環(huán)來(lái)說(shuō)，序列中有l(wèi)個(gè)不同的結(jié)點(diǎn)。個(gè)不同的結(jié)點(diǎn)。因?yàn)槭且驗(yàn)槭莕階圖，所以任何基本循環(huán)的長(zhǎng)度，都不會(huì)階圖，所以任何基本循環(huán)的長(zhǎng)度，都不會(huì)超過(guò)超過(guò)n，綜上

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

59、有向圖 ，其中，其中|V|=n，并且假定并且假定G中的各結(jié)點(diǎn)是有序的。試定義一個(gè)中的各結(jié)點(diǎn)是有序的。試定義一個(gè)nn的路徑矩陣的路徑矩陣P，使得其元素為，使得其元素為 ,GV E 1 0 ijijijvvPvv如果從 到 至少存在一條路徑如果從 到 不存在任何路徑 路經(jīng)矩陣P僅表明了圖中的任何結(jié)點(diǎn)偶對(duì)之間是否至少存在一條路徑，以及在任何結(jié)點(diǎn)上存在循環(huán)與否；它并不能指明存在的所有路徑。 114可達(dá)性矩陣可達(dá)性矩陣?yán)涸嚇?gòu)成下列有向圖的路徑矩陣?yán)涸嚇?gòu)成下列有向圖的路徑矩陣P。 解：設(shè)鄰接矩陣解：設(shè)鄰接矩陣A=A1。在前面的。在前面的例中，已經(jīng)求出過(guò)矩陣的冪例中，已經(jīng)求出過(guò)矩陣的冪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可達(dá)性矩陣可達(dá)性矩陣注意：注意：對(duì)于具有對(duì)于具有n個(gè)結(jié)點(diǎn)的圖而言，長(zhǎng)度為個(gè)結(jié)點(diǎn)的圖而言，長(zhǎng)度為n的路徑不可能的路徑不可能是基本路徑。是基本路徑。 假定圖中的每一個(gè)結(jié)點(diǎn)，從它本身出發(fā)總是可達(dá)的，假定圖中的每一個(gè)結(jié)點(diǎn)，從它本身出發(fā)總是可達(dá)的，由矩陣由矩陣Bn-1構(gòu)成路徑矩陣構(gòu)成路徑矩陣P，或由矩陣，或由矩陣Bn構(gòu)成路徑構(gòu)成路徑矩陣矩陣P，這兩種方法都可以采納。，這兩種方法都可