1、離散數(shù)學(xué)大連理工大學(xué)學(xué)院7.4圖的矩陣表示一、鄰接矩陣定義： 設(shè)G V , E, 是一個(gè)簡(jiǎn)單有向圖，其中的結(jié)點(diǎn)集合V v1 , v2 ,vn ，并且假定各結(jié)點(diǎn)已經(jīng)有了從結(jié)點(diǎn)v1到vn的次序。試定義一個(gè)nn的矩陣A，使得其中的元素當(dāng) vi ,v j E當(dāng) vi ,v j E1 a(1)i j0則稱(chēng)這樣的矩陣A是圖G的鄰接矩陣。2/41鄰接矩陣定義：元素或?yàn)?或?yàn)?的任何矩陣，都稱(chēng)為比特矩陣或矩陣。鄰接矩陣也是矩陣，第i行上值為1的元素的個(gè)數(shù)，等于結(jié)點(diǎn)vi的出度；第j列上值為1的元素的個(gè)數(shù)，等于結(jié)點(diǎn)vj的入度。3/41鄰接矩陣圖的鄰接矩陣不具有唯一性。對(duì)于給定簡(jiǎn)單有向圖G V , E, 來(lái)說(shuō)，其鄰

2、接矩陣依賴(lài)于集合V中的各元素間的次序關(guān)系。給定兩個(gè)有向圖和相對(duì)應(yīng)的鄰接矩陣，如果首先在一個(gè)圖的鄰接矩陣換一些行，而后交換相對(duì)應(yīng)的各列，從而有一個(gè)圖的鄰接矩陣，能夠求得另外一個(gè)圖的鄰接矩陣，則事實(shí)上這樣的兩個(gè)有向圖，必定是互為同構(gòu)的。4/41鄰接矩陣?yán)簩?xiě)出下圖的鄰接矩陣，并計(jì)算各個(gè)節(jié)點(diǎn)的出度和入度。解：首先給各結(jié)點(diǎn)安排好一個(gè)次序，譬如說(shuō)是v1 , v2 , v3 , v4。得出鄰接矩陣如下：v1v2v1v 2v3v40v4v31v1v2vv1101105/41鄰接矩陣上例中，如果重新把各結(jié)點(diǎn)排列成v2 , v3 , v1 , v4 ，就能寫(xiě)出另外一個(gè)矩陣如下：vv12v2v 3vvv4v3v1

3、0v vv00110110A 10如果首先交換第一行和第三行，而后交換第一列與第三列，接著交換v2和v3所對(duì)應(yīng)的行，而后交換v2和v3所對(duì)應(yīng)的列，那么就能夠由鄰接矩陣A2求得鄰接矩陣A1。6/41鄰接矩陣對(duì)于給定圖G，顯然不會(huì)因結(jié)點(diǎn)編序不同而使其結(jié)構(gòu)會(huì)發(fā)生任何變化，即圖的結(jié)點(diǎn)所有不同編序?qū)嶋H上仍表示同一個(gè)圖。換句話說(shuō)，這些結(jié)點(diǎn)的不同編序的圖都是同構(gòu)的，并且它們的n！個(gè)鄰接矩陣都是相似的。今后將略去這種由于V中結(jié)點(diǎn)編序而引起鄰接矩陣的任意性。而取該圖的任一個(gè)鄰接矩陣作為該圖的矩陣表示。7/41鄰接矩陣由鄰接矩陣判斷有向圖的性質(zhì)：如果有向圖是自反的，則鄰接矩陣的主對(duì)角線上的各元素，必定都是1。如果

4、有向圖是反自反的，則鄰接矩陣的主對(duì)角線上的各元素，必定都是0。對(duì)于對(duì)稱(chēng)的有向圖來(lái)說(shuō)，其鄰接矩陣也是對(duì)稱(chēng)的，也就說(shuō)，對(duì)于所有的i和j而言，都應(yīng)有aij=aji。如果給定有向圖是稱(chēng)的，則對(duì)于所有的i和j和ij而言，aij=1 蘊(yùn)含aji=0。8/41鄰接矩陣可以把簡(jiǎn)單有向圖的矩陣表示的概念，推廣到簡(jiǎn)單無(wú)向圖、多重邊圖和圖。對(duì)于簡(jiǎn)單無(wú)向圖來(lái)說(shuō)，這種推廣會(huì)給出一個(gè)對(duì)稱(chēng)的鄰接矩陣，在多重邊圖或圖的情況下，可以令 wijaij其中的wij，或者是邊vi , v j 的重?cái)?shù)，或者是邊vi , v j 的權(quán)。另外，若vi , v j E ，則wij 0。在零圖的鄰接矩陣中，所有元素都應(yīng)該是0，亦即其鄰接矩陣是

