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

1、離散數(shù)學(xué)大連理工大學(xué)軟件學(xué)院陳志奎第9章圖的基本概念及其矩陣表示論2/128圖論（GraphTheory）是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干定的點(diǎn)連接兩點(diǎn)的線所構(gòu)成的圖形，這特形通用來描述某些事物之間的某種關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖論起源斯堡的島與河名的柯尼斯堡七橋問題。格爾河上有七座橋?qū)⒑又薪Y(jié)起來，如下圖所示，A、在的B、C，表示陸地。3/128圖論的起源 哥尼斯堡七橋問題：17世紀(jì)的東普魯士有一座哥尼斯堡（Konigsberg）城，城中有一條普雷格爾（Pregel）河，全城共有七座橋?qū)⒑又械膷u及島與河岸聯(lián)結(jié)起來，如下圖所示，a,

2、b,c,d表示陸。從四塊陸地的任何一塊出發(fā)，怎樣通過且僅通過每座橋一次，最終回到出發(fā)地點(diǎn)？4/128圖論的起源1736年瑞士大數(shù)學(xué)家列昂哈德歐拉（Leonhard Euler）解決了這一問題，他用了科學(xué)研究中最一般的方法抽象。字母a,b,c,d表示四塊陸地，并用7用條7座橋，從而將七橋問題抽象為，尋找經(jīng)過圖中每邊一次且僅一圖的次的回路，后來人們把為歐拉圖。這樣回路的圖稱cadb5/128圖論的起源歐拉證明了這個(gè)問題沒有解，并且推廣了這個(gè)問題，給出了對(duì)于一個(gè)給定的圖可以某種方式的判定法。這項(xiàng)工作使歐拉成為圖論始人。歐拉被稱為圖論之父，1736年也被稱為“圖論元年”。圖論部分共分為三章：圖的基本概

3、念及其矩陣表示，幾種圖的介紹，樹。本章將首論圖論中的一些基本概念，繼之闡述圖基本性質(zhì)，而后介紹圖的矩陣表示方法。6/128主要內(nèi)容 圖的基本概念 子圖和圖的運(yùn)算基礎(chǔ)知識(shí) 路徑 圖的 歐拉圖路、連通性表示 哈密爾頓圖 二部圖、平面圖 網(wǎng)絡(luò) 樹特殊圖7/1289.1圖的基本概念 圖是由一些頂點(diǎn)和連接這些頂點(diǎn)的一些邊所組成的離散結(jié)構(gòu)。 根據(jù)連接頂點(diǎn)對(duì)的邊的種類和數(shù)目的不同，圖有多種類型。幾乎每一門可以想到的學(xué)科，都有用圖模型來解決的問題。8/128圖的種類(1) 如果y : E ® v1, v2 v1 ÎV Ù v2ÎV，則稱G = áV , E,y

4、 ñ為無向圖。(2) 如果y : E ® V ´V，則稱 G = áV , E,y ñ為有向圖。圖還是有向圖，都統(tǒng)稱為圖，其中V無論是素稱為圖G的結(jié)點(diǎn)，E的元素稱為圖G的邊，圖G 點(diǎn)數(shù)目稱為圖的階。可以用幾何圖形表示上面定義的圖。用小圓圈的的向圖中，若y (e) = v1 , v2 ，就用連接表示結(jié)點(diǎn)。結(jié)點(diǎn)v1和v2的無向線段表示邊e。在有向圖中，若y (e) = áv1 , v2 ñ，就用v1指向v2的有向線段表示邊e。9/128圖的基本概念定義： 設(shè)無向圖G = áV , E,y ñ，e, e1 ,

5、e2Î E ，v1, v2ÎV(1)如果y (e) = v1 , v2，則稱e與v1(或v2)互相關(guān)聯(lián)。e連接v1和v2，v1和v2既是e的起點(diǎn)，也是e的終點(diǎn)，也稱v1和v2為點(diǎn)鄰接。(2)如果兩條不同的邊e1和e2與同一個(gè)結(jié)點(diǎn)關(guān)聯(lián)，則稱e1和e2為邊鄰接。也就是說，共邊的點(diǎn)稱為點(diǎn)鄰接；共點(diǎn)的邊稱為邊鄰接。10/128圖的基本概念定義：設(shè)有向圖G = áV , E,y ñ, e Î E, v1, v2 ÎV。如果y (e) = áv1 , v2 ñ ，則稱e連接v1和v2，e與v1(或v2)互相關(guān)聯(lián)，分別稱v1和v

6、2是e的起點(diǎn)和終點(diǎn)，也稱v1和v2鄰接。例：無向圖e1連接v1和v2，v1和v2鄰接，e1和e2鄰接。11/128圖的基本概念例：有向圖v2和v1分別是e1的起點(diǎn)和終點(diǎn)，v2與v1鄰接。12/128圖的基本概念定義： 設(shè)圖G = áV , E,y ñ ,e1和e2是G的兩條不同的邊。(1) 如果與e1關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)相同，則稱e1為自圈(或稱環(huán)和回路)。(2) 如果y (e1 ) =y (e2 ) ，則稱e1與e2平行。(3)如果圖G沒有自單圖。也沒有平行邊，則稱G為簡(jiǎn)4)如邊圖圖G沒有自回路，有平行邊，則稱G為多重(5)如果圖G既有自回路，又有平行邊，則稱G為偽圖。13/1

