離散數(shù)學(xué)圖的矩陣表示

離散數(shù)學(xué)圖的矩陣表示1第一頁，共二十五頁，2022年，8月28日無向圖的關(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).2第二頁，共二十五頁，2022年，8月28日

例:求下圖G的關(guān)聯(lián)矩陣上圖G的關(guān)聯(lián)矩陣:3第三頁，共二十五頁，2022年，8月28日無向圖的關(guān)聯(lián)矩陣

性質(zhì)：（5）當(dāng)且僅當(dāng)vi為孤立點(diǎn)。4第四頁，共二十五頁，2022年，8月28日有向圖的關(guān)聯(lián)矩陣定義設(shè)無環(huán)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

則稱(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).5第五頁，共二十五頁，2022年，8月28日例:求圖G的關(guān)聯(lián)矩陣。

上圖G的關(guān)聯(lián)矩陣:6第六頁，共二十五頁，2022年，8月28日有向圖的關(guān)聯(lián)矩陣(續(xù))性質(zhì)

(4)平行邊對應(yīng)的列相同7第七頁，共二十五頁，2022年，8月28日定義設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱()mn為D的鄰接矩陣,記作A(D),簡記為A.有向圖的鄰接矩陣

8第八頁，共二十五頁，2022年，8月28日求下圖G的鄰接矩陣。解上圖G的鄰接矩陣。

給出了圖G的鄰接矩陣，就等于給出了圖G的全部信息。圖的性質(zhì)可以由矩陣

A通過運(yùn)算而獲得。9第九頁，共二十五頁，2022年，8月28日定義設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱()mn為D的鄰接矩陣,記作A(D),簡記為A.性質(zhì)有向圖的鄰接矩陣

10第十頁，共二十五頁，2022年，8月28日

D中的通路及回路數(shù)定理設(shè)A為n階有向圖D的鄰接矩陣,則Al(l1)中元素為D中vi到vj長度為l的通路數(shù)，為vi到自身長度為l的回路數(shù)，為D中長度為l的通路總數(shù)，為D中長度為l的回路總數(shù).11第十一頁，共二十五頁，2022年，8月28日D中的通路及回路數(shù)(續(xù))例有向圖D如圖所示,求A,A2,A3,A4,

并回答諸問題：(1)D中長度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)D中長度小于或等于4的通路為多少條？其中有多少條回路？推論設(shè)Bl=A+A2+…+Al(l1),則Bl中元素為D中長度小于或等于l的通路數(shù)，為D中長度小于或等于l的回路數(shù).12第十二頁，共二十五頁，2022年，8月28日例(續(xù))

長度通路回路

合計(jì)50818121133141417313第十三頁，共二十五頁，2022年，8月28日在下圖中v1到v3長度為1、2、3、4的通路分別有多少條，G中共有長度為4的通路多少條，其中回路多少條，長度小于等于4的通路共有多少條，其中回路多少條。14第十四頁，共二十五頁，2022年，8月28日解:因?yàn)?/p>

15第十五頁，共二十五頁，2022年，8月28日

所以，由v1到v3長度為1、2、3、4的通路分別有0、2、2、4條，G中共有長度為4的通路43條，其中回路11條，長度小于等于4的通路共有87條，其中回路22條。注無向圖也有相應(yīng)的鄰接矩陣，一般只考慮簡單圖，無向圖的鄰接矩陣是對稱的，其性質(zhì)基本與有向圖鄰接矩陣的性質(zhì)相同。16第十六頁，共二十五頁，2022年，8月28日

例如:下圖鄰接矩陣為：

17第十七頁，共二十五頁，2022年，8月28日有向圖的可達(dá)矩陣

稱(pij)nn為D的可達(dá)矩陣,記作P(D),簡記為P.性質(zhì):

P(D)主對角線上的元素全為1.D強(qiáng)連通當(dāng)且僅當(dāng)P(D)的元素全為1.定義設(shè)D=<V,E>為有向圖,V={v1,v2,…,vn},令18第十八頁，共二十五頁，2022年，8月28日有向圖的可達(dá)矩陣(續(xù))例右圖所示的有向圖D的可達(dá)矩陣為19第十九頁，共二十五頁，2022年，8月28日

設(shè)G=V,E是n階簡單有向圖，V={v1,v2,…,vn}，由可達(dá)性矩陣的定義知，當(dāng)i≠j時(shí)，如果vi到vj有路，則pij=1；如果vi到vj無通路，則pij=0；又如果vi到vj有通路，則必存在長度小于等于n–1的通路。又n階圖中，任何回路的長度不大于n

，如下計(jì)算圖G的可達(dá)性矩陣P：

B=E+A+A2+…+An-1

=(bij)

n×n

其中

E是單位矩陣。則20第二十頁，共二十五頁，2022年，8月28日

圖9.24鄰接矩陣A和A2，A3，A4如下：

21第二十一頁，共二十五頁，2022年，8月28日

22第二十二頁，共二十五頁，2022年，8月28日則圖G的可達(dá)性矩陣

B=A0＋A＋A2＋A3＋A4=

P=23第二十三頁，共二十五頁，2022年，8月28日可達(dá)性矩陣用來描述有向圖的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路，即是否可達(dá)。無向圖也可以用矩陣描述一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路。在無向圖中，如果結(jié)點(diǎn)之間有路，稱這兩個(gè)結(jié)點(diǎn)連通，不叫可達(dá)。所以把描述一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路的矩陣叫連通矩陣，而不叫可達(dá)性矩陣。

24第二十四頁，共二十五頁，2022年，8月28日

定義設(shè)G=V,E是簡單無向圖，V={v1,v2,…,vn}P(G)=(pij)

n×n