5、個(gè)零矩陣。9/41鄰接矩陣逆圖的鄰接矩陣：如果給定的圖G V , E, 是一個(gè)簡(jiǎn)單有向圖，并且其鄰接矩陣是A，則圖G的逆圖的鄰接矩陣 G 是A的轉(zhuǎn)置AT 。對(duì)于無(wú)向圖或者對(duì)稱(chēng)的有向圖來(lái)說(shuō)，應(yīng)。AAT有10/41B AAT在圖上的意義。設(shè)aij是鄰接矩陣中的第i行和第j定義矩陣 B AAT列上的(i, j) 元素，bij 是矩陣中的第i行和第j列上的元素(i,j)。于是，對(duì)于i, j 1, 2, 3, n 來(lái)說(shuō)，有bij aik a j kk 1n 1 ，如果邊v j , vk E ，如果邊vi , vk E，則有aik則有ajk 1 。對(duì)于某一個(gè)確定的k來(lái)說(shuō)，如果vi , vk 和 vj ,

6、vk 都是給定圖的邊，則在表示bij的上述求和表達(dá)式中，應(yīng)該引入基值1。從結(jié)點(diǎn) vi和vj二者引出的邊，如果能共同終止于一些結(jié)點(diǎn)的話，那么這樣的一些結(jié)點(diǎn)的數(shù)目，就是元素bij的值。11/41B AAT例：如圖，求 AAT在圖上的意義00解：1011000101100011100011A 0 1AT11000010101001022vv012 2AAT113v4v3簡(jiǎn)單算法：原矩陣A中，第i行和第j行相交，有幾個(gè)1，AAT的第i行第j列就是幾。矩陣的主對(duì)角線的元素對(duì)應(yīng)了各個(gè)節(jié)點(diǎn)的出度。12/41C AT A在圖上的意義設(shè)aij是鄰接矩陣A中的(i,j)元素；cij 是矩陣C中的元素。于是，對(duì)于i

7、 1, 2, n,Cij akiakjnk 1對(duì)于某一個(gè)確定的k來(lái)說(shuō)，如果vk , vi , vk , v j 都是給定圖的邊，則在上式中應(yīng)引入基值1。可得從圖中的一些點(diǎn)所引出的邊，如果能夠同時(shí)終止于結(jié)點(diǎn)vi和vj的話，那么這樣的一些結(jié)點(diǎn)的數(shù)目，就是元素Cij的值。13/41C AT A 在圖上的意義例：如圖，求 AT A解：000011v1101100010001111011000v211A 0 1AT1100vv00432310簡(jiǎn)單算法：原矩陣A中，第i列和第j列相交，有幾個(gè)1，ATA的第i行第j列就是幾。220AT A 0101矩陣的主對(duì)角線的元素對(duì)應(yīng)了各個(gè)節(jié)點(diǎn)的入度。14/41鄰接矩陣

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

9、11211 14A 02A31311216/41鄰接矩陣的冪定理：設(shè)G V , E, 是一簡(jiǎn)單有向圖，并且A是G的鄰接矩陣。對(duì)于m 1, 2, 3, 來(lái)說(shuō)，矩陣Am中的元素 (i,j)的值，等于從vi到vj長(zhǎng)度為m的路徑數(shù)目。證：對(duì)于m進(jìn)行歸納證明。當(dāng)m=1時(shí)，由鄰接矩陣的定義中能夠得到Am=A。設(shè)矩陣Ak中的元素(i,j)值(k )aAk 1 Ak A，且對(duì)于m=k來(lái)說(shuō)結(jié)論為真。因?yàn)槭?，ij所以應(yīng)有n aipapj(k 1)( k )aijp1(k ) aapj是從結(jié)點(diǎn)vi出發(fā)，經(jīng)過(guò)結(jié)點(diǎn)vp到vj的長(zhǎng)度ip為k+1的各條路徑的數(shù)目。這里vk是倒數(shù)第二個(gè)(k 1)結(jié)點(diǎn)。因此，a應(yīng)是從結(jié)點(diǎn)v 出

