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

1、圖的矩陣表示,1.鄰接矩陣：,設(shè)G=是一個(gè)簡(jiǎn)單圖， 是G的n個(gè)結(jié)點(diǎn)， 則n階方陣A(G)=(aij)稱為G的鄰接矩陣。其中：,adj表是鄰接，nadj表示不鄰接。,v2,v1,簡(jiǎn)單圖是無(wú)向圖，鄰接矩陣是對(duì)稱的； 簡(jiǎn)單圖是有向圖時(shí)，鄰接矩陣不一定對(duì)稱。,對(duì)于給定集合A上的關(guān)系R，可以用有向圖來(lái)表示，而對(duì)于關(guān) 系圖，又可以用一個(gè)矩陣表示，所以對(duì)于一般形式的圖，也 給出其矩陣表示。,在鄰接矩陣A中，第i行中值為1的元素個(gè)數(shù)等于vi的出度； 第j列中值為1的元素個(gè)數(shù)等于vj的入度。,零矩陣對(duì)應(yīng)零圖；,(僅有孤立結(jié)點(diǎn)組成的圖稱為零圖),設(shè)有向圖G的結(jié)點(diǎn)集合 ，它的鄰接矩陣為 ，現(xiàn)在我們想計(jì)算從結(jié)點(diǎn) 到

2、結(jié)點(diǎn) 的長(zhǎng)度為2的路的數(shù)目,分析：從 到 長(zhǎng)度為2的路，中間必須經(jīng)過 如果圖G中有路 存在，則肯定有 ，反之如果圖G中不存在路 ，那么 或者 ， 即 于是從結(jié)點(diǎn) 到 的長(zhǎng)度為2的路的數(shù)目就等于：,按照矩陣的乘法規(guī)則，上式恰好等于矩陣 中第i行，第j列的元素，即 ； 表示從 到 的長(zhǎng)度為2的路的數(shù)目,定理： A(G)是圖G的鄰接矩陣，則(A(G)l中的i行，j列元素 aij(l)等于G中聯(lián)結(jié)vi與vj的長(zhǎng)度為l的路的數(shù)目。,證明：用數(shù)學(xué)歸納法,當(dāng)l=2時(shí)，由上面證明知顯然成立,假設(shè)命題對(duì)l成立，只需證明當(dāng)l=l+1時(shí)也成立即可,由 所以,在實(shí)際問題中，常需要考慮到結(jié)點(diǎn)之間是否存在路的問題。 可以

3、通過計(jì)算A,A2,.,An,.，當(dāng)發(fā)現(xiàn)某個(gè)Al的第i行,第j列不為0， 就表明vi到vj可達(dá)。,由前面的定理7-2.1的推論可知，如果在vi到vj之間存在路，必定存在 一條長(zhǎng)度不超過n的通路，所以l只需計(jì)算到n就可以了。,推論： G有n個(gè)結(jié)點(diǎn)， A是鄰接矩陣， ，bij為Bn的i行，j列元素，若bij0，則表明vi，vj中存在路。,對(duì)于簡(jiǎn)單有向圖的任意兩個(gè)結(jié)點(diǎn)之間的可達(dá)性，也可以用矩陣 表示出來(lái)，即可達(dá)性矩陣,2、可達(dá)性矩陣： G=是簡(jiǎn)單有向圖，|V|=n，定義nxn矩陣,P=(pij)為可達(dá)性矩陣，其中,將Bn中不為零的元素值改為1，就可得到可達(dá)性矩陣P。,例1： 設(shè)圖G的鄰接矩陣為 ，求G

4、的可達(dá)性矩陣。,解：,對(duì)于無(wú)向圖，鄰接矩陣是一個(gè)對(duì)稱矩陣，其可達(dá)性矩陣也是對(duì)稱的。,上面我們介紹了圖的鄰接矩陣表示和可達(dá)性矩陣表示，可知 這兩種表示方法都是跟結(jié)點(diǎn)相關(guān)的。 還可以給出結(jié)點(diǎn)和邊的關(guān)聯(lián)矩陣，在給出點(diǎn)和邊的關(guān)聯(lián)關(guān)系 時(shí)，假定圖中無(wú)自回路。下面給出完全關(guān)聯(lián)矩陣的概念。,（a）G為無(wú)向圖 設(shè) 為G的結(jié)點(diǎn)集， 為G的邊集，稱矩陣M(G)=(mij)為完全關(guān)聯(lián)矩陣，其中：,3、完全關(guān)聯(lián)矩陣：,完全關(guān)聯(lián)矩陣為：,例：,（1）M（G）中每一列中有且僅有兩個(gè)1，對(duì)應(yīng)圖中每一邊關(guān)聯(lián)兩 個(gè)結(jié)點(diǎn)。 （2）每一行中元素的和為對(duì)應(yīng)結(jié)點(diǎn)的度數(shù)。 （3）一行中若元素全為0，則其對(duì)應(yīng)的結(jié)點(diǎn)為孤立結(jié)點(diǎn)。 （4）平行

5、邊對(duì)應(yīng)的列相同。 （5）結(jié)點(diǎn)或邊編序不同，對(duì)應(yīng)完全關(guān)聯(lián)矩陣只有行序、列序的 差別。,從關(guān)聯(lián)矩陣中看出圖形的一些性質(zhì)：,類似，給出有向圖的完全關(guān)聯(lián)矩陣的定義：,（b）G為有向圖 G=， ， pXq階矩陣M(G)=(mij)為G的完全關(guān)聯(lián)矩陣，其中：,關(guān)聯(lián)矩陣：,有向圖的完全 關(guān)聯(lián)矩陣也有類似于無(wú)向圖的一些性質(zhì),（1）M（G）中每一列中有且僅有兩個(gè)1，對(duì)應(yīng)圖中每一邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)。 （2）每一行中元素的和為對(duì)應(yīng)結(jié)點(diǎn)的度數(shù)。 （3）一行中若元素全為0，則其對(duì)應(yīng)的結(jié)點(diǎn)為孤立結(jié)點(diǎn)。 （4）平行邊對(duì)應(yīng)的列相同。 （5）結(jié)點(diǎn)或邊編序不同，對(duì)應(yīng)完全關(guān)聯(lián)矩陣只有行序、列序的差別。,（1）每一列中一個(gè)值為1，一個(gè)為

