離散數(shù)學(xué)第七章第三節(jié)ppt課件

.,1,第7-3講圖的矩陣表示,1.鄰接矩陣2.可達(dá)性矩陣和連通矩陣3.關(guān)聯(lián)矩陣4.課堂練習(xí)5.第7-3講作業(yè),.,2,1、鄰接矩陣（1）,定義1設(shè)G=簡單圖,它有n個結(jié)點(diǎn)v1,v2,vnV，則n階方陣A(G)=(aij)稱為G的鄰接矩陣，這里,例如，左下圖的鄰接矩陣列于右側(cè)：,.,3,1、鄰接矩陣（2）,圖的鄰接矩陣顯然與n個結(jié)點(diǎn)的標(biāo)定次序有關(guān)，因而同一個圖可得出不同的鄰接矩陣。不過這些矩陣可以通過交換行和列而相互得出。具有這樣性質(zhì)的矩陣稱它們置換等價。,例如，左下圖的兩個置換等價鄰接矩陣：,置換等價是n階布爾矩陣集合上的一個等價關(guān)系。我們忽略鄰接矩陣的多樣性，可取圖G的任一鄰接矩陣視為該圖的鄰接矩陣,.,4,1、鄰接矩陣（3）,簡單有向圖G的鄰接矩陣A(G)=(aij)nn的第i行元素之和等于vi的出度。第j列元素之和等于vj的入度。,例如，左下有向圖中，v3的出度=1+1+0+1=3，v3的入度=0+1+0+0=1,.,5,1、鄰接矩陣（4）,定理1設(shè)簡單有向圖G=的鄰接矩陣為A，則矩陣Ak中的第i行第j列元素等于G中連結(jié)vi與vj長度為k的路的數(shù)目。,例如，左下有向圖，A2中的第2行第1列元素等于2，說明連結(jié)v2與v1長度為2的路的有兩條：v2v4v1，v2v3v1。,分析:a21(2)=a21a11+a22a21+a23a31+a24a41=00+00+11+11=2注意從v2到v1長度為2的路中間必經(jīng)由一個結(jié)點(diǎn)vk,即v2vkv1(1k4)。K=3時，a23a31=11表示v2到v3、v3到v1有路(邊)。,.,6,1、鄰接矩陣（5）,定理1設(shè)簡單有向圖G=的鄰接矩陣為A，則矩陣Ak中的第i行第j列元素等于G中連結(jié)vi與vj長度為k的路的數(shù)目。,證明思路分析：對此定理不作全面證明。從A2為例作一些說明。計算連結(jié)vi與vj長度為2的路的數(shù)目，注意從vi到vj長度為2的路中間必經(jīng)由一個結(jié)點(diǎn)vk,即vivkvj(1kn)，而且aik=akj=1，那么aikakj=1。反之，如果不存在路徑vivkvj，則aik=0或akj=0，從而aikakj=0。所以從vi到vj長度為2的路徑的數(shù)目等于,按矩陣的乘法法則，此和式恰好是A2中第i行第j列元素aij(2)。,.,7,1、鄰接矩陣（6）,定理1設(shè)簡單有向圖G=的鄰接矩陣為A，則矩陣Ak中的第i行第j列元素等于G中連結(jié)vi與vj長度為k的路的數(shù)目。,證明思路分析(續(xù))：計算連結(jié)vi與vj長度為3的路徑的數(shù)目，注意從vi到vj長度為3的路徑可視為從vi到中間結(jié)點(diǎn)vk長度為1的路徑，再加上從vk到vj長度為2的路徑，所以從vi到vj長度為3的路徑的數(shù)目等于,.,8,2、可達(dá)性矩陣和連通矩陣(1),定義2設(shè)G=為簡單有向圖，V=v1,v2,vn，定義矩陣P=（pij）,其中,有向圖G中從vi到vj是否有路可達(dá)可通過矩陣運(yùn)算而得到。,由圖G的鄰接矩陣A可得可達(dá)性矩陣P，令Bn=A+A2+An=(bij)nnBn中的元素bij表示從vi到vj是長度等于或小于n的路徑數(shù)。若bij0，則表示從vi到vj可達(dá)。這樣，將Bn中不為零的元素全部換成1，而等于零的元素保持不變，即得可達(dá)矩陣。,P稱為圖G的可達(dá)性矩陣。,.,9,2、可達(dá)性矩陣和連通矩陣(2),求可達(dá)性矩陣可簡化為：(1)由圖G的鄰接矩陣A求可達(dá)性矩陣P:P=A(1)A(2)A(n)其中的元素A(i)表示Ai對應(yīng)的布爾矩陣。(2)用Warshall算法計算：因?yàn)橛邢蚝唵螆D的鄰接矩陣A可視為具有n個結(jié)點(diǎn)的集合V上的鄰接關(guān)系R的關(guān)系矩陣，而可達(dá)矩陣可視為鄰接關(guān)系R的傳遞閉包所對應(yīng)的矩陣。,設(shè)A=(aij)nn、B=(bij)nn是布爾矩陣，令C=AB=(cij)nn，稱為布爾矩陣求“和”；令D=AB=(dij)nn，稱為布爾矩陣求“積”。其中：,.,10,2、可達(dá)性矩陣和連通矩陣(3),方法1：先由鄰接矩陣A求B4,B4=A+A2+A3+A4然后寫出可達(dá)矩陣P。,計算可達(dá)矩陣舉例:,方法2：將A、A2、A3、A4轉(zhuǎn)換為布爾矩陣A(1)、A(2)、A(3)、A(4)，則P=A(1)A(2)A(3)A(4)。,.,11,2、可達(dá)性矩陣和連通矩陣(4),(3)用Warshall算法計算:,計算可達(dá)矩陣舉例（續(xù)）:,.,12,3、關(guān)聯(lián)矩陣(1),定義3設(shè)G=為無向圖，V=v1,v2,vp，E=e1,e2,eq，定義矩陣M(G)=(mij)pq,其中,例如，寫出下圖的關(guān)聯(lián)矩陣。,M(G)稱為圖G的完全關(guān)聯(lián)矩陣。,.,13,3、關(guān)聯(lián)矩陣(2),從完全關(guān)聯(lián)矩陣可得出圖的有關(guān)信息：(1)因每邊只關(guān)聯(lián)兩個結(jié)點(diǎn)，故每列有且只有兩個1，其余為0。(2)每行各元素之和即相應(yīng)結(jié)點(diǎn)的度數(shù)。(3)若某行各元素皆為0，則相應(yīng)結(jié)點(diǎn)為孤立結(jié)點(diǎn)。(4)平行邊所對應(yīng)的列完全相同。(5)同一個圖取不同的點(diǎn)、邊序列，其對應(yīng)的關(guān)聯(lián)矩陣僅存在行序和列序的差異。,.,14,3、關(guān)聯(lián)矩陣(3),定義4設(shè)G=為簡單有向圖，V=v1,v2,vp，E=e1,e2,eq，定義矩陣M(G)=(mij)pq,其中,例如，寫出如下簡單有向圖的關(guān)聯(lián)矩陣。,M(G)稱為有向圖G的完全關(guān)聯(lián)矩陣。,.,15,3、關(guān)聯(lián)矩陣(4),從有向圖的完全關(guān)聯(lián)矩陣可得出圖的有關(guān)信息：(1)每邊關(guān)聯(lián)一個始點(diǎn)，一個終點(diǎn)。故每列只有一個元素為1，一個元素為-1，其余為0。(2)每行的1之和即相應(yīng)結(jié)點(diǎn)的出度，-1之和即相應(yīng)結(jié)點(diǎn)的入度。(3)若某行各元素皆為0，則相應(yīng)結(jié)點(diǎn)為孤立結(jié)點(diǎn)。(4)平行邊所對應(yīng)的列完全相同。,.,16,3、關(guān)聯(lián)矩陣(5),定理2設(shè)連通圖G有r個結(jié)點(diǎn)，則其完全關(guān)聯(lián)矩陣的秩為r-1。(證明從略),兩個關(guān)于關(guān)聯(lián)矩陣的秩的結(jié)論：,推論設(shè)圖G有r個結(jié)點(diǎn)，w個最大連通子圖，則圖G的完全關(guān)聯(lián)矩陣的秩為r-w。,注：(1)矩陣中的任意k階方陣的行列式該矩陣的k階子式。(2)矩陣A中不為0的子式的最大階數(shù)r叫A的秩。(3)交換矩陣中兩行或兩列；用非零數(shù)乘矩陣的某行或某列；用非零數(shù)乘矩陣的某行或某列后再加到另一行或列的對應(yīng)元素上。以上三種變換叫矩陣的初等變換。初等變換不改變矩陣的秩。,.,17,4、課堂練習(xí),練習(xí)求如下有