7、28圖的種類例：中國(guó)主要城市通訊圖14/128圖的種類15/128類型邊允許平行邊允許自環(huán)圖無向否否多重圖無向是否偽圖無向是是有向圖有向否是有向多重圖有向是是圖的同構(gòu)從圖的定義可以看出，圖的最本質(zhì)的內(nèi)容是結(jié)點(diǎn)和邊的關(guān)聯(lián)關(guān)系。兩個(gè)表面上看起來不同的圖，可能表達(dá)相同的結(jié)點(diǎn)和邊的關(guān)聯(lián)關(guān)系。16/128圖的同構(gòu)實(shí)際中，利用圖的同構(gòu)可以研究是否有可能用同樣的方式畫兩個(gè)圖。例如化學(xué)里，表示過去已知化合物的圖可以用來判定想象中的新化合物是否已經(jīng)研究過了。17/128圖的同構(gòu)定義：設(shè)圖G = áV , E,y ñ 和G ' = áV ', E ',y &#

8、39;ñ 。如果存在雙射f :V ®V ' 和雙射g : E ® E ', 使得對(duì)于任意的e Î E，v1, v2 ÎV都滿足(e) = 若y (e)= v1 ,v2若y (e)= v1 ,v2并稱f和g為G和G'之y則稱G 間的同f (v1 ), f (v2 )f (v1 ), f (v2 )同構(gòu)，記作 G G ，' 射，簡(jiǎn)稱同構(gòu)18/128圖的同構(gòu)換一種更簡(jiǎn)單的方法來描述：設(shè)圖G = áV , E,y ñ 和圖G ' = áV ', E ',y '

9、ñ，若存在從到的雙射函數(shù)f，對(duì)于V中所有的結(jié)點(diǎn)a和b來說，在G中有a到b的邊當(dāng)且僅當(dāng)在G與G同構(gòu)。中有f(a)和f(b)的邊，就說也就，兩個(gè)同構(gòu)的圖有同樣多的結(jié)點(diǎn)和邊，并且映射f保持結(jié)點(diǎn)間的鄰接關(guān)系，映射g保持邊之的鄰接關(guān)系。圖同構(gòu)的直觀含義，是其中一個(gè)圖經(jīng)與另一個(gè)圖完過旋轉(zhuǎn)、平移、拉伸等全重合。19/128圖的同構(gòu)例：求證下圖和同構(gòu)。證明：兩個(gè)圖點(diǎn)、邊的數(shù)目都相同。設(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)=

10、v2, f(u4)=v2與f(u3)=v3,f(u3)=v3與f(u1)=v1在H中相鄰。因此，二圖同構(gòu)。20/128圖的同構(gòu)兩個(gè)圖同構(gòu)必須滿足的必要條件是：(1) 頂點(diǎn)個(gè)數(shù)相同(2) 邊數(shù)相同(3) 度數(shù)相同的頂點(diǎn)個(gè)數(shù)相同(4)K度頂點(diǎn)的導(dǎo)出子圖同構(gòu)判定圖的同構(gòu)比較難，但是卻可以通過上述四點(diǎn)證明圖不同構(gòu)。21/128圖的同構(gòu)例：判斷下列兩圖是否同構(gòu)。22/128圖的同構(gòu)例：判斷下列兩圖是否同構(gòu)。23/128 上面兩個(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)。24/128圖的同構(gòu)例：判斷下列兩圖是否同構(gòu)。a2a1 b2b1e2f

11、2e1f1c2c1d2d125/128 上面兩個(gè)圖是同構(gòu)的。我們只要構(gòu)造雙射函數(shù) f:b1,c1,d1,e1,f11)=f2 ,f(b1)a2,b2,c2,d2,e2,f2,f(c1)=c2,f(f1)=e2 并且f)=d2 ,f(e1)=a2 f是個(gè)關(guān)系射函數(shù),并且保持了邊的鄰接26/128圖的同構(gòu)判定兩個(gè)圖是否同構(gòu)，已知的最好算法具有指數(shù)的最壞情形時(shí)間復(fù)雜度（對(duì)圖的結(jié)點(diǎn)來說）。不過，解決這個(gè)問題的線性平均情形時(shí)間復(fù)雜度的算法已經(jīng)找到，而且有希望找到判定兩個(gè)圖是否同構(gòu)的多項(xiàng)式最壞情形時(shí)間復(fù)雜度算法。一個(gè)名叫NAUTY的最佳算法，目前可以在個(gè)人電腦上秒之內(nèi)判定帶有100個(gè)結(jié)點(diǎn)的兩個(gè)圖是否同構(gòu)。