10、發(fā)，經(jīng)過(guò)任意iji的倒數(shù)第二個(gè)結(jié)點(diǎn)到vj的長(zhǎng)度為k+1的路徑總數(shù)。因此，對(duì)于m=k+1，定理成立。17/41鄰接矩陣的冪根據(jù)上述定理，出結(jié)論：能使矩陣Am中的元素(i,j)值是非零的最小正整數(shù)m，就是距d離vi , v j 。對(duì)于m 1, 2, , n 1和i j來(lái)說(shuō)，如果矩陣Am中的(i,j)元素值和(j,i)元素值都為0，那么就不會(huì)有任何路徑連通結(jié)點(diǎn)vi和vj。因此，結(jié)點(diǎn)vi和vj必定是屬于圖G的不同分圖。18/41鄰接矩陣的冪例：給定一個(gè)簡(jiǎn)單有向圖G V , E, ，如下圖所示，其中的結(jié)點(diǎn)集合 V v1 , v2 , v3 , v4 , v5。試求出圖G的鄰接矩陣A和A的冪A2，A3,A

11、4。v10010100010000000110v5A 00v201v004v319/41鄰接矩陣的冪1v1解：002000101000001000v 105A2v200v40100010v3200400020200020200020000000100020 20 00A3A40100000120/41二、可達(dá)性矩陣給定一個(gè)簡(jiǎn)單有向圖G V , E, ，并且設(shè)結(jié)V ?？芍?，由圖G的鄰接矩陣A能夠直接確定點(diǎn)vi , v jr ，I由矩陣 ArG中是否存在一條從vi到vj的邊。設(shè)能夠求得從結(jié)點(diǎn)vi到vj長(zhǎng)度為r的路徑數(shù)目。試矩陣B A A2 Arr矩陣Br的(i,j)元素值表示了從結(jié)點(diǎn)vi到vj長(zhǎng)度

12、小于或等于r的路徑數(shù)目。當(dāng)圖中的結(jié)點(diǎn)數(shù)目為n時(shí)，矩陣Bn都能夠提供足夠的信息，以表明從圖中的任何結(jié)點(diǎn)到其它結(jié)點(diǎn)的可達(dá)性。21/41可達(dá)性矩陣定義： 給定一個(gè)簡(jiǎn)單有向圖G V , E, ，其中|V|=n，并且假定G中的各結(jié)點(diǎn)是有序的。試定義一個(gè)nn的路徑矩陣P，使得其元素為 1如果從vi到vj至少存在一條路徑P0ij如果從v 到v 不存在任何路徑ij矩陣P僅表明了圖中的任何結(jié)點(diǎn)偶對(duì)之間是否至少存在一條路徑，以及在任何結(jié)點(diǎn)上存在循環(huán)與否；它并不能指明存在的所有路徑。22/41可達(dá)性矩陣下列有向圖的路徑矩陣P。解：設(shè)鄰接矩陣A=A1。例：試面的例vv12中，已經(jīng)求出過(guò)矩陣的冪A2，A3和A4。求出矩

13、陣B4和路徑矩陣P如下：v4v3232111454912141111111141 2P 11B43611523/41可達(dá)性矩陣注意：對(duì)于具有n個(gè)結(jié)點(diǎn)的圖而言，長(zhǎng)度為n的路徑不可能是基本路徑。假定圖中的每一個(gè)結(jié)點(diǎn)，從它本身出發(fā)總是可達(dá)的，由矩陣Bn-1路徑矩陣P，或由矩陣Bn路徑矩陣P，這兩種方法都可以采納。24/41可達(dá)性矩陣矩陣A, A2 , An，而后由他們矩陣B ，首先n再由矩陣Bn路徑矩陣P，太麻煩了。為了減少計(jì)算工作量，應(yīng)該設(shè)法使得不產(chǎn)生這些不必要的信息。生成路徑矩陣的簡(jiǎn)單方法：和和矩陣法。積對(duì)：于兩個(gè)nn的矩陣A和B，A和B的和A ，B并分別稱(chēng)為矩A ,BA和B的是積是陣C和D，它

14、們也都是元素分別定義成矩陣。把矩陣C和D的n aij bij , dij (aik bkj )Cijk 125/41可達(dá)性矩陣鄰接矩陣A是個(gè)矩陣。路徑矩陣P也是個(gè)矩陣。對(duì)于r 2, 3,來(lái)說(shuō)，令A(yù) A A(2)A(r 1) A A(r)于是，可以把路徑矩陣P表示成n A(k )P A A(2) A(3) A(n)k 1注意：A(m)表示矩陣，如果從vi到vj有長(zhǎng)度為m的路徑的話，矩陣中(i,j)元素為1；Am中(i,j)元素表示從vi到vj的長(zhǎng)度為m的路徑的個(gè)數(shù)。26/41可達(dá)性矩陣?yán)簩?duì)于下述的有向圖來(lái)說(shuō)，試求出矩陣A(2),A(3),A(4)和P。011110010101001111101

