7-3 圖的矩陣表示

1、Discrete Mathematics 1課程回顧路：路、通路、跡、圈、無(wú)向圖的連通性：點(diǎn)與點(diǎn)的連通性、連通分支、連通圖、割點(diǎn)、點(diǎn)連通度、割邊、邊連通度、相關(guān)定理有向圖的連通性：可達(dá)、距離、單側(cè)連通、強(qiáng)連通、弱連通、強(qiáng)分圖、單側(cè)分圖、弱分圖2第七章 圖論第3講 73 圖的矩陣表示 7-4 歐拉圖和漢密爾頓圖(上)37-3 圖的矩陣表示 給定一個(gè)圖G=，使用圖形表示法很容易把圖的結(jié)構(gòu)展現(xiàn)出來(lái)，而且這種表示直觀明了。但這只在結(jié)點(diǎn)和邊(或弧)的數(shù)目相當(dāng)小的情況下才是可行的。顯然這限制了圖的利用。本節(jié)提供另一種圖的表示法圖的矩陣表示法。它不僅克服了圖形表示法的不足，而且這種表示可以充分利用現(xiàn)代工具電

2、子計(jì)算機(jī)，以達(dá)到研究圖的目的。4學(xué)習(xí)本節(jié)要熟悉如下術(shù)語(yǔ)（4個(gè)）：鄰接矩陣、有向圖的完全關(guān)聯(lián)矩陣、可達(dá)性矩陣、掌握2個(gè)定理，1個(gè)推論。重在計(jì)算求解。無(wú)向圖的完全關(guān)聯(lián)矩陣、5 一個(gè)簡(jiǎn)單圖G=由V中每?jī)蓚€(gè)結(jié)點(diǎn)間的鄰接關(guān)系唯一地確定，這種關(guān)系可以用一個(gè)矩陣給出，而矩陣形式與圖中結(jié)點(diǎn)的編序有密切關(guān)系，這是用矩陣表示圖值得注意的一點(diǎn)。6 一、鄰接矩陣 定義7-3.1 設(shè)G=是一個(gè)簡(jiǎn)單圖，它有n個(gè)結(jié)點(diǎn)V=v1,v2,vn ，則n階方陣A(G)=(aij)nn稱(chēng)為圖G的鄰接矩陣(adjacency matrix) 。其中： 1 vi adj vj 0 vi nadj vj 或 i=jadj表示鄰接， nadj

3、表示不鄰接。aij=7 0 1 0 0A(G1)= 0 0 1 1 1 1 0 1 1 0 0 0例如 0 1 1 1 1 1 0 1 0 0A(G)= 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)矩陣，有向圖的鄰接矩陣不一定是對(duì)稱(chēng)的。無(wú)向圖有向圖8 0 0 1 1 1 0 0 0A(G2)= 1 1 0 1 0 1 0 0圖G2的鄰接矩陣是將圖G1的鄰接矩陣第一、二行對(duì)調(diào)，第一、二列對(duì)調(diào)得到的。 0 1 0 0A(G1)= 0 0 1 1 1 1 0 1 1 0 0 09 對(duì)于給定圖G，顯然不會(huì)因結(jié)點(diǎn)編序不同而使其結(jié)構(gòu)發(fā)生任何變化，即圖的結(jié)點(diǎn)所有不同的編序

4、實(shí)際上仍表示同一個(gè)圖。 換句話說(shuō)，這些結(jié)點(diǎn)的不同編序的圖都是同構(gòu)的，并且它們的鄰接矩陣都是相似的。于是G與H同構(gòu)存在置換矩陣P，使A(H)=P-1A(G)P。 今后將略去這種由于V中結(jié)點(diǎn)編序而引起鄰接矩陣的任意性，而取該圖的任一個(gè)鄰接矩陣作為該圖的矩陣表示。10鄰接矩陣可展示相應(yīng)圖的一些性質(zhì)： 若鄰接矩陣的元素全為零，則其對(duì)應(yīng)的圖是零圖； 若(無(wú)向圖)鄰接矩陣的元素除主對(duì)角線元素外全為1，則其對(duì)應(yīng)的圖是簡(jiǎn)單完全圖。 (有向圖)鄰接矩陣的元素除主對(duì)角線元素外全為1，則其對(duì)應(yīng)的圖是強(qiáng)連通圖。11 當(dāng)給定的簡(jiǎn)單圖是無(wú)向圖時(shí)，鄰接矩陣是對(duì)稱(chēng)矩陣；反之，若給定任何對(duì)稱(chēng)矩陣A，顯然可以唯一地作出以A為其鄰