6、-1，對(duì)應(yīng)圖中的一條有向邊。,（2）把一行中的值為1的元素相加，得到頂點(diǎn)的出度，把值為-1的元素相加，得到頂點(diǎn)的入度。,（3）一行中元素全為0，對(duì)應(yīng)孤立結(jié)點(diǎn)。,（4）平行邊對(duì)應(yīng)的列相同。,（5）結(jié)點(diǎn)或邊編序不同，對(duì)應(yīng)完全關(guān)聯(lián)矩陣只有行序、列序的差別。,例,行相加運(yùn)算： 有向圖：對(duì)應(yīng)分量普通加法運(yùn)算； 無(wú)向圖：對(duì)應(yīng)分量模2加法運(yùn)算。 行相加相當(dāng)于G中對(duì)應(yīng)結(jié)點(diǎn)的合并。,，說明vi和vj中只有一個(gè)結(jié)點(diǎn)是邊er的端點(diǎn)，合并 后仍是er的端點(diǎn)。,，有兩種情況：,a、vi，vj都不是er的端點(diǎn)； b、vi，vj都是er的端點(diǎn)，合并后刪去自回路。,若合并后完全關(guān)聯(lián)矩陣中出現(xiàn)元素全為0的列，表明對(duì)應(yīng)的 邊消失。,有了這種運(yùn)算，就可以運(yùn)用這種運(yùn)算求關(guān)聯(lián)矩陣的秩,矩陣的秩：矩陣中所有非零子式的最高階數(shù)；就是將矩陣通過初等變換化為行階梯后非零行的行數(shù)。,定理： G為連通圖，有r個(gè)結(jié)點(diǎn)，則其完全關(guān)聯(lián)矩陣M(G)的