12、27/128圖模型 圖可以用在各種模型里，用于不同的行業(yè)。棲息地重疊圖：頂點(diǎn)表示物種，若兩個(gè)物種競(jìng)爭(zhēng)（他們共享某些食物來源），則用無向邊連接表示他們的頂點(diǎn)。貓頭鷹浣熊鷹松鼠烏鴉負(fù)鼠啄木鳥老鼠28/128圖模型熟人圖：可以用模型表示人與人之間的各種關(guān)系。頂條無向表示人，當(dāng)兩個(gè)人互相認(rèn)識(shí)時(shí)，用一連接這兩個(gè)人。據(jù)估計(jì)，世界上所有人的熟人圖有超過60億條邊。個(gè)頂點(diǎn)和可能超過1萬萊塢圖：好萊塢圖用頂點(diǎn)表示演員，當(dāng)兩個(gè)頂點(diǎn)的演員共同出演一部電影時(shí)，就用一條無向邊連接這兩個(gè)頂點(diǎn)。根據(jù)無聯(lián)網(wǎng)電影數(shù)據(jù)庫(kù)， 在2001年11月，好萊塢圖有574724個(gè)頂點(diǎn)和超過1600萬條邊，這些頂點(diǎn)所表示的演員出現(xiàn)在29260

13、9部影中。29/12830/128圖模型循環(huán)賽圖：每個(gè)隊(duì)其其他所有隊(duì)各有一次的比賽稱為循環(huán)賽。其中每個(gè)頂點(diǎn)表示每個(gè)隊(duì)，若a隊(duì)擊敗b 隊(duì)，則有一條從a指向b的有向邊。31/128圖模型合作圖：合作圖可以用來為學(xué)術(shù)論文的合作者關(guān)系建立模型。頂點(diǎn)表示某個(gè)文章的某個(gè)作者（人），如果兩個(gè)人合作論文，則用無向邊連接這兩個(gè)人。已經(jīng)發(fā)現(xiàn)在數(shù)學(xué)研究論文上合作的合作有超過337000個(gè)頂點(diǎn)和496000條邊。網(wǎng)示網(wǎng)圖：互聯(lián)網(wǎng)可以用有向圖來建模，用頂點(diǎn)表若有從網(wǎng)頁a指向網(wǎng)頁b的鏈接，則做一條從a向b的有向邊。網(wǎng)絡(luò)圖幾乎是連續(xù)變化的，幾乎每秒都有新頁面產(chǎn)生而又有其他頁面被刪除。目前網(wǎng)絡(luò)圖有超過10億個(gè)頂點(diǎn)和幾百億條邊

14、。許多研究者正解網(wǎng)絡(luò)的特研究網(wǎng)。的性質(zhì)，以便更好的理32/128圖模型優(yōu)先圖與并發(fā)處理：通過并發(fā)的執(zhí)行某些語句，計(jì)算機(jī)程序可能執(zhí)行的更快。但重要的是，要避免語句執(zhí)行時(shí)還要用到尚未執(zhí)行語句的結(jié)果。語句與前面語句的相關(guān)性可以表示成有向圖。用頂點(diǎn)表示某個(gè)語句，若在a語句執(zhí)行完之前不能執(zhí)行b語句，則引出一個(gè)從a到b的有向邊，這樣的圖稱為優(yōu)先圖。33/128圖模型S6S5S1：a:=0S2:S3:S4:S5:S6:b:=0c:=a+1 d:=b+a e:=d+1f:=c+dS3S4S2S134/128度定義：G =< V , E > 。(1) 如果G是無向圖，G中與v關(guān)聯(lián)的邊和與v關(guān)聯(lián)的自回

15、路的數(shù)目之和稱為v的度(或次)，記為dG (v)。(1) 如果G是有向圖，中以v為起點(diǎn)的邊的數(shù)目v) ；G中以v為終點(diǎn)的稱為v的邊的數(shù)目，記為為v的入記為 d - (v)；v的出度G與入度之和稱為v的度，記為dG (v) 。注意，在計(jì)算無向圖中結(jié)點(diǎn)的度時(shí)，自回路要考慮兩遍，因?yàn)樽曰芈芬彩沁叀?5/128度例：計(jì)算下圖中各結(jié)點(diǎn)的度。v3dG (v1 ) = 4 , dG (v2 ) = dG (v3 ) = 2v1v2d + (v ) = d + (v ) = d - (v ) = 2D1D2D3d - (v ) = 0,d - (v ) = 3D1D4d - (v ) = d + (v ) =

16、 d + (v ) = 1D2D3D4dD (v1 ) = 2dD (v2 ) = dD (v3 ) = 3dD (v4 ) = 436/128度定理：在無向圖中，所有節(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。證：因?yàn)槊織l邊給圖G帶來兩度，設(shè)圖G有m條邊，所以圖G共有2m度，等于圖G的所有結(jié)點(diǎn)的度數(shù)之和。定理：在向圖中，所有頂有頂點(diǎn)的入度的度數(shù)之和等于和等于所有節(jié)點(diǎn)的邊的出度倍；和，都等于邊數(shù)。37/128度 例：結(jié)點(diǎn)的度。38/128結(jié)點(diǎn)定義：度數(shù)為奇數(shù)的結(jié)點(diǎn)稱為奇結(jié)點(diǎn)，度數(shù)為偶數(shù)的結(jié)點(diǎn)稱為偶結(jié)點(diǎn)。定理：任何圖都有偶數(shù)個(gè)奇結(jié)點(diǎn)。V1 = v v為奇點(diǎn)= v v為偶點(diǎn)V2å d (v) + &#