15、1v101v2 1 0A(2)A(3)011111v4v3111111101011 11A( 4)11111111111111 A A(2)A A(2) A(3) A(3) A(4) P111127/41可達(dá)性矩陣可以用不同的方法解釋矩陣A, A(2) , A(3) , 。在簡(jiǎn)單有向圖G V , E, 中，應(yīng)有E V V，因此可以把集合E看成是V中的二元關(guān)系。鄰接矩陣A是關(guān)系E的關(guān)系關(guān)系E oE E 2 定義矩陣。在第四章中，曾經(jīng)把成這樣一種關(guān)系：如果存在一個(gè)結(jié)點(diǎn)vk，能使viEvk和vkEvj，則必有viE2vj。換句話說(shuō)，從vi到vj如果至 少存在一條長(zhǎng)度為2的路徑的話，那么E2的關(guān)系矩陣

16、中的(i,j)元素值是1。這就說(shuō)明了，矩陣A(2)是關(guān)系E2的關(guān)系矩陣。與此類(lèi)似，A(3)是V中的關(guān)系E oE oE E3的關(guān)系矩陣，類(lèi)推。設(shè)E1和E2是V中的兩種關(guān)系，并且A1和A2分別是E1和E2的關(guān)系矩陣。于是,關(guān)系E1 U E2和E1 oE2的關(guān)系矩陣分別是A1 A2和 A1 A2。28/41閉包對(duì)于集合V中的關(guān)系E來(lái)說(shuō)，E的可傳遞閉包E+應(yīng)是E E U E2 U E3 U可傳遞閉包E+的關(guān)系矩陣應(yīng)為：A A A(2) A(3) 式中的A是關(guān)系E的關(guān)系矩陣。如果|V|=n，則圖中的基本路徑或基本循環(huán)的長(zhǎng)度不會(huì)超過(guò)n。因此A A A(2) A(3) A(n) P可見(jiàn)，矩陣A+與路徑矩陣P

17、相同。計(jì)算關(guān)系的可傳遞閉包等同于計(jì)算對(duì)應(yīng)關(guān)系圖的路徑矩陣。29/41可達(dá)性矩陣判斷強(qiáng)分圖由路徑矩陣P可以求得含有給定圖的任何特定結(jié)點(diǎn)的強(qiáng)分圖。設(shè)G V , E, 是一個(gè)簡(jiǎn)單有向圖，并且G。P是圖G的路徑矩陣，PT是矩陣P的轉(zhuǎn)置。設(shè)矩陣P中的(i,j)元素為Pij，而矩陣PT中的(i,j)元素為PijT。試定義pTpP PT，使得它的(i,j)元素為一個(gè)矩陣。于是，ijij矩陣P PT 中的第i行，就確定了含有結(jié)點(diǎn)vi的強(qiáng)分圖。30/41可達(dá)性矩陣判斷強(qiáng)分圖v3e4v4e5v6e3e2e6e1vvv2151011100011100011110011111110111000111000000100

18、00001010101010P 00 P PT 0000010001 31/41可達(dá)性矩陣判斷遞歸過(guò)程利用簡(jiǎn)單有向圖的可達(dá)矩陣，能夠確定某過(guò)程是否為遞歸的。假設(shè)VPrg=p1，p2，pn是程序Prg中的過(guò)程集合，做有向圖G=，其中piVPrg， i=1，2，n；E iff pi調(diào)用pj。如果圖G中有包含pi的回路，則斷言pi是遞歸的。為此，由圖G的鄰接矩陣A=(aij)計(jì)算出關(guān)系矩陣 A+=(aij)。如果A+中的主對(duì)角線上的某元素a =1，則p 是遞歸的iji32/41可達(dá)性矩陣判斷遞歸過(guò)程例如，已知程序Prg中的過(guò)程集合 VPrg=p1，p2，p3，p4，p5，其過(guò)程的調(diào)用關(guān)系可表成下圖所示的有向圖，該圖的鄰接矩陣A為。0010001000000100000A=100100圖16.4.633/41可達(dá)性矩陣判斷遞歸過(guò)程于是可求得A+:0111111000001111101A =+100111由此可知，p2，p4和p5是遞歸的。34/41三、關(guān)聯(lián)矩陣給定無(wú)環(huán)的有向圖D=，V=v1，v2，vm，E=e1，e2，en，令1,vi為e j的始點(diǎn) b