離散數學圖的矩陣表示演示文稿1第1頁，共23頁。2（優(yōu)選）離散數學圖的矩陣表示第2頁，共23頁。

例:求下圖G的關聯矩陣上圖G的關聯矩陣:第3頁，共23頁。無向圖的關聯矩陣

性質：（5）當且僅當vi為孤立點。第4頁，共23頁。有向圖的關聯矩陣定義設無環(huán)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

則稱(mij)n

m為D的關聯矩陣，記為M(D).第5頁，共23頁。例:求圖G的關聯矩陣。

上圖G的關聯矩陣:第6頁，共23頁。有向圖的關聯矩陣(續(xù))性質

(4)平行邊對應的列相同第7頁，共23頁。定義設有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點vi鄰接到頂點vj邊的條數，稱()m

n為D的鄰接矩陣,記作A(D),簡記為A.有向圖的鄰接矩陣

第8頁，共23頁。求下圖G的鄰接矩陣。解上圖G的鄰接矩陣。

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

A通過運算而獲得。第9頁，共23頁。定義設有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點vi鄰接到頂點vj邊的條數，稱()m

n為D的鄰接矩陣,記作A(D),簡記為A.性質有向圖的鄰接矩陣

第10頁，共23頁。

D中的通路及回路數定理設A為n階有向圖D的鄰接矩陣,則Al(l

1)中元素為D中vi到vj長度為l的通路數，為vi到自身長度為l的回路數，為D中長度為l的通路總數，為D中長度為l的回路總數.第11頁，共23頁。D中的通路及回路數(續(xù))例有向圖D如圖所示,求A,A2,A3,A4,

并回答諸問題：(1)D中長度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)D中長度小于或等于4的通路為多少條？其中有多少條回路？推論設Bl=A+A2+…+Al(l

1),則Bl中元素為D中長度小于或等于l的通路數，為D中長度小于或等于l的回路數.第12頁，共23頁。例(續(xù))

長度通路回路

合計508181211331414173第13頁，共23頁。在下圖中v1到v3長度為1、2、3、4的通路分別有多少條，G中共有長度為4的通路多少條，其中回路多少條，長度小于等于4的通路共有多少條，其中回路多少條。第14頁，共23頁。解:因為

第15頁，共23頁。

所以，由v1到v3長度為1、2、3、4的通路分別有0、2、2、4條，G中共有長度為4的通路43條，其中回路11條，長度小于等于4的通路共有87條，其中回路22條。注無向圖也有相應的鄰接矩陣，一般只考慮簡單圖，無向圖的鄰接矩陣是對稱的，其性質基本與有向圖鄰接矩陣的性質相同。第16頁，共23頁。

例如:下圖鄰接矩陣為：

第17頁，共23頁。有向圖的可達矩陣

稱(pij)n

n為D的可達矩陣,記作P(D),簡記為P.性質:

P(D)主對角線上的元素全為1.D強連通當且僅當P(D)的元素全為1.定義設D=<V,E>為有向圖,V={v1,v2,…,vn},令第18頁，共23頁。有向圖的可達矩陣(續(xù))例右圖所示的有向圖D的可達矩陣為第19頁，共23頁。

設G=

V,E

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

，如下計算圖G的可達性矩陣P：

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

=(bij)

n×n