17、229; d (v) = å d (v) = 2må d (v)vÎV2vÎV1å d (v)vÎV1vÎV2vÎVV定義： 度為0的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)，度為1的結(jié)點(diǎn)稱為端點(diǎn)。39/128一些特殊的簡(jiǎn)單圖零圖：結(jié)點(diǎn)都是孤立結(jié)點(diǎn)的圖稱為零圖。平凡圖：零圖稱為平凡圖。圈圖（Cn(n3)）：是由n個(gè)頂點(diǎn)v1,v2,vn以及邊v1,v2,v2,v3,vn-1,vn,vn,v1組成的。40/128一些特殊的簡(jiǎn)單圖輪圖：對(duì)來說，當(dāng)給圈圖Cn添加一個(gè)頂點(diǎn)， 并且把這個(gè)新頂點(diǎn)與Cn里的n個(gè)頂點(diǎn)逐個(gè)連接， 可以得到輪圖Wn。41/12

18、8一些特殊的簡(jiǎn)單圖正則圖： 所有結(jié)點(diǎn)的度均為自然數(shù)d的無向圖稱為d度正則圖。42/128一些特殊的簡(jiǎn)單圖完全無向圖：設(shè)n Î I+ ，如果n階簡(jiǎn)單無向圖G是n-1度正則圖，則稱G為完全無向圖，記為Kn。注意：完全無向圖的任意兩個(gè)不同結(jié)點(diǎn)都鄰接。一至五階完全無向圖43/128一些特殊的簡(jiǎn)單圖完全有向圖：設(shè)n Î I+ ，每個(gè)結(jié)點(diǎn)的出度和入度均為n-1的n階簡(jiǎn)單有向圖稱為完全有向圖。注意：完全有向圖的任意兩個(gè)不同結(jié)點(diǎn)之間都有一對(duì)方向相反的有向邊相連接。一至三階完全有向圖44/128一些特殊的簡(jiǎn)單圖45/128特殊類型的圖的一些應(yīng)用局域網(wǎng)：在一座大樓里，像小型計(jì)算機(jī)和個(gè)人電腦這樣

19、的計(jì)算機(jī)，以及像打印機(jī)這樣的外設(shè)，可以用局域網(wǎng)來連接。有三種常見的局域網(wǎng)拓?fù)浣Y(jié)構(gòu)。局域網(wǎng)的星形、環(huán)形及混合型拓?fù)?6/1289.2子圖和圖的運(yùn)算定義：設(shè)G = áV , E,y ñ和G¢ = áV ¢, E¢,y ¢ñ為圖。(1)如果V ¢ Í V , E¢ Í E,y ¢ Í y ，則稱G是G的子圖， 記作 G¢ Í G ，并稱G是G的母圖。(2)如果V ¢ Í V , E¢ Ì E,y

20、62; Ì y記作 G¢ Ì G 。，則稱G是G的真子圖，(3)如果V ¢ = V , E¢ Í E,y ¢ Í y ，則稱G'是G的生成子圖。G = áV , E,y ñ，G本身以平凡生成子圖：對(duì)于圖及零圖 G = áV , Æñ都是G的平凡生成子圖。47/128子圖定義： 設(shè)圖G = áV , E,y ñ ，V ¢ Í V 且 V ¢ ¹ F。以V為結(jié)點(diǎn)集合，以起點(diǎn)和終點(diǎn)均在V中的邊的全體為邊集

21、合的G的子圖，稱由V導(dǎo)出的G的子圖，記為GV。若V ¢ Ì V ，導(dǎo)出子圖GV - V ¢，記為 G -V ¢。G -V ¢ 是從G中去掉V'中的結(jié)點(diǎn)以及與這些結(jié)點(diǎn)關(guān)聯(lián)的邊而得到的圖G的子圖。定義：設(shè)圖G = áV , E,y ñ ，E¢ Í E 且 E，V ¢ = v | v ÎV Ù ($e)(e Î E¢ Ù v與e關(guān)聯(lián)) 。以V ¢為結(jié)點(diǎn)集合，以 E 為邊集合的G的子圖稱為由E'導(dǎo)出的子圖。48/128子圖從圖示

22、看，圖G的子圖是圖G的一部分，G的真子圖的邊數(shù)比G的邊數(shù)少，G的生成子圖與G有相同的結(jié)點(diǎn)，G的導(dǎo)出子圖GV ¢ 是G的以 V ¢為結(jié)點(diǎn)集合的最大子圖。例：ddccceefffhhaaabg(b)是(a)的子圖、真子圖和生成子圖，(c)是(a)的由1,2,3,4導(dǎo)出的子圖。49/128子圖50/128圖的運(yùn)算定義：設(shè)圖G = áV , E,y ñ 和G¢ = áV ¢, E¢,y ¢ñ 同為無向圖或同為有向圖。E¢具有y (e) = y ¢(e) ，則稱(1)如果對(duì)于任意 e

23、Î EG 和 G¢是可運(yùn)算的。(2)如果V IV ¢ = E I E¢ = F ，則稱G和G¢是不相交的。(3)如果 E I E¢ = F ，則稱G和 G¢ 是邊不相交的。51/128圖的運(yùn)算= áV1 , E1 ,y1 ñ和 G2 = áV2 , E2 ,y 2 ñ為可運(yùn)算的。設(shè)圖G1(1)稱以 V1邊集合的G1V2 為結(jié)點(diǎn)集合，以 E1E為2和G2的公共子圖為G1和G2的交，記為G1 I G2 。(2) 稱以 E1 U E2為邊集合，以與這些邊關(guān)聯(lián)的結(jié)點(diǎn)集合為點(diǎn)集的G1和G2的公共

