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