圖的矩陣表示

圖的矩陣表示第1頁，課件共26頁，創(chuàng)作于2023年2月 定義1設(shè)G＝(V,E)為簡單圖，它有n個結(jié)點V＝{v1,v2,…,vn}，，則n階方陣稱為G的鄰接矩陣。其中v2v4v5v3v1v2v4v5v3v1無向圖第2頁，課件共26頁，創(chuàng)作于2023年2月有向圖

如果給定的圖是零圖，則其對應(yīng)的矩陣中所有的元素都為零，它是一個零矩陣，反之亦然，即鄰接矩陣為零矩陣的圖必是零圖。v1v2v4v3G1v2v1v4v3G2第3頁，課件共26頁，創(chuàng)作于2023年2月用圖形表示圖的方法，關(guān)于結(jié)點間的通路很容易在圖形中看出來，但在鄰接矩陣中就需經(jīng)過計算。設(shè)有向圖G的結(jié)點集V＝{v1,v2,…,vn}，它的鄰接矩陣為：

A(G)＝(aij)n×n，現(xiàn)在我們來計算從結(jié)點vi

到結(jié)點vj

的長度為2的路的數(shù)目。注意到每條從結(jié)點vi

到結(jié)點vj

的長度為2的路的中間必經(jīng)過一個結(jié)點vk，即vi→vk→vj(1≤k≤n)，如果圖中有路vivkvj

存在，那么aik＝akj＝1，即aik·akj＝1，反之如果圖G中不存在路vivkvj，那么aik＝0或akj＝0，即aik·akj＝0，于是從結(jié)點vi

到結(jié)點vj

的長度為2的路的數(shù)目等于：第4頁，課件共26頁，創(chuàng)作于2023年2月按照矩陣的乘法規(guī)則，這恰好是矩陣中的第i行，第j列的元素。表示從結(jié)點vi

到結(jié)點vj

的長度為2的路的數(shù)目。表示從結(jié)點vi

到結(jié)點vi

的長度為2的回路的數(shù)目。第5頁，課件共26頁，創(chuàng)作于2023年2月從結(jié)點vi

到結(jié)點vj

的一條長度為3的路，可以看作從結(jié)點vi

到結(jié)點vk

的長度為1的路，和從結(jié)點vk

到結(jié)點vj

的長度為2的路，故從結(jié)點vi

到結(jié)點vj的一條長度為3的路的數(shù)目：即：第6頁，課件共26頁，創(chuàng)作于2023年2月一般地有上述這個結(jié)論對無向圖也成立。第7頁，課件共26頁，創(chuàng)作于2023年2月定理2設(shè)A(G)為圖G的鄰接矩陣，則(A(G))l

中的i行j列元素等于G中連接結(jié)點vi

與vj

的長度為l的路的數(shù)目。證明：歸納法證明。

(1)當(dāng)l＝2時，由上得知是顯然成立。

(2)設(shè)命題對l成立，由

故第8頁，課件共26頁，創(chuàng)作于2023年2月根據(jù)鄰接矩陣的定義aik

表示連接vi

與vk

長度為1的路的數(shù)目，而是連接vk

與vj

長度為l的路的數(shù)目，式中每一項表示由vi

經(jīng)過一條邊到vk，再由vk

經(jīng)過長度為l的路到vj

的，總長度為l1的路的數(shù)目。對所有的k求和，即是所有從vi

到v的長度為l1的路的數(shù)目，故命題對成立。第9頁，課件共26頁，創(chuàng)作于2023年2月【例3】給定一圖G＝(V,E)如下圖所示。v3v1v2v4v5解：從矩陣中可以看到，v1

與v2

之間有兩條長度為3的路，結(jié)點v1

與v3

之間有一條長度為2的路，在結(jié)點v2

有四條長度為4的回路。第10頁，課件共26頁，創(chuàng)作于2023年2月在許多問題中需要判斷有向圖的一個結(jié)點vi

到另一個結(jié)點vj

是否存在路的問題。如果利用圖G的鄰接矩陣A，則可計算A，A2，A3，…，An，…，當(dāng)發(fā)現(xiàn)其中的某個Al

的aij(l)≥1，就表明結(jié)點vi

到vj

可達。但這種計算比較繁瑣，且Al

不知計算到何時為止。從前面得知，如果有向圖G有n個結(jié)點

V＝{v1,v2,…,vn} vi

到vj

有一條路，則必有一條長度不超過n的通路，因此只要考察aij(l)

就可以了，其中1≤l≤n。對于有向圖G中任意兩個結(jié)點之間的可達性，亦可用可達矩陣。第11頁，課件共26頁，創(chuàng)作于2023年2月 定義4令G＝<V,E>是一個簡單有向圖，，假定V

的結(jié)點已編序，即V＝{v1,v2,…,vn}，定義一個n×n矩陣。其中

稱矩陣P是圖G的可達性矩陣。第12頁，課件共26頁，創(chuàng)作于2023年2月 可達性矩陣表明了圖中任意兩個結(jié)點間是否至少存在一條路以及在任何結(jié)點上是否存在回路。一般地可由圖G的鄰接矩陣A得到可達性矩陣P。即令Bn＝AA2…An，在從Bn

中將不為0的元素改為1，而為零的元素不變，這樣改換的矩陣即為可達性矩陣P。