24、母圖為G1和G2的并， 記為G1 U G2 。(3) 稱以V1 UV2為結(jié)點(diǎn)集合，以 E1 Å E2為邊集合的的子圖為G1和G2的環(huán)和，記為G1 Å G2。G1 U G252/128圖的運(yùn)算53/128圖的運(yùn)算e3v1v1v2e1e1v3ee24v2v3v4不是任何兩個(gè)圖都有交、并和環(huán)和。如上，(a)和(b)沒有交和并，因?yàn)檫卐1在(a)中連接v1和v2，而在(b)中連接v2和v3。54/128圖的運(yùn)算= áV2 , E2 ,y 2 ñ 為可運(yùn)算的。= áV1 , E1 ,y1 ñ和G2定理： 設(shè)圖G1¹ F(1)如果V1

25、IV2，則存在唯一的 G1 I G2 。(2)存在唯一的G1 U G 和G1 Å G2 。證：設(shè)G1和G2同為同樣證明。(1)定義y : E1 I E2 ® (V1 IV2 ) ´ (V1 IV2 )圖，若同為無向圖也可為：對(duì)任意的e Î E1 I E2，y (e) =y1(e) =y 2 (e)。顯然，á(V1 IV2 ), (E1 I E2 ),y ñ = G1 I G2.設(shè)圖G = áV1 IV2 , E1 I E2 ,y ñ和G¢ = áV1 IV2E,y ¢ñ 均為

26、G1和G2的交。因,y (e) =y1 (e).因?yàn)镚¢ Í G1為G Í G1 ，對(duì)任意 Î EI，。這表明y =y ¢。因?qū)θ我鈋 Î E1 I E2 ,y ¢(e) =y1 (e)此，G = G¢。55/128圖的運(yùn)算證： （2）定義y = E1 U E2® (V1 UV2 ) ´ (V1 UV2 )如下：e Î E1y (e) = ìy1 (e)íye Î E - E(e)î221然，áV1 UV2 , E1 U E2 ,y &

27、#241; = G1 UG2 。設(shè)G = áV1 UV2 , E1 U E2 ,y ñÍ G和G¢ = áV1 UV2 , E1 U E2 ,y ¢ñ均為G1和G2的并。因?yàn)?G1Í G¢ ，所以對(duì)任意eÎ E1 ，y (e) =y1(e) =y ¢(e)且G，1這表明 y =y ¢ ，因此G = G¢ 。對(duì)于存在唯一的G1 Å G2可同樣證明。56/128圖的運(yùn)算定義： 設(shè)圖G = áV , E,y ñ, E¢ Í

28、 E,記 áV , E - E¢,y /(E - E¢)ñ為G - E¢，對(duì)任意 e Î E ，記G -e為G - e。G - E¢是從G中去掉E'中的邊所得到的G的子圖。= áV , E,y ñ 和G¢ = áV ¢, E¢,y ¢ñ同為無向圖，并且邊不相交，記G + G¢為G + Ey¢ ¢。定義：設(shè)圖或同為有向G + Ey¢ ¢是由G增加E'中的邊所得到的圖，其中y 

29、2;指出E'中的邊與結(jié)點(diǎn)的關(guān)聯(lián)關(guān)系。57/128圖的運(yùn)算58/128圖的運(yùn)算上面的例子中，(a)和(b)分別為G1和G2 ,則圖c,d,e分別是 (G1 G2)-v5,v6,(G1 G2)-g,h, G2 +Ey其中g(shù)y=<g,v1,v3>59/1289.3路徑、回路和連通性60/128路徑和回路例：分析下列無向圖v1a v2 fv5在該無向圖中，v bv dv ev bv 是路23423徑，但不是簡(jiǎn)單路徑；cv3v2bv3cv3dv4是簡(jiǎn)單路徑，但不是基本路徑；v3cv3cv3 是閉路徑，但不是簡(jiǎn)單閉路徑。bedv4h從路徑 v1gv3cv3中去掉另外，如閉路徑v3cv3

30、到基本路徑 v1 gv3。61/128路徑和回路例：分析下列有向圖ahebk fcd在該有向圖中，1c4b1c4是，但不是簡(jiǎn)單路徑；1a1c4 是簡(jiǎn)單路徑，不是基本路徑。從 1a1c4中去掉閉路徑1a1就得到基本路徑1a4?？梢钥闯?，從2至1存在多條有路徑。62/128路但從1至2沒路徑和回路注意： 單獨(dú)一個(gè)結(jié)因此，任何 在無向圖中，也是路徑，它是長(zhǎng)度為0的基本路徑。其自身總存在路徑。結(jié)點(diǎn)v至結(jié)點(diǎn)v'存在路徑，則從v'至v必存在路徑。而在有向圖中，從結(jié)點(diǎn)v至v'結(jié)點(diǎn)存在路徑，而從v'至v卻不一定存在路徑。= v×× vn-1envn和P1 =

31、 vne '1 v '1××× v 'm-1 e 'me1v1 ××× vn-1envne '1 v '1××× v 'm-1 e 'm v 'm設(shè)路徑P1v 'm，用P1P2記路63/128路徑和回路例：“擺渡問題”：一個(gè)人帶有一條狼、一頭羊和一捆白菜，要從河的左岸渡到右岸去，河上僅有一條小船，而且只有人能劃船，船上每次只能由人帶一件東西過河。另外，不能讓狼和羊、羊和菜單獨(dú)留下。問怎樣安排擺渡過程？64/128路徑和回路解：