5、接矩陣的簡(jiǎn)單圖G。 于是，所有n個(gè)結(jié)點(diǎn)的不同編序的簡(jiǎn)單圖的集合與所有n階對(duì)稱(chēng)矩陣的集合可建立一一對(duì)應(yīng)。12 當(dāng)給定的圖是簡(jiǎn)單有向圖時(shí)，其鄰接矩陣并非一定是對(duì)稱(chēng)矩陣，但所有n個(gè)結(jié)點(diǎn)的不同編序的簡(jiǎn)單圖的集合，與所有n階鄰接矩陣的集合亦可建立一一對(duì)應(yīng)。13簡(jiǎn)單有向圖的鄰接矩陣的性質(zhì) (1)第i行中值為1的元素?cái)?shù)目等于結(jié)點(diǎn)vi的出度。 (2)第j列中值為1的元素?cái)?shù)目等于結(jié)點(diǎn)vj的入度。14定理7-3.1:設(shè)G的結(jié)點(diǎn)集為v1,v2,vn，鄰接矩陣為A，則矩陣AL（L=1，2，）的第i行j列的元素aij(L)表示圖G中連接結(jié)點(diǎn)vi到vj長(zhǎng)度為L(zhǎng)的路的數(shù)目。注：設(shè)圖G有n個(gè)結(jié)點(diǎn)V=v1,v2,vn，（二）鄰

6、接矩陣的應(yīng)用15定理7-3.1證明思路 對(duì)l用數(shù)學(xué)歸納法證明。 1) 當(dāng)l=2時(shí):aij (2)等于G中聯(lián)結(jié)vi與vj的長(zhǎng)度為2的路徑條數(shù)。 2)設(shè)命題對(duì)l成立，即：aij (l)等于G中聯(lián)結(jié)vi與vj的長(zhǎng)度為l的路徑條數(shù)。 3)現(xiàn)證l+1時(shí)也成立。即(A(G)l+1=(A(G). (A(G)l n aij (l+1) = aik akj (l) k=1 對(duì)k求和即得結(jié)論。 vkvivj長(zhǎng)度=1長(zhǎng)度=l共akj (l)條16例: 給定一圖G=V，E如圖所示。求A，A2，A3，A417Matlab計(jì)算：A=0 1 0 0 0;1 0 1 0 0;0 1 0 0 0;0 0 0 0 1;0 0 0

7、 1 0B=A*AA2A318練習(xí)300頁(yè)（1） 求出圖7-3.9中有向圖的鄰接矩陣A，找出從v1到v4長(zhǎng)度為2和4的路，用計(jì)算A2，A3，A4來(lái)驗(yàn)證這結(jié)論。解A= 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 1 0 2 0 1 0 1 1 1 0 0 1 1A2= 0 2 1 2 0 1 2 2 0 2 1 2 0 2 0 1A3= 0 3 2 3 0 4 1 3 0 3 2 3 0 1 2 2A4=從v1到v4長(zhǎng)度為2的路為v1 v2 v4從v1到v4長(zhǎng)度為4的路有：v1 v2 v4 v2 v4 v1 v2 v3 v2 v4 v1 v4 v2 v3 v4 1

8、9 在一些實(shí)際問(wèn)題中，有時(shí)要判定圖中結(jié)點(diǎn)vi到結(jié)點(diǎn)vj是否可達(dá)，或者說(shuō)vi到vj是否存在路。如果利用圖G的鄰接矩陣A，則可計(jì)算A2，A3，An，。當(dāng)發(fā)現(xiàn)其中某個(gè)Al的aij(l)1，就表明vi可達(dá)vj或vi到vj存在一條路。但這種計(jì)算繁瑣量大，另外計(jì)算Al到何時(shí)為止？20 根據(jù)定理7-2.1的推論可知，如果有向圖G有n個(gè)結(jié)點(diǎn)， vi到vj有一條路，則必然有一條長(zhǎng)度不大于n的通路，因此，只需考慮aij(l)就可以了，其中1ln。即只要計(jì)算Bn=A+A2+A3+An。21 如果關(guān)心的是結(jié)點(diǎn)間可達(dá)性或結(jié)點(diǎn)間是否有路，至于結(jié)點(diǎn)間的路存在多少條及長(zhǎng)度是多少無(wú)關(guān)緊要，那么便可用可達(dá)矩陣來(lái)表示結(jié)點(diǎn)間可達(dá)性。

9、22二、可達(dá)矩陣 可達(dá)性矩陣的求法有兩種： 1) 計(jì)算矩陣 Bn=A+A2+A3+An 令矩陣 Bn中不為零的元素等于1，為零的元素不變，得到P。見(jiàn)例題1。 2) 令P =AA(2) A(3) A(n) 其中A(i)(i=1,2,n)為布爾矩陣。見(jiàn)例題2。 定義7-3.2 設(shè)G=是一個(gè)簡(jiǎn)單有向圖，它有n個(gè)已經(jīng)編序的結(jié)點(diǎn)V=v1,v2,vn，定義n階方陣P(G)=(pij)nn稱(chēng)為圖G的可達(dá)性矩陣 。其中： 1 從vi到 vj至少存在一條路。 0 從vi到 vj不存在路。pij=23 可見(jiàn)，可達(dá)矩陣表明了圖中任意兩結(jié)點(diǎn)間是否至少存在一條路以及在結(jié)點(diǎn)處是否有回路。 從圖G的鄰接矩陣A可以得到可達(dá)矩

10、陣P，即令Bn=A+A2+A3+An，再?gòu)腂n中非零元素改為1而零元素不變，這種變換后的矩陣即是可達(dá)矩陣P。24 無(wú)向圖的可達(dá)矩陣：可將每條無(wú)向邊看成是具有相反方向的兩條邊，因此是對(duì)稱(chēng)矩陣，又稱(chēng)為連通矩陣。25練習(xí)：300頁(yè)（2）如果u可達(dá)v，它們之間可能不止一條路，在所有這些路中，最短路的長(zhǎng)度稱(chēng)為u和v之間的距離（或短程線），記作d，如果從u到v是不可達(dá)的，則通常寫(xiě)成 d =26距離矩陣為 0 1 2 1 0 1 1 1 0 1 1 2 0A= 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 1 0 2 0 1 0 1 1 1 0 0 1 1A2= 0 2 1 2