Warshall算法可以由鄰接矩陣求可達性矩陣P。第13頁，課件共26頁，創(chuàng)作于2023年2月【例5】求下圖的可達性矩陣。p2p1p3p5p4解：第14頁，課件共26頁，創(chuàng)作于2023年2月同理可得：

第15頁，課件共26頁，創(chuàng)作于2023年2月可達性矩陣的概念可以推廣到無向圖中，只要將無向圖的每一條邊看成是具有相反方向的兩條邊，這樣，一個無向圖就可以看成是有向圖。無向圖的鄰接矩陣是一個對稱矩陣，其可達矩陣稱為連通矩陣。對于一個無向圖G，除了可用鄰接矩陣以外，還對應(yīng)著一個稱為圖G的完全關(guān)聯(lián)矩陣，假定圖G無自回路，如因某種運算得到自回路，則將它刪去。第16頁，課件共26頁，創(chuàng)作于2023年2月定義6給定無向圖G，令v1,v2,…,vp

和e1,e2,…,eq

分別記為G的結(jié)點和邊，則矩陣M(G)＝(mij)，其中稱M(G)為完全關(guān)聯(lián)矩陣。無向圖及其完全關(guān)聯(lián)矩陣v2v1e3e4e2e1e1e2e3e4v11101v21110V30011v3第17頁，課件共26頁，創(chuàng)作于2023年2月從關(guān)聯(lián)矩陣中可以看出圖形的一些性質(zhì)： （1）圖中每一邊關(guān)聯(lián)兩個結(jié)點，故M(G)的每一列只有兩個1。 （2）每一行元素的和數(shù)對應(yīng)于結(jié)點的度數(shù)。 （3）一行中的元素全為0，其對應(yīng)的結(jié)點為孤立點。 （4）兩個平行邊其對應(yīng)的兩列相同。 （5）同一圖當(dāng)結(jié)點或邊的編序不同，其對應(yīng)M(G)僅有行序、列序的差別。 當(dāng)一個圖是有向圖時，亦可用結(jié)點和邊的關(guān)聯(lián)矩陣來表示。第18頁，課件共26頁，創(chuàng)作于2023年2月定義7給定簡單有向圖G＝<V,E>，V＝{v1,v2,…,vp}，E＝{e1,e2,…,eq}，p×q階矩陣M(G)＝(mij)，其中稱M(G)為G的關(guān)聯(lián)矩陣。v2v1e3e4e2e1v3v4e5e1e2e3e4e5v110101v2-11000v30-1-110v4000-1-1簡單有向圖及其完全關(guān)聯(lián)矩陣第19頁，課件共26頁，創(chuàng)作于2023年2月 有向圖的完全關(guān)聯(lián)矩陣也有類于無向圖的一些性質(zhì)。定義8對圖G的完全關(guān)聯(lián)矩陣中的兩行相加如下：若記vi

對應(yīng)的行為，將第i行與第j行相加，規(guī)定為：對有向圖是指對應(yīng)分量的加法運算，對無向圖是指對應(yīng)分量的模2

的加法運算，把這種運算記作。執(zhí)行這個運算實際上是對應(yīng)于把圖G的結(jié)點vi

與結(jié)點vj

合并。

第20頁，課件共26頁，創(chuàng)作于2023年2月

設(shè)圖G的結(jié)點vi

與結(jié)點vj

合并得到圖G′，那么M(G’)是將M(G)中的第i行與第j行相加而得到。因為若有關(guān)項中第r個對應(yīng)分量有，則說明vi

與vj

兩者之中只有一個結(jié)點是邊er

的端點，且將這兩個結(jié)點合并后的結(jié)點vi,j

仍是er

的端點。

第21頁，課件共26頁，創(chuàng)作于2023年2月若則有兩種情況：（1）vi

與vj

都不是邊er

的端點，那么vi,j

也不是er

的端點。（2）vi

與vj

都是邊er

的端點，那么合并后在G′中er成為vi,j

的自回路，按規(guī)則應(yīng)該被刪去。此外，在M(G’)中若有某些列，其元素全為0，說明G中的一些結(jié)點合并后，消失了一些對應(yīng)邊。第22頁，課件共26頁，創(chuàng)作于2023年2月【例9】無向圖(a)中結(jié)點v4

和v5

合并得到圖(b)。解：其關(guān)聯(lián)矩陣M(G’)是由關(guān)聯(lián)矩陣M(G)中將第4行加到第5行而得到。e1e2e3e4e5e6e7v10000011v20001110v30111000v41100000v51010101v2v1e3e4e2e1v3v4e5v5e7e6v2v1e3e4e2v3e5V4,5e7e6e1e2e3e4e5e6e7v10000011v20001110v30111000V4,50110101（a）（b）第23頁，課件共26頁，創(chuàng)作于2023年2月【例10】有向圖(a)中合并結(jié)點v2

和v3。解：合并時，刪去自回路得圖(b)。其關(guān)聯(lián)矩陣M(G’)是由M(G)中將第2行加到第3行上面得到的。e1e2e3e4e5e6E7e8e9v1110000000v2-101000100v300-11000-11v40-10001-110v500001-100-1v6000-1-10000v1e9e4e2e1v2,3v4e5v5e7e6v6e8v2v1e9e4e2