32、河左岸允許出現(xiàn)的情況有以下1羊菜、人羊、狼菜、狼、菜、羊及空情況：人狼羊菜、人狼羊、人狼菜、人物品已安全渡河），我們把這10種狀態(tài)視為10個(gè)點(diǎn)，若一種狀態(tài)通過一次擺渡后變?yōu)榱硪环N狀態(tài)，則在兩種狀態(tài)（點(diǎn)）之間畫一直線，得到上圖。這樣擺渡問題就圖中找出以“人羊菜”為起點(diǎn)，以“空”為終點(diǎn)的簡(jiǎn)，即：?jiǎn)温?。容易看出，只有兩條簡(jiǎn)單路符合要（1） 人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空；（2） 人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。對(duì)于簡(jiǎn)單路（1）的安排為：人帶羊過河；人回來；帶狼過河；放下狼再將羊帶回； 人再帶菜過河；人回來；帶羊過河。對(duì)于簡(jiǎn)單路（2）的安排為：人帶羊過河；人回來；帶

33、菜過河；放下菜再將羊帶回； 人再帶狼過河；人回來；帶羊過河。次、回3次，且不會(huì)再有述的兩種方案都是少次數(shù)的渡河辦法了。65/128路徑和回路定理： 設(shè)v和v'是圖G中的結(jié)點(diǎn)。如果存在從v至v'的路徑，則存在從v證：設(shè)當(dāng)從v至v的基本路徑。在長(zhǎng)度小于l 的路徑時(shí)，從v至v'必存在基本路徑。如果存在路徑v0e1v1 ××× vl -1e= v¢，并且= v, vl其中v0= v j ，則v0e1v1 ××× viej +1v j +1 ××× vl -1elvl路徑。根據(jù)歸納

34、假設(shè)，存j £ l 且vi有i和j滿足0 £ i £是從v至v'的長(zhǎng)度為l-j 在從v至v'的基本路徑66/128路徑和回路定理：n階圖中的基本路徑的長(zhǎng)度小于或等于n-1。證：在任何基本路徑中，出現(xiàn)于序列中的各結(jié)點(diǎn)都是互不相同的。在長(zhǎng)度為l的任何基本路徑中，不 同的結(jié)點(diǎn)數(shù)目是l+1。因?yàn)榧蟅僅有n個(gè)不同的結(jié) 點(diǎn)，所以任何基本路徑的長(zhǎng)度不會(huì)大于n-1。對(duì)于 長(zhǎng)度為l的基本循環(huán)來說，序列中有l(wèi)個(gè)不同的結(jié)點(diǎn)。因?yàn)槭莕階圖，所以任何基本循環(huán)的長(zhǎng)度，都不會(huì) 超過n，綜上所述，在n階圖中，基本路徑的長(zhǎng)度不會(huì)超過n-1。67/128路徑和回路路徑可以表示很多圖

35、模型中的有用信息：熟人關(guān)系圖通路（最小世界原理）合作圖中的通路（數(shù)學(xué)埃德斯數(shù)）好萊塢圖中的通路（演員的培根數(shù)（著名演員凱文.培根）68/128路徑和回路定理：設(shè)v是圖G的任意結(jié)點(diǎn)，G是回路或有向回路， 當(dāng)且僅當(dāng)G的階與邊數(shù)相等，并且在G中存在這樣一條從v到v的閉路徑，使得除了v在該閉路徑中出現(xiàn) 兩次外，其余結(jié)點(diǎn)和每條邊都在該閉路徑上恰出現(xiàn)一次。證：見書上。69/128路徑和回路70/128路徑和回路71/128路徑和回路例：判斷圖(a)有沒有有向回路。72/128連通性定義：設(shè)v1和v2是圖G的結(jié)點(diǎn)。如果在G中存在從v1至v2的路徑，則稱在G中從v1可達(dá)v2或v1和v2 是連通的，否則稱在G中

36、從v1不可達(dá)v2。對(duì)于圖G的結(jié)點(diǎn)，用R(v)表示從v可達(dá)的全體結(jié)點(diǎn)的集合。圖中，若從v1可達(dá)v2，則從v2必可向圖中，從v1可達(dá)v2不能保證從v2 論無向圖還是有向圖，任何節(jié)點(diǎn)是可達(dá)的。注意：在達(dá)v1；而必可到自73/128連通性74/128連通性75/128連通性76/128連通圖77/128連通圖無向圖 G = áV , E,y ñ是連通的，當(dāng)且僅當(dāng)對(duì)于任意v ÎV ，R(v) = V。78/128連通圖由于可達(dá)性的非對(duì)稱性，有向圖的連通概念要復(fù)雜得多，這里需要用到基礎(chǔ)圖的概念。79/128連通圖定義：設(shè)G是有向圖。(1) 如果G中任意兩個(gè)結(jié)點(diǎn)都互相可達(dá)，則稱

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

