第7章+圖論-3(圖的矩陣表示)

1、1返回 結(jié)束第七章 圖論引言引言7.1 圖的基本概念圖的基本概念7.2 路與連通路與連通7.3 圖的矩陣表示2返回 結(jié)束7.3 圖的矩陣表示v圖的矩陣表示圖的矩陣表示 圖的數(shù)學(xué)抽象是三元組，其形象直觀的表圖的數(shù)學(xué)抽象是三元組，其形象直觀的表示即圖的圖形表示。為便于計(jì)算，特別為便示即圖的圖形表示。為便于計(jì)算，特別為便于用計(jì)算機(jī)處理圖，下面介紹圖的第三種表于用計(jì)算機(jī)處理圖，下面介紹圖的第三種表示方法示方法圖的矩陣表示。圖的矩陣表示。利用矩陣的運(yùn)算還可以了解到它的一些有關(guān)性質(zhì)。內(nèi)容：內(nèi)容：關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)矩陣。重點(diǎn)：重點(diǎn)：1、有向圖，無向圖的關(guān)聯(lián)矩陣，2、有向圖的鄰接矩陣。了解：了解：有向圖

2、的可達(dá)矩陣。3返回 結(jié)束7.3.1 圖的矩陣表示鄰接矩陣鄰接矩陣 存儲原則存儲原則: 存儲結(jié)點(diǎn)集和邊集的信息存儲結(jié)點(diǎn)集和邊集的信息.（1 1）存儲結(jié)點(diǎn)集；）存儲結(jié)點(diǎn)集；（2 2）存儲邊集：）存儲邊集： 存儲每兩個(gè)結(jié)點(diǎn)存儲每兩個(gè)結(jié)點(diǎn)是否有關(guān)系。是否有關(guān)系。4返回 結(jié)束7.3.1 鄰接矩陣1.無向圖的鄰接矩陣無向圖的鄰接矩陣ijaiv12,pVv vv定義 1.6.2設(shè) 的頂點(diǎn)集為 ，用 表示 中頂點(diǎn) 與 之間的邊數(shù)。稱矩陣 為 的鄰接矩陣。( , )GV EGjv( )()ijp pM GaG從圖的鄰接矩陣的定義容易得出以下性質(zhì)： 是一個(gè)對稱矩陣；若 為無環(huán)圖。則 中第 行(列)的元素之和等于頂

3、點(diǎn) 的度數(shù)；(3) 兩個(gè)圖 與 同構(gòu)的充要條件是存在一個(gè)置換矩陣 ，使得 。( )M G( )M G( )M GiivGHP( )()TM GP M H P對應(yīng)的鄰接矩陣12345123450101110211()020001101111010vvvvvvvMGvvv例2下圖所示 的鄰接矩陣為：GA(G)A(G)A(G)A(G)A(G)A(G)相當(dāng)于將單位矩陣中相應(yīng)的行與行，或者列與列互換的矩陣5返回 結(jié)束7.3.1 鄰接矩陣v同構(gòu)圖v判別定理：圖G1 ，G2同構(gòu)的充要條件充要條件是：存在置換矩陣P，使得：A1PA2P。v 其中A1，A2分別是G1 ，G2的鄰接矩陣。v如何判斷兩圖同構(gòu)是圖論中

4、一個(gè)困難問題v1v2v3v4圖G1vavbvcvd圖G20 1 1 11 0 1 11 1 0 11 1 1 0A11 2 3 40 1 1 11 0 1 11 1 0 11 1 1 0A2a b c dv1vav2vbv3vcv4vd6返回 結(jié)束7.3.1 鄰接矩陣v在鄰接矩陣A的冪A2， A3， 矩陣中， 每個(gè)元素有特定的含義。v定理 :設(shè)G是具有n個(gè)結(jié)點(diǎn)集v1， v2， ， vn 的圖， 其鄰接矩陣為A， 則Al（l1， 2， ）的（i， j）項(xiàng)元素a(l)ij是從vi到vj的長度等于l的路的總數(shù)。 證明 : 歸納法 當(dāng)l1時(shí)， A1A， 由A的定義， 定理顯然成立。 若lk時(shí)定理成立，

