1、7.3 圖的矩陣表示圖的矩陣表示 無向圖的關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣有向圖的鄰接矩陣有向圖的鄰接矩陣有向圖的可達(dá)矩陣有向圖的可達(dá)矩陣 無向圖的關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣定義定義 設(shè)無向圖設(shè)無向圖G=, V=v1, v2, , vn, E=e1, e2, , em, 令令mij為為vi與與ej的關(guān)聯(lián)次數(shù)，稱的關(guān)聯(lián)次數(shù)，稱(mij)nm為為G的關(guān)聯(lián)矩陣，記為的關(guān)聯(lián)矩陣，記為M(G). e1e2e3e4e51234 例:求下圖G的關(guān)聯(lián)矩陣l上圖上圖G的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣:12342100001110( )0011100001M G12345eeeee無向圖的關(guān)聯(lián)矩陣無向圖

2、的關(guān)聯(lián)矩陣平行邊的列相同平行邊的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij 性質(zhì)：（5） 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)vi為孤立點(diǎn)。為孤立點(diǎn)。mjijm1, 0有向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣 的終點(diǎn)的終點(diǎn)為為，不關(guān)聯(lián)不關(guān)聯(lián)與與，的始點(diǎn)的始點(diǎn)為為jijijiijevevevm10,1定義定義 設(shè)無環(huán)有向圖設(shè)無環(huán)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 則稱則稱(mij)nm為為D的關(guān)聯(lián)矩陣，記為的關(guān)聯(lián)矩陣，記為M(D).e5e6e3e2e1e453412n例例: 求圖求圖G的關(guān)