38、2）G的極向連通子圖稱為G的單向分支。（3）G的極大弱連同子圖稱為G的弱分支。81/128子圖和分支定理：連通無向圖恰有一個(gè)分支。非連通無向圖有一個(gè)以上分支。定理：強(qiáng)連（單向連通，弱連通）有向圖?。▎蜗蚍种?，弱分支）；非強(qiáng)連有一個(gè)強(qiáng)通（非單向連通上強(qiáng)分支（單向分弱連通）有向圖有一個(gè)以，弱分支）。82/128子圖和分支e4例：v3vv46e3e2e5e6e1vvv215有4個(gè)強(qiáng)分支，即áv1, v2 , v3,e1, e2 , e3,áe1, áv1, v2 ññ,áe2 , áv2 , v3 ññ, &#

39、225;e3 , áv3 , v1ñññ, áv4, Æ, Æñ, áv5, Æ, Æñ, áv6, Æ, Æñ結(jié)點(diǎn)恰處于一個(gè)強(qiáng)分支中，而邊e4 , e5 , e6 不每何強(qiáng)分支中。G有兩個(gè)單向分支，即Gv6在和Gv5 , v6。顯然，v5處于兩個(gè)單向分支中，G只有一個(gè)弱分支，即其本身。83/128子圖和分支 注意： 無向圖的每個(gè)結(jié)點(diǎn)和每條邊都恰在一個(gè)連通分支中；有向圖中，并不是每個(gè)邊都恰在一個(gè)強(qiáng)分支中 在簡(jiǎn)單有向中，每個(gè)結(jié)點(diǎn)每條邊都恰

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

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

42、2，rn是系統(tǒng)在時(shí)刻t的資源集合。資源分配圖Gt = <Rt，E>是有向圖，它表示了時(shí)間t系統(tǒng)中資源分配狀態(tài)。把每個(gè)資源ri看作圖中一個(gè)結(jié)點(diǎn)，其中i=1，2，n。<ri，rj>表示有向邊，<ri，rj>E當(dāng)且僅當(dāng)程序pkPt已分配到資源ri且等源rj。89/128分析（續(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=<Rt，E>如圖16.2

43、.7所示。能夠證明，在時(shí)刻t計(jì)算機(jī)系統(tǒng)處于死鎖狀態(tài)iff 資源分配圖Gt中包含強(qiáng)連通圖。90/128前例資源分配圖91/128割集有時(shí)刪除一個(gè)結(jié)點(diǎn)和它所關(guān)聯(lián)的邊，就產(chǎn)生帶有比原圖更多的連通分支的子圖。把這樣的結(jié)點(diǎn)稱為割點(diǎn)。有時(shí)刪除一條邊，就產(chǎn)生分支的子圖，把這樣的邊有比原圖更多的連通做割邊或者橋。92/1289.4圖的矩陣表示鄰接矩陣定義： 設(shè) G = áV, E,y ñ 是一個(gè)簡(jiǎn)單有向圖，其中的結(jié)點(diǎn)集合V =v1,v2 ,×××vn ，并且假定各結(jié)點(diǎn)已經(jīng)有了從結(jié)點(diǎn)v1到vn的次序。試定義一個(gè)n×n的矩陣A，使得其中的元素當(dāng)á

44、; vi ,v j ñÎ E當(dāng)á vi ,v j ñÏ E1= a(1)i j0則稱這樣的矩陣A是圖G的鄰接矩陣。93/128鄰接矩陣定義：元素或?yàn)?或?yàn)?的任何矩陣，都稱為比特矩 陣或布爾矩陣。i行上值為1的元素的個(gè)列上值為1的元素的個(gè)數(shù)，鄰接矩陣也是布爾矩陣，數(shù)，等于結(jié)點(diǎn)vi的出度； 等于結(jié)點(diǎn)vj的入度。94/128鄰接矩陣圖的鄰接矩陣不具有唯一性。G = áV , E,y ñ來說，其鄰接矩陣對(duì)于給定簡(jiǎn)單有向圖依賴于集合V中的各元素間的次序關(guān)系。兩個(gè)和相對(duì)應(yīng)的鄰接矩陣，如果首鄰接矩陣中交換一些行，而后交在一個(gè)圖換相對(duì)應(yīng)的

45、各列，從能夠求得另外一個(gè)圖一個(gè)圖的鄰接矩陣，鄰接矩陣，則事實(shí)上這互為同構(gòu)的。樣的兩個(gè)向圖，必95/128鄰接矩陣?yán)簩懗鱿聢D的鄰接矩陣，并計(jì)算各個(gè)節(jié)點(diǎn)的出度和入度。解：首先給各結(jié)點(diǎn)安排好一個(gè)次序，譬如說是v1 , v2 , v3 , v4 , v5。得出鄰接矩陣如下：év1v210101v301000v400101v5 ùê 00 úvêê 0ú0 ú1A = v2ê 01 úvêú3ê 10 úv4êúv5 êë

46、10 úû96/128鄰接矩陣上例中，如果重新把各結(jié)點(diǎn)排列成 v5 , v2 , v3 , v4 , v1，就能寫出另外一個(gè)矩陣如下：év5v1 ùv210101v301000v410100ê 01 úvêê 0ú0 ú5A¢ = v2ê 10 úvêú3ê 01 úv4v1êúêë 00 úû97/128鄰接矩陣 對(duì)于給定圖G，顯然不會(huì)因結(jié)點(diǎn)編序不同而使其結(jié)構(gòu)會(huì)發(fā)生

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