5、 則當(dāng)lk1時(shí)， A k+1 A Ak ， 所以 n k=1vkvivj長度長度=1長度長度=l7返回 結(jié)束7.3.1 鄰接矩陣v結(jié)論： (1) 如果對l1， 2， ， n-1， Al的（i， j）項(xiàng)元素（ij）都為零， 那么vi和vj之間無任何路相連接， 即vi和vj不連通。 因此， vi和vj必屬于G的不同的連通分支。 (2) 結(jié)點(diǎn)vi 到vj （ij）間的距離d（vi， vj）是使Al（l1， 2， ， n-1 ）的（i， j）項(xiàng)元素不為零的最小整數(shù)l。 (3) Al的（i， i）項(xiàng)元素a(l)ii表示開始并結(jié)束于vi長度為l的回路的數(shù)目。 8返回 結(jié)束7.3.1 鄰接矩陣?yán)? 圖G（V

6、， E）的圖形如圖， 求鄰接矩陣A和A2， A3， A4， 并分析其元素的圖論意義。解 2340100010100101000200001000101000000100001000100001002000202002020004000020002020000001000100001000001AAAA9返回 結(jié)束7.3.1 鄰接矩陣 (1) 由A中a(1)121知， v1和v2是鄰接的； 由A3中a(3)122知， v1到v2長度為3的路有兩條， 從圖中可看出是v1 v2 v1 v2和v1 v2 v3 v2 。 (2) 由A2的主對角線上元素知， 每個(gè)結(jié)點(diǎn)都有長度為的回路， 其中結(jié)點(diǎn)v2有兩條

7、： v2 v1 v2和v2 v3 v2 ， 其余結(jié)點(diǎn)只有一條。 (3) 由于A3的主對角線上元素全為零， 所以G中沒有長度為的回路。 (4) 由于a（）34a（）34a（）34a（）34， 所以結(jié)點(diǎn)v3和v4間無路， 它們屬于不同的連通分支。 (5) d（v1， v3）。 對其他元素讀者自己可以找出它的意義。 10返回 結(jié)束7.3.1 鄰接矩陣設(shè)圖，如下圖所示討論（1）圖G的鄰接矩陣中的元素為0和1，又稱為布爾矩陣；（2）圖G的鄰接矩陣中的元素的次序是無關(guān)緊要的，進(jìn)行行和行、列和列的交換，則得到相同矩陣。若有二個(gè)簡單有向圖，則可得到二個(gè)對應(yīng)的鄰接矩陣，若對某一矩陣進(jìn)行行和行、列和列之間的交換后

8、得到和另一矩陣相同的矩陣，則此二圖同構(gòu)。（3）當(dāng)有向圖中的有向邊表示關(guān)系時(shí)，鄰接矩陣就是關(guān)系矩陣；（4）零圖的鄰接矩陣稱為零矩陣，即矩陣中的所有元素均為0；（5）在圖的鄰接矩陣中， 行中1的個(gè)數(shù)就是行中相應(yīng)結(jié)點(diǎn)的引出次數(shù) 列中1的個(gè)數(shù)就是列中相應(yīng)結(jié)點(diǎn)的引入次數(shù)A11返回 結(jié)束7.3.1 鄰接矩陣v矩陣的計(jì)算矩陣的計(jì)算：ATATAAAAT主對角線上的數(shù)表示結(jié)點(diǎn)i（或j）的引出次數(shù)。 主對角線上的數(shù)表示結(jié)點(diǎn)i（或j）的引入次數(shù)。 12返回 結(jié)束7.3.1 鄰接矩陣AAA2AAA23AAA34表示i和j之間具有長度為2的通路數(shù)，表示i和j之間具有長度為3的通路數(shù)，表示i和j之間具有長度為4的通路數(shù)，

