圖的矩陣表示

1、114.4 圖的矩陣表示v無(wú)向圖的關(guān)聯(lián)矩陣無(wú)向圖的關(guān)聯(lián)矩陣v有向無(wú)環(huán)圖的關(guān)聯(lián)矩陣有向無(wú)環(huán)圖的關(guān)聯(lián)矩陣v有向圖的鄰接矩陣有向圖的鄰接矩陣v有向圖中的通路數(shù)與回路數(shù)有向圖中的通路數(shù)與回路數(shù)v有向圖的可達(dá)矩陣有向圖的可達(dá)矩陣2無(wú)向圖的關(guān)聯(lián)矩陣設(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例如例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2 1 1 0 0 00 1 0 1 1 10 0

2、0 0 1 10 0 0 0 0 00 0 1 1 0 0 3關(guān)聯(lián)矩陣的性質(zhì)列列相相同同列列與與第第第第是是平平行行邊邊與與kjeemmnivdmmjmkjjiijimjijniij)4(2)3(,.,2,1),()2(,.,2,1,2)1(,11(6) ej是環(huán)是環(huán) 第第j列的一個(gè)元素為列的一個(gè)元素為2, 其余為其余為0(5) vi是孤立點(diǎn)是孤立點(diǎn) 第第i行全為行全為04無(wú)環(huán)有向圖的關(guān)聯(lián)矩陣則稱則稱(mij)n m為為D的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣, 記為記為M(D). 的的終終點(diǎn)點(diǎn)為為，不不關(guān)關(guān)聯(lián)聯(lián)與與，的的始始點(diǎn)點(diǎn)為為jijijiijevevevm10,1設(shè)無(wú)環(huán)有向圖設(shè)無(wú)環(huán)有向圖D=, V=v1

3、, v2, , vn, E=e1, e2, , em. 令令mjmniij,.,2 , 1, 0)1(1(3) ej與與ek是平行邊是平行邊 第第j列與第列與第k列相同列相同(2) 第第i行行1的個(gè)數(shù)等于的個(gè)數(shù)等于d+(v), 第第i行行 1的個(gè)數(shù)等于的個(gè)數(shù)等于d (v)性質(zhì)性質(zhì):5實(shí)例v1v2v3v4e2e1e3e4e5e6e7M(D)= 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 06有向圖的鄰接矩陣環(huán)的個(gè)數(shù)環(huán)的個(gè)數(shù)中中等于等于性質(zhì)性質(zhì)Damanjvdanivdaniiijiijjniijinjij1)1(,)1(1)1(1)

4、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ù)，稱( )m n為為D的鄰接矩陣的鄰接矩陣, 記作記作A(D), 簡(jiǎn)記作簡(jiǎn)記作A.)1(ija)1(ija7實(shí)例A=1 1 0 00 0 1 01 0 0 01 0 2 0v1v2v3v48有向圖中的通路數(shù)與回路數(shù)定理定理14.11 設(shè)設(shè)A為為n階有向圖階有向圖D的鄰接矩陣的鄰接矩陣, 則則Al(l 1)中元素中元素 等于等于D中中vi到到vj長(zhǎng)度為長(zhǎng)度為 l 的通路的

5、通路(含回路含回路)數(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ù). )(liia)(lija ninjlija11)( niliia1)(9有向圖中的通路數(shù)與回路數(shù)(續(xù))推論推論 設(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

6、 的通路的通路(含回路含回路)數(shù)數(shù), 為為D中長(zhǎng)度小于等于中長(zhǎng)度小于等于l 的回路數(shù)的回路數(shù). ninjlijb11)( niliib1)()( lijb)( liib10實(shí)例(續(xù)) A=1 1 0 00 0 1 01 0 0 01 0 2 0A2=1 1 1 01 0 0 01 1 0 03 1 0 0A3=2 1 1 01 1 0 01 1 0 03 3 1 0A4=3 2 1 01 1 0 02 1 1 04 3 1 0v1到到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的通路共有的通路共

7、有15條條,其中回路其中回路3條條v1v2v3v411有向圖的可達(dá)矩陣性質(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, 令令 稱稱(pij)n n為為D的可達(dá)矩陣的可達(dá)矩陣, 記作記作P(D), 簡(jiǎn)記為簡(jiǎn)記為P. 否則否則可達(dá)可達(dá), 0, 1jiijvvp12實(shí)例例例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的通路共有多少條的通

8、路共有多少條?其中有多少條回路其中有多少條回路?(4) 長(zhǎng)度小于等于長(zhǎng)度小于等于4的回路共有多少條的回路共有多少條?(5) 寫出寫出D的可達(dá)矩陣的可達(dá)矩陣, 并問并問D是強(qiáng)連通的嗎是強(qiáng)連通的嗎?解解v1v2v3v4A=1 2 1 00 0 1 00 0 0 10 0 1 013實(shí)例(續(xù))v1到到v4長(zhǎng)為長(zhǎng)為3的通路有的通路有 條條,A2=1 2 3 10 0 0 10 0 1 00 0 0 1A3=1 2 4 30 0 1 00 0 0 10 0 1 0A4=1 2 6 40 0 0 10 0 1 00 0 0 13v4到到v1長(zhǎng)為長(zhǎng)為3的通路有的通路有 條條0v1到自身長(zhǎng)為到自身長(zhǎng)為1,2,3,4的回路各有