3、聯(lián)矩陣。的關(guān)聯(lián)矩陣。l 上圖G的關(guān)聯(lián)矩陣:12345100000111100( )011011000111000000M G123456e ee ee e有向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣( (續(xù)續(xù)) ) jiijmjiijmjiijniijmnivdmvdmmjm,1110)3(,.,2 , 1),()1(),()1()2(),.,2 , 1(0)1(性質(zhì)性質(zhì) (4) 平行邊對(duì)應(yīng)的列相同平行邊對(duì)應(yīng)的列相同定義定義 設(shè)有向圖設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 為頂點(diǎn)為頂點(diǎn)vi鄰接到頂點(diǎn)鄰接到頂點(diǎn)vj邊的條數(shù)，邊的條數(shù)，稱稱( )mn為為D的鄰接矩

4、陣的鄰接矩陣, 記作記作A(D), 簡(jiǎn)記為簡(jiǎn)記為A. )1(ija)1(ija有向圖的鄰接矩陣有向圖的鄰接矩陣 2341n求下圖求下圖G的鄰接矩陣。的鄰接矩陣。l解解 上圖上圖G的鄰接矩陣。的鄰接矩陣。12000010()10010010A G 給出了圖G的鄰接矩陣，就等于給出了圖G的全部信息。圖的性質(zhì)可以由矩陣 A通過運(yùn)算而獲得。 定義定義 設(shè)有向圖設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 為頂點(diǎn)為頂點(diǎn)vi鄰接到頂點(diǎn)鄰接到頂點(diǎn)vj邊的條數(shù)，邊的條數(shù)，稱稱( )mn為為D的鄰接矩陣的鄰接矩陣, 記作記作A(D), 簡(jiǎn)記為簡(jiǎn)記為A. 性質(zhì)性質(zhì)的回路數(shù)的

5、回路數(shù)中長(zhǎng)度為中長(zhǎng)度為的通路數(shù)的通路數(shù)中長(zhǎng)度為中長(zhǎng)度為1)4(1)3(,.,2 , 1),()2(,.,2 , 1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij )1(ija)1(ija有向圖的鄰接矩陣有向圖的鄰接矩陣 D中的通路及回路數(shù)中的通路及回路數(shù))(lija)(liia ninjlija11)( niliia1)(定理定理 設(shè)設(shè)A為為n階有向圖階有向圖D的鄰接矩陣的鄰接矩陣, 則則Al(l1)中中元素元素 為為D中中vi到到vj長(zhǎng)度為長(zhǎng)度為 l 的通路數(shù)，的通路數(shù)， 為為vi到自身長(zhǎng)度為到自身長(zhǎng)度為 l 的回路數(shù)，的回路數(shù)

6、， 為為D中長(zhǎng)度為中長(zhǎng)度為 l 的通路總數(shù)，的通路總數(shù)， 為為D中長(zhǎng)度為中長(zhǎng)度為 l 的回路總數(shù)的回路總數(shù). D中的通路及回路數(shù)中的通路及回路數(shù)(續(xù)續(xù))例例 有向圖有向圖D如圖所示如圖所示, 求求A, A2, A3, A4, 并回答諸問題：并回答諸問題：(1) D中長(zhǎng)度為中長(zhǎng)度為1, 2, 3, 4的通路各有多的通路各有多 少條？其中回路分別為多少條？少條？其中回路分別為多少條？(2) D中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于4的通路為多的通路為多 少條？其中有多少條回路？少條？其中有多少條回路？ ninjlijb11)( niliib1)(推論推論 設(shè)設(shè)Bl=A+A2+Al(l1), 則則Bl中元

7、素中元素 為為D中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于l 的通路數(shù)，的通路數(shù)， 為為D中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于l 的回路數(shù)的回路數(shù).例(續(xù)) 長(zhǎng)度長(zhǎng)度 通路通路 回路回路 1004010410050001010310030104000110020102100300010101100101020001432AAAA合計(jì)合計(jì) 50 818 1211 3314 1417 32341在下圖中在下圖中v1到到v3長(zhǎng)度為長(zhǎng)度為1、2、3、4的通路分別有的通路分別有多少條，多少條，G中共有長(zhǎng)度為中共有長(zhǎng)度為4的通路多少條，其中回的通路多少條，其中回路多少條，長(zhǎng)度小于等于路多少條，長(zhǎng)度小于等于4的通路共有多

8、少條，其的通路共有多少條，其中回路多少條。中回路多少條。l解解:由于由于 23412001200122000100010100110011001121000100010100132225642121022212221443212102221AAAl 所以，由v1到v3長(zhǎng)度為1、2、3、4的通路分別有0、2、2、4條，G中共有長(zhǎng)度為4的通路43條，其中回路11條，長(zhǎng)度小于等于4的通路共有87條，其中回路22條。l 注 無向圖也有相應(yīng)的鄰接矩陣，一般只考慮簡(jiǎn)單圖，無向圖的鄰接矩陣是對(duì)稱的，其性質(zhì)基本與有向圖鄰接矩陣的性質(zhì)相同。0111101011011010)(GA 例如:下圖鄰接矩陣為： 有向圖

9、的可達(dá)矩陣有向圖的可達(dá)矩陣 1,0,ijijvvp可達(dá)否則稱稱(pij)nn為為D的可達(dá)矩陣的可達(dá)矩陣, 記作記作P(D), 簡(jiǎn)記為簡(jiǎn)記為P. 性質(zhì)性質(zhì): P(D)主對(duì)角線上的元素全為主對(duì)角線上的元素全為1. D強(qiáng)連通當(dāng)且僅當(dāng)強(qiáng)連通當(dāng)且僅當(dāng)P(D)的元素全為的元素全為1.定義定義 設(shè)設(shè)D=為有向圖為有向圖, V=v1, v2, , vn, 令令有向圖的可達(dá)矩陣(續(xù))例例 右圖所示的有向圖右圖所示的有向圖D的可達(dá)矩陣為的可達(dá)矩陣為 1101110111110001P 設(shè)G=V,E是n階簡(jiǎn)單有向圖，V=v1,v2,vn，由可達(dá)性矩陣的定義知，當(dāng)ij時(shí)，如果vi到vj有路，則pij=1；如果vi到v

10、j無通路，則pij=0；又如果vi到vj有通路，則必存在長(zhǎng)度小于等于n1的通路。又n階圖中，任何回路的長(zhǎng)度不大于n ，如下計(jì)算圖G的可達(dá)性矩陣P： B=E+A+A2+A n-1 =(b ij ) nn 其中 E 是單位矩陣。那么1000ijijijbpb 圖9.24鄰接矩陣A和A2，A3，A4如下：0100010000000100010100010A 01000100000002000202000203A10000010000020200040002024A 10000010000010100020001012A則圖則圖G的可達(dá)性矩陣的可達(dá)性矩陣 B= A0AA2A3A4 = 31000130000043300373003341100011000001110011100111 P= 可達(dá)性矩陣用來描述有向圖的一個(gè)結(jié)點(diǎn)到另可達(dá)性矩陣用來描述有向圖的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路，即是否可達(dá)。無向圖也一個(gè)結(jié)點(diǎn)是否有路，即是否可達(dá)。無向圖也可以用矩陣描述一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否可以用矩陣描述一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路。在無向圖中，如果結(jié)點(diǎn)之間有路，稱有路。在無向圖中，如果結(jié)點(diǎn)之間有路，稱這兩個(gè)結(jié)點(diǎn)連通，不叫可達(dá)。所以把描述一這兩個(gè)結(jié)點(diǎn)連通，不叫可達(dá)。所以把描述一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路的矩陣叫連通個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是