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

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

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

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

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

5、邊對應(yīng)的列相同。 （5）結(jié)點或邊編序不同，對應(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)矩陣也有類似于無向圖的一些性質(zhì),（1）M（G）中每一列中有且僅有兩個1，對應(yīng)圖中每一邊關(guān)聯(lián)兩個結(jié)點。 （2）每一行中元素的和為對應(yīng)結(jié)點的度數(shù)。 （3）一行中若元素全為0，則其對應(yīng)的結(jié)點為孤立結(jié)點。 （4）平行邊對應(yīng)的列相同。 （5）結(jié)點或邊編序不同，對應(yīng)完全關(guān)聯(lián)矩陣只有行序、列序的差別。,（1）每一列中一個值為1，一個為

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