9、2A3A4A13返回 結(jié)束7.3.1 鄰接矩陣bij表示從結(jié)點(diǎn)vi到vj有長度分別為1，2，3，4的不同通路總數(shù)。此時(shí)， bij0，表示從vi到vj是可達(dá)的。43214AAAAB14返回 結(jié)束7.3.1 鄰接矩陣2.有向圖的鄰接矩陣1、設(shè)有向圖,DV E12,nVv vv，EmD的鄰接矩陣(1)()ijn nA Da，其中指鄰接到的邊的條數(shù) (非負(fù)整數(shù))。(1)ijaivjv15返回 結(jié)束7.3.1 圖的矩陣表示有向圖的鄰接有向圖的鄰接矩陣矩陣16返回 結(jié)束7.3.2 鄰接矩陣v例例1 有向圖(下圖所示)，求D()A D。解：解：12100010()00010010A D17返回 結(jié)束7.3.

10、2 關(guān)聯(lián)矩陣v關(guān)聯(lián)矩陣多用于簡單無向圖v無向圖的關(guān)聯(lián)矩陣一個(gè)圖 由它的頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系唯一確定；( , )GV E( )()ijp qB Gbjeivijb12,pVv vv定義定義 1.6.1 設(shè) 的頂點(diǎn)集和邊集分別為 ， 。用 表示頂點(diǎn) 與邊 關(guān)聯(lián)的次數(shù)(0，1或2)，稱矩陣 為 的關(guān)聯(lián)矩陣。( , )GV E12,qEe eeG18返回 結(jié)束7.3.2 關(guān)聯(lián)矩陣v例1G下圖所示 的關(guān)聯(lián)矩陣為：對應(yīng)的關(guān)聯(lián)矩陣12345678912345000010011111000101( )110000000001211000000001110eeeeeeeeevvB Gvvv從圖的關(guān)聯(lián)矩陣的定義容易

11、得出以下性質(zhì)： 的每一列元素之和均為2； 的每一行元素之和等于對應(yīng)頂點(diǎn)的度數(shù)。若某行元素全為0，則對應(yīng)的頂點(diǎn)為孤立點(diǎn)。(1) 重邊所對應(yīng)的列完全相同。( )B G( )B G210jijjijjiexeexeex關(guān)聯(lián)于 ， 是自環(huán)關(guān)聯(lián)于 ， 不是自環(huán)不關(guān)聯(lián)與=ijb19返回 結(jié)束7.3.2 關(guān)聯(lián)矩陣v有向圖的關(guān)聯(lián)矩陣1、設(shè)有向圖有向圖,DV E12,nVv vv，12,mEe ee，的關(guān)聯(lián)矩陣D()()ijn mM Dm，101ijijijijvemveve為 的始點(diǎn)與 不關(guān)聯(lián)為 的終點(diǎn)其中2110jijijjijjiexDexeDexeex是自環(huán)，且關(guān)聯(lián)與在 中 以 為起點(diǎn)， 不是自環(huán)在 中 以 為終點(diǎn)， 不是自環(huán)與 不關(guān)聯(lián)20返回 結(jié)束7.3.2 關(guān)聯(lián)矩陣v例例2 有向圖(下圖所示)，求D()M D。1100010111()0000101110M D解：解：A(D)A(D)21返回 結(jié)束7.3.3 有向圖的可達(dá)性矩陣v有向圖的可達(dá)性矩陣。有向圖的可達(dá)性矩陣。(了解了解)設(shè)為有向圖，,DV E12,nVv vv令1iip ，1,2,in1()0ijijvvpij可達(dá)否則可達(dá)性矩陣()ijn nPp其中元素可由求得：()ijpij(1)1nnijn nBb