11、 0 1 2 2 0 2 1 2 0 2 0 1A3= 0 3 2 3 0 4 1 3 0 3 2 3 0 1 2 2A4=27三、關(guān)聯(lián)矩陣1、無(wú)向圖的關(guān)聯(lián)矩陣 定義7-3.3 給定無(wú)向圖G=,設(shè) v1, v2, vpV, e1, eqE, 稱(chēng)pq階矩陣M (G)=(mij)pq 為圖G的完全關(guān)聯(lián)矩陣（incidence matrix）。其中: 1 若vi關(guān)聯(lián) ej。 0 若vi不關(guān)聯(lián) ej。 mij=28 例:求下圖G的關(guān)聯(lián)矩陣上圖G的關(guān)聯(lián)矩陣:29 無(wú)向圖的關(guān)聯(lián)矩陣反映出來(lái)圖的性質(zhì): 1) 每一條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn),故每一列中只有兩個(gè)1。 2) 每一行中元素之和等于該行對(duì)應(yīng)的結(jié)點(diǎn)的度數(shù)。 3)

12、 一行中元素全為0，其對(duì)應(yīng)結(jié)點(diǎn)為孤立點(diǎn)。 4) 兩個(gè)平行邊其對(duì)應(yīng)的兩列相同。 5) 同一個(gè)圖當(dāng)結(jié)點(diǎn)或邊的編號(hào)不同時(shí)，其對(duì)應(yīng)的矩陣只有行序列序的差別。302、有向圖的關(guān)聯(lián)矩陣 定義7-3.4 給定簡(jiǎn)單有向圖G=,設(shè) v1, v2, vpV, e1, eqE, 稱(chēng)pq階矩陣M (G)=(mij)pq 為圖G的完全關(guān)聯(lián)矩陣(incidence matrix)。其中: 1 若vi是 ej的起點(diǎn)。 -1 若vi是 ej的終點(diǎn)。 0 若vi不關(guān)聯(lián) ej。 mij=31例：寫(xiě)出下圖的完全關(guān)聯(lián)矩陣。v1V2V3V4v5M(G)=e1 e2 e3 e4 e5 e6 e71 0 0 0 1 1 1-1 1 0 0

13、 0 0 00 -1 1 0 0 -1 00 0 -1 1 0 0 -10 0 0 -1 -1 0 0e3e1e2e5e4e6e7v2v1v3v4v532 有向圖的關(guān)聯(lián)矩陣的特點(diǎn)： (1)每一列中有一個(gè)1和一個(gè)-1，對(duì)應(yīng)一邊一個(gè)始點(diǎn)、一個(gè)終點(diǎn)，元素和為零。 (2)每一行元素的絕對(duì)值之和為對(duì)應(yīng)點(diǎn)的度數(shù)。-1的個(gè)數(shù)等于入度，1的個(gè)數(shù)等于出度。33 有向圖G的兩行相加定義為：第i行第j行的對(duì)應(yīng)元素算術(shù)相加；相當(dāng)于刪除結(jié)點(diǎn)vi與結(jié)點(diǎn)vj之間的關(guān)聯(lián)邊，合并結(jié)點(diǎn)vi和vj 。合并后得到的新結(jié)點(diǎn)記為vi,j 。 無(wú)向圖G的兩行相加定義為：第i行第j行的對(duì)應(yīng)元素模2相加；相當(dāng)于刪除結(jié)點(diǎn)vi與結(jié)點(diǎn)vj之間的關(guān)聯(lián)邊，合并結(jié)點(diǎn)vi和vj 。合并后得到的新結(jié)點(diǎn)記為vi,j 。 343、關(guān)聯(lián)矩陣的秩 舉例 299頁(yè)例3 定理7-3.2