離散數(shù)學第七章第三節(jié)

1、1第7-3講 圖的矩陣表示1. 鄰接矩陣2. 可達性矩陣和連通矩陣3. 關(guān)聯(lián)矩陣4. 課堂練習5. 第7-3講 作業(yè)21、鄰接矩陣（1）定義1 設(shè)設(shè)G=簡單圖簡單圖,它有它有n個結(jié)點個結(jié)點v1, v2,vn V， 則則n階階方陣方陣A(G)=(aij)稱為稱為G的鄰接矩陣，這里的鄰接矩陣，這里例如，左下圖的例如，左下圖的鄰接矩陣鄰接矩陣列于右側(cè)：列于右側(cè)：jivvvvajijiij或不鄰接鄰接010001101111000010)(GA31、鄰接矩陣（2） 圖的鄰接矩陣顯然與圖的鄰接矩陣顯然與n個結(jié)點的標定次序有關(guān)，因而同一個個結(jié)點的標定次序有關(guān)，因而同一個圖可得出不同的鄰接矩陣。不過這些矩陣

2、可以通過交換行和圖可得出不同的鄰接矩陣。不過這些矩陣可以通過交換行和列而相互得出。具有這樣性質(zhì)的矩陣稱它們列而相互得出。具有這樣性質(zhì)的矩陣稱它們置換等價。 例如，左下圖的兩個例如，左下圖的兩個置換等價鄰接矩陣置換等價鄰接矩陣：0001101111000010)(GA010000011101101041324132vvvvvvvv 置換等價是置換等價是n階布爾矩陣集合上的一個等價關(guān)系。階布爾矩陣集合上的一個等價關(guān)系。 我們忽略鄰接矩陣的多樣性，可取圖我們忽略鄰接矩陣的多樣性，可取圖G的任一鄰接矩陣視為的任一鄰接矩陣視為該圖的鄰接矩陣該圖的鄰接矩陣41、鄰接矩陣（3） 簡單有向圖簡單有向圖G的鄰接

3、矩陣的鄰接矩陣A(G)=(aij)n n的第的第i行元素之和等于行元素之和等于vi的出度。第的出度。第j列元素之和等于列元素之和等于vj的入度。的入度。 例如，左下有向圖中，例如，左下有向圖中， v3的出度的出度=1+1+0+1=3， v3的入度的入度=0+1+0+0=10001101111000010)(GA010000011101101041324132vvvvvvvv51、鄰接矩陣（4）定理1 設(shè)簡單有向圖設(shè)簡單有向圖G=的鄰接矩陣為的鄰接矩陣為A，則矩陣，則矩陣Ak中的中的第第i行第行第j列元素等于列元素等于G中連結(jié)中連結(jié)vi與與vj長度為長度為k的路的數(shù)目的路的數(shù)目 。 例如，左下有

4、向圖，例如，左下有向圖， A2中的第中的第2行第行第1列元素等于列元素等于2，說明連，說明連結(jié)結(jié)v2與與v1長度為長度為2的路的有兩條：的路的有兩條： v2 v4 v1 ， v2 v3 v1 。0001101111000010)(GA00101111101211002A分析分析: a21(2)= a21a11+a22a21+ a23a31+a24a41=00+00+11+11=2注意從注意從v2到到v1長度為長度為2的路中間必經(jīng)由一個結(jié)點的路中間必經(jīng)由一個結(jié)點vk,即即v2 vk v1(1 k 4)。K=3時，時，a23 a31= 11表示表示v2到到v3、v3到到v1有路有路(邊邊)。61、

5、鄰接矩陣（5）定理1 設(shè)簡單有向圖設(shè)簡單有向圖G=的鄰接矩陣為的鄰接矩陣為A，則矩陣，則矩陣Ak中的中的第第i行第行第j列元素等于列元素等于G中連結(jié)中連結(jié)vi與與vj長度為長度為k的路的數(shù)目的路的數(shù)目 。 證明思路分析：對此定理不作全面證明。從對此定理不作全面證明。從A A2 2為例作一些說為例作一些說明。計算明。計算連結(jié)連結(jié)vi與與vj長度為長度為2的路的數(shù)目，注意從的路的數(shù)目，注意從vi到到vj長度為長度為2的路中間必經(jīng)由一個結(jié)點的路中間必經(jīng)由一個結(jié)點vk,即即vi vk vj(1 k n)，而且，而且aik=akj=1，那么，那么aikakj=1。反之，如果不存在路徑。反之，如果不存在路

6、徑vi vk vj，則，則aik=0或或akj=0，從而，從而aikakj=0。所以從。所以從vi到到vj長度為長度為2的路徑的的路徑的數(shù)目等于數(shù)目等于nkkjiknjinjijijkijnijijiaaaaaaaavvvvvvvvvvvv1221121.按矩陣的乘法法則，此和式恰好是按矩陣的乘法法則，此和式恰好是A2中中第第i行第行第j列元素列元素aij(2)。71、鄰接矩陣（6）定理1 設(shè)簡單有向圖設(shè)簡單有向圖G=的鄰接矩陣為的鄰接矩陣為A，則矩陣，則矩陣Ak中的中的第第i行第行第j列元素等于列元素等于G中連結(jié)中連結(jié)vi與與vj長度為長度為k的路的數(shù)目的路的數(shù)目 。 證明思路分析(續(xù))：計

7、算計算連結(jié)連結(jié)vi與與vj長度為長度為3的路徑的數(shù)目，的路徑的數(shù)目，注意從注意從vi到到vj長度為長度為3的路徑可視為從的路徑可視為從vi 到中間結(jié)點到中間結(jié)點vk長度為長度為1的路徑，再加上從的路徑，再加上從vk到到vj長度為長度為2的路徑，所以從的路徑，所以從vi到到vj長度為長度為3的路徑的數(shù)目等于的路徑的數(shù)目等于23)3(1)2()3()(AAAaaaannijnkkjikij那么0001101111000010A00101111101211002A11002122112110123A82、可達性矩陣和連通矩陣(1)定義2 設(shè)G=為簡單有向圖，V=v1,v2,vn，定義矩陣P=（pij

8、）,其中 有向圖有向圖G G中從中從v vi i到到v vj j是否有路可達可通過矩陣運算而得到。是否有路可達可通過矩陣運算而得到。 由圖G的鄰接矩陣A可得可達性矩陣P，令，令 Bn=A+A2+An=(bij)n nBn中的元素中的元素bij表示表示從從v vi i到到v vj j是長度等于或小于是長度等于或小于n n的路徑數(shù)。若的路徑數(shù)。若bij 0，則表示，則表示從從v vi i到到v vj j可達。這樣，將可達。這樣，將Bn中不為零的元素全中不為零的元素全部換成部換成1，而等于零的元素保持不變，即得可達矩陣。，而等于零的元素保持不變，即得可達矩陣。不存在路到從至少存在一條路到從jiji0

9、1vvvvpijP稱為圖G的可達性矩陣。92、可達性矩陣和連通矩陣(2)求可達性矩陣可簡化為：(1) 由圖G的鄰接矩陣A求可達性矩陣P: P=A(1) A(2) A(n) 其中的元素其中的元素A(i)表示表示Ai對應的布爾對應的布爾矩陣矩陣。(2)用Warshall算法計算： 因為有向簡單圖的鄰接矩陣因為有向簡單圖的鄰接矩陣A A可視為具有可視為具有n n個結(jié)點的集合個結(jié)點的集合V V 上上的鄰接關(guān)系的鄰接關(guān)系R R的關(guān)系矩陣，而可達矩陣可視為鄰接關(guān)系的關(guān)系矩陣，而可達矩陣可視為鄰接關(guān)系R R的傳遞的傳遞閉包所對應的矩陣。閉包所對應的矩陣。 設(shè)設(shè)A=(aA=(aijij) )n n、 B=(b

10、B=(bijij) )n n是是布爾矩陣，令布爾矩陣，令C=AC=A B=(cB=(cijij) )n n，稱為稱為布爾矩陣求“和”；令令D=AD=A B=(dB=(dijij) )n n，稱為，稱為布爾矩陣求“積”。其中：其中：kjiknkijijijijbadbac1102、可達性矩陣和連通矩陣(3)方法方法1：先由鄰接矩陣A求B4, B4=A+A2+A3+A4然后寫出可達矩陣然后寫出可達矩陣P。 計算可達矩陣舉例:0000101111001010A00002110101111002A00002111211010113A00003121211121104A00001111111111110

11、0008353633252314PB00001111111111110000111111111110000011111110101100001110101111000000101111001010p方法方法2：將A、A2、A3、A4轉(zhuǎn)換為布爾矩陣A(1)、A(2)、A(3)、A(4)， 則則 P=A(1) A(2) A(3) A(4)。 112、可達性矩陣和連通矩陣(4)(3)用Warshall算法計算:計算可達矩陣舉例（續(xù)）:0000101111001010A00002110101111002A00002111211010113A00003121211121104A4321000011111

12、1111111:0000111111111111:0000111111001110:0000101111001010:0000101111001010:iiiiAPM123、關(guān)聯(lián)矩陣(1)定義3 設(shè)G=為無向圖，V=v1,v2,vp， E=e1,e2,eq，定義矩陣M(G)=(mij)pq,其中例如，寫出下圖的關(guān)聯(lián)矩陣。例如，寫出下圖的關(guān)聯(lián)矩陣。jiji01evevmij不關(guān)聯(lián)關(guān)聯(lián)M(G)稱為圖G的完全關(guān)聯(lián)矩陣。000000011000101100000111110011)(54321654321vvvvveeeeeeGM133、關(guān)聯(lián)矩陣(2)從完全關(guān)聯(lián)矩陣可得出圖的有關(guān)信息：從完全關(guān)聯(lián)矩陣可

13、得出圖的有關(guān)信息： (1)(1)因每邊只關(guān)聯(lián)兩個結(jié)點，故每列有且只有兩個因每邊只關(guān)聯(lián)兩個結(jié)點，故每列有且只有兩個1 1，其余，其余為為0 0。 (2)(2)每行各元素之和即相應結(jié)點的度數(shù)。每行各元素之和即相應結(jié)點的度數(shù)。 (3)(3)若某行各元素皆為若某行各元素皆為0 0，則相應結(jié)點為孤立結(jié)點。，則相應結(jié)點為孤立結(jié)點。 (4)(4)平行邊所對應的列完全相同。平行邊所對應的列完全相同。 (5)(5)同一個圖取不同的點、邊序列，其對應的關(guān)聯(lián)矩陣僅同一個圖取不同的點、邊序列，其對應的關(guān)聯(lián)矩陣僅存在行序和列序的差異。存在行序和列序的差異。000000011000101100000111110011)(

14、54321654321vvvvveeeeeeGM143、關(guān)聯(lián)矩陣(3)定義4 設(shè)G=為簡單有向圖，V=v1,v2,vp， E=e1,e2,eq，定義矩陣M(G)=(mij)pq,其中例如，寫出如下簡單有向圖的關(guān)聯(lián)矩陣。例如，寫出如下簡單有向圖的關(guān)聯(lián)矩陣。不關(guān)聯(lián)與的終點是的起點是jijiji011evevevmijM(G)稱為有向圖G的完全關(guān)聯(lián)矩陣。00110000101100100011000000111110001)(543217654321vvvvveeeeeeeGM153、關(guān)聯(lián)矩陣(4)從有向圖的完全關(guān)聯(lián)矩陣可得出圖的有關(guān)信息：從有向圖的完全關(guān)聯(lián)矩陣可得出圖的有關(guān)信息： (1) (1)

15、每邊關(guān)聯(lián)一個始點，一個終點。故每列只有一個元素為每邊關(guān)聯(lián)一個始點，一個終點。故每列只有一個元素為1 1，一個元素為一個元素為-1-1，其余為，其余為0 0。 (2)(2)每行的每行的1 1之和即相應結(jié)點的出度，之和即相應結(jié)點的出度，-1-1之和即相應結(jié)點的入之和即相應結(jié)點的入度。度。 (3)(3)若某行各元素皆為若某行各元素皆為0 0，則相應結(jié)點為孤立結(jié)點。，則相應結(jié)點為孤立結(jié)點。 (4)(4)平行邊所對應的列完全相同。平行邊所對應的列完全相同。 00110000101100100011000000111110001)(543217654321vvvvveeeeeeeGM163、關(guān)聯(lián)矩陣(5)

16、定理2 設(shè)連通圖G有r個結(jié)點，則其完全關(guān)聯(lián)矩陣的秩為r-1。 (證明從略)兩個關(guān)于關(guān)聯(lián)矩陣的秩的結(jié)論：推 論 設(shè)圖G有r個結(jié)點，w個最大連通子圖，則圖G的完全關(guān)聯(lián)矩陣的秩為r-w。注：(1) 矩陣中的任意矩陣中的任意k階方陣的行列式該矩陣的階方陣的行列式該矩陣的k階子式。階子式。(2) 矩陣矩陣A中不為中不為0的子式的最大階數(shù)的子式的最大階數(shù)r叫叫A的秩。的秩。(3) 交換矩陣中兩行或兩列；用非零數(shù)乘矩陣的某行或某列；交換矩陣中兩行或兩列；用非零數(shù)乘矩陣的某行或某列；用非零數(shù)乘矩陣的某行或某列后再加到另一行或列的對應元素上。以用非零數(shù)乘矩陣的某行或某列后再加到另一行或列的對應元素上。以上三種變換叫矩陣的初等變換。初等變換不改變矩陣的秩。上三種變換叫矩陣的初等變換。初