離散數(shù)學(xué)圖論6.2

1、n 6.3.1 無(wú)向圖的關(guān)聯(lián)矩陣無(wú)向圖的關(guān)聯(lián)矩陣 n 6.3.2 有向無(wú)環(huán)圖的關(guān)聯(lián)矩陣有向無(wú)環(huán)圖的關(guān)聯(lián)矩陣 n 6.3.3 有向圖的鄰接矩陣有向圖的鄰接矩陣,無(wú)向圖的相鄰矩陣無(wú)向圖的相鄰矩陣 l 圖中的通路數(shù)與回路數(shù)圖中的通路數(shù)與回路數(shù) n 6.3.4 圖的可達(dá)矩陣圖的可達(dá)矩陣 1 設(shè)無(wú)向圖設(shè)無(wú)向圖G=, V=v1, v2, , vn, E=e1, e2, , em. 令令mij為為vi與與ej的關(guān)聯(lián)次數(shù)的關(guān)聯(lián)次數(shù), 稱稱(mij)n m為為G的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣, 記為記為 M(G). mij的可能取值為的可能取值為:0,1,2 2 例如例如 e1 e2 e3 e4 e5 e6 v5 v1

2、v2 v3 v4 M(G)= 2 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 列相同列相同列與第列與第第第是平行邊是平行邊與與kjee mm nivdm mjm kj ji ij i m j ij n i ij )4( 2)3( ,.,2 , 1),()2( ,.,2 , 1, 2)1( , 1 1 3 (6) ej是環(huán)是環(huán) 第第j列的一個(gè)元素為列的一個(gè)元素為2, 其余為其余為0 (5) vi是孤立點(diǎn)是孤立點(diǎn) 第第i行全為行全為0 4 則稱則稱(mij)n m為為D的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣, 記為記為M(D). 的終點(diǎn)的終點(diǎn)為

3、為， 不關(guān)聯(lián)不關(guān)聯(lián)與與， 的始點(diǎn)的始點(diǎn)為為 ji ji ji ij ev ev ev m 1 0 ,1 設(shè)無(wú)環(huán)有向圖設(shè)無(wú)環(huán)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em. 令令 性質(zhì)性質(zhì): (1) 每列恰好有一個(gè)每列恰好有一個(gè)1和一個(gè)和一個(gè)-1 (2) 1總個(gè)數(shù)等于總個(gè)數(shù)等于-1的總個(gè)數(shù)的總個(gè)數(shù), 等于邊數(shù)等于邊數(shù). (3) 第第i行行1的個(gè)數(shù)等于的個(gè)數(shù)等于d+(vi), 第第i行行-1的個(gè)數(shù)等于的個(gè)數(shù)等于d-(vi) (4) ej與與ek是平行邊是平行邊 第第j列與第列與第k列相同列相同 5 v1 v2 v3 v4 e2 e1 e3 e4e5 e6 e7 M(D)

4、= -1 1 0 0 0 1 1 0 -1 1 0 0 0 0 0 0 -1 -1 -1 1 -1 1 0 0 1 1 0 0 6 環(huán)的個(gè)數(shù)環(huán)的個(gè)數(shù)中中等于等于 性質(zhì)性質(zhì) Da ma njvda nivda n i ii ji ij j n i ij i n j ij 1 )1( , )1( 1 )1( 1 )1( )4( )3( ,.,2 , 1),()2( ,.,2 , 1),()1(: 設(shè)有向圖設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 為頂點(diǎn)為頂點(diǎn)vi鄰接到頂點(diǎn)鄰接到頂點(diǎn)vj邊的條數(shù)，稱邊的條數(shù)，稱( )n n為為D的鄰接矩陣的鄰接矩陣, 記作

5、記作A(D), 簡(jiǎn)記作簡(jiǎn)記作A. )1( ij a )1( ij a 7 A= 1 1 0 0 0 0 1 0 1 0 0 0 1 0 2 0 v1 v2 v3 v4 8 定理定理6.6 設(shè)設(shè)A為為n階有向圖階有向圖D的鄰接矩陣的鄰接矩陣, 則則Al(l 1)中元素中元素 等于等于D中中vi到到vj長(zhǎng)度為長(zhǎng)度為 l 的通路的通路(含回路含回路)數(shù)數(shù), 等于等于vi到自身長(zhǎng)到自身長(zhǎng) 度為度為l 的回路數(shù)的回路數(shù), 等于等于D中長(zhǎng)度為中長(zhǎng)度為 l 的通路的通路(含回路含回路) 總數(shù)總數(shù), 等于等于D中長(zhǎng)度為中長(zhǎng)度為 l 的回路總數(shù)的回路總數(shù). )(l ii a )(l ij a n i n j l

6、 ij a 11 )( n i l ii a 1 )( 9 推論推論 設(shè)設(shè)Bl=A+A2+Al(l 1), 則則Bl中元素中元素 等于等于D中中vi到到 vj長(zhǎng)度小于等于長(zhǎng)度小于等于 l 的通路的通路(含回路含回路)數(shù)數(shù), 等于等于D中中vi到到vi長(zhǎng)度長(zhǎng)度 小于等于小于等于 l 的回路數(shù)的回路數(shù), 等于等于D中長(zhǎng)度小于等于中長(zhǎng)度小于等于l 的的 通路通路(含回路含回路)數(shù)數(shù), 為為D中長(zhǎng)度小于等于中長(zhǎng)度小于等于l 的回路數(shù)的回路數(shù). n i n j l ij b 11 )( n i l ii b 1 )( )(l ij b )(l ii b 10 說(shuō)明說(shuō)明: 在這里在這里, 通路和回路數(shù)是定

7、義意義下的通路和回路數(shù)是定義意義下的 A= 1 1 0 0 0 0 1 0 1 0 0 0 1 0 2 0 A2= 1 1 1 0 1 0 0 0 1 1 0 0 3 1 0 0 A3= 2 1 1 0 1 1 0 0 1 1 0 0 3 3 1 0 A4= 3 2 1 0 1 1 0 0 2 1 1 0 4 3 1 0 v1到到v2長(zhǎng)為長(zhǎng)為3的通路有的通路有1條條 v1到到v3長(zhǎng)為長(zhǎng)為3的通路有的通路有1條條 v1到自身長(zhǎng)為到自身長(zhǎng)為3的回路有的回路有2條條 D中長(zhǎng)為中長(zhǎng)為3的通路共有的通路共有15條條,其中回路其中回路3條條 v1 v2 v3 v4 例例 寫出無(wú)向圖的相鄰矩陣寫出無(wú)向圖的相

8、鄰矩陣, 并求并求v1到到v2長(zhǎng)度為長(zhǎng)度為3的通路數(shù)和的通路數(shù)和v1到到v1長(zhǎng)度為長(zhǎng)度為 3的回路數(shù)的回路數(shù). 11 設(shè)無(wú)向簡(jiǎn)單圖設(shè)無(wú)向簡(jiǎn)單圖G=, V=v1, v2, , vn, 令令 為頂點(diǎn)為頂點(diǎn)vi與與vj 之間邊的條數(shù)，稱之間邊的條數(shù)，稱( )n n為為G的的相鄰矩陣相鄰矩陣, 記作記作A(G). )1( ij a )1( ij a v1v4 v2v3 0011 0010 1101 1010 A 2111 1101 1031 1112 2 A 2143 1031 4324 3142 3 A v1到到v2長(zhǎng)度為長(zhǎng)度為3的通路有的通路有3條條:v1v2v1v2, v1v2v3v2, v1v

9、4v1v2. v1到到v1長(zhǎng)度為長(zhǎng)度為3的回路有的回路有2條條: v1v2v4v1, v1v4v2v1. 性質(zhì)性質(zhì): (1) P(G)主對(duì)角線上的元素全為主對(duì)角線上的元素全為1. (2) 無(wú)向圖的可達(dá)矩陣是對(duì)稱的無(wú)向圖的可達(dá)矩陣是對(duì)稱的. (3) 無(wú)向圖無(wú)向圖G連通當(dāng)且僅當(dāng)連通當(dāng)且僅當(dāng)P(G)的元素全為的元素全為1. 有向圖有向圖D強(qiáng)連通當(dāng)且僅當(dāng)強(qiáng)連通當(dāng)且僅當(dāng)P(D)的元素全為的元素全為1. (4)對(duì)對(duì)n階圖階圖, pij=1 , i j 12 設(shè)圖設(shè)圖(無(wú)向圖和有向圖無(wú)向圖和有向圖)G=, V=v1, v2, , vn, 令令 稱稱(pij)n n為為G的可達(dá)矩陣的可達(dá)矩陣, 記作記作P(G

10、), 簡(jiǎn)記為簡(jiǎn)記為P. 否否則則 可可達(dá)達(dá) , 1 , 0 ji ij vv p 0 )1( n ij b 例例1 (1) v1到到v4,v4到到v1長(zhǎng)為長(zhǎng)為3的通路各有多少條的通路各有多少條? (2) v1到自身長(zhǎng)為到自身長(zhǎng)為1,2,3,4的回路各有多少條的回路各有多少條? (3) 長(zhǎng)為長(zhǎng)為4的通路共有多少條的通路共有多少條?其中有多少條回路其中有多少條回路? (4) 長(zhǎng)度小于等于長(zhǎng)度小于等于4的回路共有多少條的回路共有多少條? (5) 寫出寫出D的可達(dá)矩陣的可達(dá)矩陣, 并問(wèn)并問(wèn)D是強(qiáng)連通的嗎是強(qiáng)連通的嗎? 解解 13 v1 v2 v3 v4 A= 1 2 1 0 0 0 1 0 0 0 0 1 0 0 1 0 14 v1到到v4長(zhǎng)為長(zhǎng)為3的通路有的通路有 條條, A2= 1 2 3 1 0 0 0 1 0 0 1 0 0 0 0 1 A3= 1 2 4 3 0 0 1 0 0 0 0 1 0 0 1 0 A4= 1 2 6 4 0 0 0 1 0 0 1 0 0 0 0 1 3 v4到到v1長(zhǎng)為長(zhǎng)為3的通路有的