48、表示的概念，推廣到簡(jiǎn)單無向圖、多重邊圖和加權(quán)圖。對(duì)于簡(jiǎn)單無向圖來說，這種推廣會(huì)給出一個(gè)對(duì)稱或加權(quán)圖的情況下，可鄰接矩陣，在多重邊圖= wijaij其中的wij，或者是邊ávi , v j ñ的的權(quán)。另外，若ávi , v j ñÏ E ，數(shù)，或者是邊ávi , v j ñ= 0wij。在零圖的鄰接矩陣中，所有元素都應(yīng)該是0，亦即其鄰接矩陣是個(gè)零矩陣。100/128鄰接矩陣逆圖的鄰接矩陣：如果給定的圖G = áV , E,ñ是一個(gè)簡(jiǎn)單有向圖，并且其鄰接矩陣是A，則圖G的逆圖的鄰接矩陣 G 是A的轉(zhuǎn)置 AT

49、。對(duì)于無向圖或者對(duì)稱的有向圖來說，應(yīng)= A 。有AT101/128B = AAT在圖上的意義。設(shè)aij是鄰接矩陣中的第i行和第j定義矩陣 B = AAT列上的(i, j) 元素，bij 是矩陣中的第i行和第j列上的元素(i,j)。于是，對(duì)于i, j = 1, 2, 3,×××, nbij= å aik a j k k -1來說，有n= 1 ，如果邊áv j , vk ñ Î E ，如果邊ávi , vk ñ Î E，則有aik則有ajk = 1 。對(duì)于某一個(gè)確定的k來說，如果ávi ,

50、 vk ñ 和ávj , vk ñ 都是給定圖的邊，則在表示bij 的上述求和表達(dá)式中，應(yīng)該引入基值1。從結(jié)點(diǎn)vi和vj二者引出的邊，如果能共同終止于一些結(jié)點(diǎn)的話，那么這樣的一些結(jié)點(diǎn)的數(shù)目，就是元素bij的值。102/128B = AAT例：如圖，求 AAT在圖上的意義解：év1v5 ùév1v5 ùv210101v301000v400101v200100v301011v410000ê 00 úê 01 úvvêê 0ú0 úê

51、4; 1ú1 ú11A = v2= v2ATê 01 úê 00 úvvêúêú33ê 10 úê 01 úv4v5v4êúêúêë 10 úûv5 êë 00 úûé11ù010001030200011ê00úê= ê1ú2úAATê01ú

52、;êêë1ú3úû簡(jiǎn)單算法：原矩陣A中，第i行和第j行相交，有幾個(gè)1，AAT的第i行第j列就是幾。矩陣的主對(duì)角線的元素對(duì)應(yīng)了各個(gè)節(jié)點(diǎn)的出度。103/128C = AT A在圖上的意義設(shè)aij是鄰接矩陣A中的(i,j)元素； cij 是矩陣C中的元素。于是，對(duì)于i = 1, 2,×××, n,Cij= å aki akjnk =1對(duì)于某一個(gè)確定的k來說，如果ávk , vi ñ, ávk , v j ñ都是給定圖的邊，則在上式中應(yīng)引入基值1?？傻脧膱D中的一些

53、點(diǎn)所引出的邊，如果能夠同時(shí)終止于結(jié)點(diǎn)vi和vj的話，那么這樣的一些結(jié)點(diǎn)的數(shù)目，就是元素Cij的值。104/128C = AT A例：如圖，求 AT A解：在圖上的意義év1v210101v301000v400101v5 ùév1v200100v301011v410000v5 ùê 00 úê 01 úvvêê 0ú0 úêê 1ú1 ú11A = v2= v2ê 01 úATê 00 úvv

54、34;úêú33ê 10 úê 01 úv4vêú4êúv5 êë 10 ûúêë 00 úûv5簡(jiǎn)單算法：原矩陣A中，第i列和第j 列相交，有幾個(gè)1，ATA 的第i行第j列就是幾。é20ù130210010012021ê11úêA = ê0ú0úATê11úêêë0ú

55、1úû矩陣的主對(duì)角線的元素對(duì)應(yīng)了各個(gè)節(jié)點(diǎn)的入度。105/128鄰接矩陣的冪對(duì)于n = 2, 3, 4,××× 來說，考察鄰接矩陣A的冪An可知， 鄰接矩陣A中的第i行和第j列上的元素值1，說明了圖G中存在一條邊<vi,vj>，也就是說，存在一條從結(jié)點(diǎn)vi到vj長(zhǎng)度為1的路徑。定義矩陣A2，使得A2中的各2 為元素 aijn= å a2aaijikkjk =12元素值 a等于從v 到v 長(zhǎng)度為2的不同路徑的ijij2數(shù)目。顯然，矩陣中主對(duì)角線上的元素 a的ii值，表示了結(jié)點(diǎn)vi (i = 1, 2,××&

56、#215;, n) 上長(zhǎng)度為2的循環(huán)的個(gè)數(shù)。矩陣A3中的元素值(i,j)依次類推。106/128鄰接矩陣的冪例：é00ùé01ù011111010101100113020111111101ê01úê20úê= ê2ú0úê= ê1ú1úA2A3,ê00úê00úêêë1ú0úûêêë0ú1úûé20ùé11ù133121130211212336151331212413ê11úê21ú