離散結(jié)構(gòu)課件6章圖論基礎(chǔ)

16.3圖的矩陣表示6.3.1無向圖的關(guān)聯(lián)矩陣6.3.2有向無環(huán)圖的關(guān)聯(lián)矩陣6.3.3有向圖的鄰接矩陣有向圖中的通路數(shù)與回路數(shù)6.3.4有向圖的可達(dá)矩陣2無向圖的關(guān)聯(lián)矩陣設(shè)無向圖G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.

令mij為vi與ej的關(guān)聯(lián)次數(shù),稱(mij)nm為G的關(guān)聯(lián)矩陣,記為M(G).mij的可能取值為:0,1,2例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2110000101110000110000000011003關(guān)聯(lián)矩陣的性質(zhì)(6)ej是環(huán)第j列的一個(gè)元素為2,其余為0(5)vi是孤立點(diǎn)第i行全為04無環(huán)有向圖的關(guān)聯(lián)矩陣則稱(mij)nm為D的關(guān)聯(lián)矩陣,記為M(D).設(shè)無環(huán)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.令(3)ej與ek是平行邊

第j列與第k列相同(2)第i行1的個(gè)數(shù)等于d+(v),第i行1的個(gè)數(shù)等于d(v)性質(zhì):5實(shí)例v1v2v3v4e2e1e3e4e5e6e7M(D)=–

11000–110–11000000

–1

–1

–11–1100110

06有向圖的鄰接矩陣設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱()nn為D的鄰接矩陣,記作A(D),簡(jiǎn)記作A.7實(shí)例A=1100001010001020v1v2v3v48有向圖中的通路數(shù)與回路數(shù)定理6.6設(shè)A為n階有向圖D的鄰接矩陣,則Al(l1)中元素等于D中vi到vj長(zhǎng)度為l的通路(含回路)數(shù),等于vi到自身長(zhǎng)度為l的回路數(shù),等于D中長(zhǎng)度為l的通路(含回路)總數(shù),等于D中長(zhǎng)度為l的回路總數(shù).9有向圖中的通路數(shù)與回路數(shù)(續(xù))推論設(shè)Bl=A+A2+…+Al(l1),則Bl中元素等于D中vi到vj長(zhǎng)度小于等于l的通路(含回路)數(shù),等于D中vi到vi的長(zhǎng)度小于等于l的回路數(shù),等于D中長(zhǎng)度小于等于l的通路(含回路)數(shù),為D中長(zhǎng)度小于等于l的回路數(shù).10實(shí)例A=1100001010001020v1v2v3v411實(shí)例

說明:在這里,通路和回路數(shù)是定義意義下的A=1100001010001020A2=1110100011003100A3=2110110011003310A4=3210110021104310v1到v2長(zhǎng)為3的通路有1條v1到v3長(zhǎng)為3的通路有1條v1到自身長(zhǎng)為3的回路有2條D中長(zhǎng)為3的通路共有15條,其中回路3條v1v2v3v412有向圖的可達(dá)矩陣性質(zhì):P(D)主對(duì)角線上的元素pii全為1.D強(qiáng)連通當(dāng)且僅當(dāng)P(D)的元素全為1.設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},令

稱(pij)nn為D的可達(dá)矩陣,記作P(D),簡(jiǎn)記為P.13實(shí)例例6.11(1)v1到v4,v4到v1長(zhǎng)為3的通路各有多少條?(2)v1到自身長(zhǎng)為1,2,3,4的回路各有多少條?(3)長(zhǎng)為4的通路共有多少條?其中有多少條回路?(4)長(zhǎng)度小于等于4的回路共有多少條?(5)寫出D的可達(dá)矩陣,并問D是強(qiáng)連通的嗎?解v1v2v3v4A=121000100001001014實(shí)例(續(xù))v1到v4長(zhǎng)為3的通路有條,A2=1231000100100001A3=1243001000010010A4=12640001001000013v4到v1長(zhǎng)為3的通路有條0v1到自身長(zhǎng)為1,2,3,4的回路各有條1長(zhǎng)為4的通路共有條，其中有條回路163長(zhǎng)度小于等于4的回路共有條8可達(dá)矩陣非強(qiáng)連通,單連通P=1111011100110011A