圖的矩陣表示及習(xí)題-答案

1、圖的矩陣表示圖是用三重組定義的，可以用圖形表示。此外，還可以用矩陣表示。使用矩陣表示圖，有利于用代數(shù)的方法研究圖的性質(zhì)，也有利于使用計(jì)算機(jī)對(duì)圖進(jìn)行處理。矩陣是研究圖的重要工具之一。本節(jié)主要討論無(wú)向圖和有向圖的鄰接矩陣、有向圖的可達(dá)性矩陣、無(wú)向圖的連通矩陣、無(wú)向圖和有向圖的完全關(guān)聯(lián)矩陣。定義9.4.1 設(shè) G=V,E是一個(gè)簡(jiǎn)單圖，V=v1,v2,vnA(G=( n×n其中：i,j=1,n稱A(G為G的鄰接矩陣。簡(jiǎn)記為A。例如圖9.22的鄰接矩陣為：又如圖9.23(a的鄰接矩陣為：由定義和以上兩個(gè)例子容易看出鄰接矩陣具有以下性質(zhì)：鄰接矩陣的元素全是0或1。這樣的矩陣叫布爾矩陣。鄰接矩陣是

2、布爾矩陣。無(wú)向圖的鄰接矩陣是對(duì)稱陣，有向圖的鄰接矩陣不一定是對(duì)稱陣。鄰接矩陣與結(jié)點(diǎn)在圖中標(biāo)定次序有關(guān)。例如圖9.23(a的鄰接矩陣是A(G，若將圖9.23(a中的接點(diǎn)v1和v2的標(biāo)定次序調(diào)換，得到圖9.23(b，圖9.23(b的鄰接矩陣是A(G?？疾霢(G和A(G發(fā)現(xiàn)，先將A(G的第一行與第二行對(duì)調(diào)，再將第一列與第二列對(duì)調(diào)可得到A(G。稱A(G與A(G是置換等價(jià)的。一般地說(shuō)，把n階方陣A的某些行對(duì)調(diào)，再把相應(yīng)的列做同樣的對(duì)調(diào)，得到一個(gè)新的n階方陣A，則稱A與A是置換等價(jià)的。可以證明置換等價(jià)是n階布爾方陣集合上的等價(jià)關(guān)系。雖然，對(duì)于同一個(gè)圖，由于結(jié)點(diǎn)的標(biāo)定次序不同，而得到不同的鄰接矩陣，但是這些

3、鄰接矩陣是置換等價(jià)的。今后略去結(jié)點(diǎn)標(biāo)定次序的任意性，取任意一個(gè)鄰接矩陣表示該圖。對(duì)有向圖來(lái)說(shuō)，鄰接矩陣A(G的第i行1的個(gè)數(shù)是vi的出度， 第j列1的個(gè)數(shù)是vj的入度。零圖的鄰接矩陣的元素全為零，叫做零矩陣。反過(guò)來(lái)，如果一個(gè)圖的鄰接矩陣是零矩陣，則此圖一定是零圖。設(shè)G=V,E為有向圖，V=v1,v2,vn，鄰接矩陣為A=(aijn×n若aij=1，由鄰接矩陣的定義知，vi到vj有一條邊，即vi到vj有一條長(zhǎng)度為1的路；若aij=0，則vi到vj無(wú)邊，即vi到vj無(wú)長(zhǎng)度為1的路。故aij表示從vi到vj長(zhǎng)度為1的路的條數(shù)。設(shè)A2=AA，A2=(n×n，按照矩陣乘法的定義，若a

4、ikakj=1，則aik=1且akj=1，vi到vk有邊且vk到vj有邊，從而vi到vj通過(guò)vk有一條長(zhǎng)度為2的路；若 =0，則aik=0或akj=0，vi到vk無(wú)邊或vk到vj無(wú)邊，因而vi到vj通過(guò)vk無(wú)長(zhǎng)度為2的路，k=1,n。故表示從vi到vj長(zhǎng)度為2的路的條數(shù)。設(shè)A3=AA2，A3=( n×n，按照矩陣乘法的定義， 若0，則=1且0，vi到vk有邊且vk到vj有路，由于是vk到vj長(zhǎng)度為2的路的條數(shù)，因而表示vi到vj通過(guò)vk長(zhǎng)度為3的路的條數(shù)；若=0, =0或=0，則vi到vk無(wú)邊或vk到vj無(wú)長(zhǎng)度為2的路，所以vi到vj通過(guò)vk無(wú)路，k=1,n。故表示從vi到vj長(zhǎng)度為

5、3的路的條數(shù)?？梢宰C明，這個(gè)結(jié)論對(duì)無(wú)向圖也成立。因此有下列定理成立。定理9.4.1 設(shè)A(G是圖G的鄰接矩陣，A(Gk=A(GA(Gk-1，A(Gk的第i行，第j列元素等于從vi到vj長(zhǎng)度為k的路的條數(shù)。其中為vi到自身長(zhǎng)度為k的回路數(shù)。推論 設(shè)G=V,E是n階簡(jiǎn)單有向圖，A是有向圖G的鄰接矩陣，Bk=AA2Ak，Bk=(n×n，則是G中由vi到vj長(zhǎng)度小于等于k的路的條數(shù)。是G中長(zhǎng)度小于等于k的路的總條數(shù)。是G中長(zhǎng)度小于等于k的回路數(shù)?！纠?.4】 設(shè)G=V,E為簡(jiǎn)單有向圖，圖形如圖9.24，寫出G的鄰接矩陣A，算出A2，A3，A4且確定v1到v2有多少條長(zhǎng)度為3的路? v1到v3

6、有多少條長(zhǎng)度為2的路? v2到自身長(zhǎng)度為3和長(zhǎng)度為4的回路各多少條?解：鄰接矩陣A和A2，A3，A4如下： =2，所以v1到v2長(zhǎng)度為3的路有2條，它們分別是：v1v2v1v2和v1v2v3v2。=1，所以v1到v3長(zhǎng)度為2的路有1條：v1v2v3。=0，v2到自身無(wú)長(zhǎng)度為3的回路。=4，v2到自身有4條長(zhǎng)度為4的回路，它們分別是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v3v2。定義9.4.2 設(shè)G=V,E是簡(jiǎn)單有向圖，V=v1,v2,vnP(G=(pijn×n其中：pij =i,j=1,n稱P(G為G的可達(dá)性矩陣。簡(jiǎn)記為P。在定義9.3.10

7、中，規(guī)定了有向圖的任何結(jié)點(diǎn)自己和自己可達(dá)。所以可達(dá)性矩陣P(G的主對(duì)角線元素全為1。設(shè)G=V,E是n階簡(jiǎn)單有向圖，V=v1,v2,vn，由可達(dá)性矩陣的定義知，當(dāng)ij時(shí)，如果vi到vj有路，則=1；如果vi到vj無(wú)路，則=0；又由定理9.2.1知，如果vi到vj有路，則必存在長(zhǎng)度小于等于n1的路。依據(jù)定理9.4.1的推論，如下計(jì)算圖G的可達(dá)性矩陣P：先計(jì)算Bn1=AA2An1，設(shè)Bn1=(n×n。若0，則令=1，若=0，則令pij =0，i,j=1,n。再令pii=1，i=1,n。就得到了圖G的可達(dá)性矩陣P。令A(yù)0為n階單位陣，則上述算法也可以改進(jìn)為： 計(jì)算Cn1= A0Bn1=A0A

8、A2An-1，設(shè)Cn1=(n×n。若0，則令=1，若=0，則令=0，i,j=1,n。使用上述方法，計(jì)算例9.4中圖G的可達(dá)性矩陣，C4= A0AA2A3A4= P=計(jì)算簡(jiǎn)單有向圖圖G的可達(dá)性矩陣P，還可以用下述方法：設(shè)A是G的鄰接矩陣，令A(yù) =(n×n，A(k =(n×n，A0為n階單位陣。A(2 = AA， 其中=(ai1a1j(ai2a2j(ainanj i,j=1,n。A(3 = AA(2，其中(ai1(ai2(ain i,j=1,n。P= A0AA(2A(3A(n1。 其中，運(yùn)算是矩陣對(duì)應(yīng)元素的析取。可達(dá)性矩陣用來(lái)描述有向圖的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路，

9、即是否可達(dá)。無(wú)向圖也可以用矩陣描述一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路。在無(wú)向圖中，如果結(jié)點(diǎn)之間有路，稱這兩個(gè)結(jié)點(diǎn)連通，不叫可達(dá)。所以把描述一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路的矩陣叫連通矩陣，而不叫可達(dá)性矩陣。下面是無(wú)向圖連通矩陣的定義。定義9.4.3 設(shè)G=V,E是簡(jiǎn)單無(wú)向圖，V=v1,v2,vnP(G=( pij n×n其中：i,j=1,n稱P(G為G的連通矩陣。簡(jiǎn)記為P。無(wú)向圖的鄰接矩陣是對(duì)稱陣，無(wú)向圖的連通矩陣也是對(duì)稱陣。求連通矩陣的方法與可達(dá)性矩陣類似。定義9.4.4 設(shè)G=V,E是無(wú)向圖，V=v1,v2,vp，E=e1,e2,eqM(G=( mij p×q其中： i=1,p，

10、j=1,q稱M(G為無(wú)向圖G的完全關(guān)聯(lián)矩陣。簡(jiǎn)記為M。例如圖9.25的完全關(guān)聯(lián)矩陣為：M(G=設(shè)G=V,E是無(wú)向圖，G的完全關(guān)聯(lián)矩陣M(G有以下的性質(zhì)：每列元素之和均為2。這說(shuō)明每條邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)。每行元素之和是對(duì)應(yīng)結(jié)點(diǎn)的度數(shù)。所有元素之和是圖中各結(jié)點(diǎn)度數(shù)的總和，也是邊數(shù)的2倍。兩列相同，則對(duì)應(yīng)的兩個(gè)邊是平行邊。某行元素全為零，則對(duì)應(yīng)結(jié)點(diǎn)為孤立點(diǎn)。定義9.4.5 設(shè)G=V,E是有向圖，V=v1,v2,vp，E=e1,e2,eqM(G=( mij p×q其中： i=1,p，j=1,q稱M(G為有向圖G的完全關(guān)聯(lián)矩陣。簡(jiǎn)記為M。圖9.26的完全關(guān)聯(lián)矩陣為：M(G=設(shè)G=V,E是有向圖，G

11、的完全關(guān)聯(lián)矩陣M(G有以下的性質(zhì)：每列有一個(gè)1和一個(gè)-1，這說(shuō)明每條有向邊有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)。每行1的個(gè)數(shù)是對(duì)應(yīng)結(jié)點(diǎn)的出度，-1的個(gè)數(shù)是對(duì)應(yīng)結(jié)點(diǎn)的入度。所有元素之和是0，這說(shuō)明所有結(jié)點(diǎn)出度的和等于所有結(jié)點(diǎn)入度的和。兩列相同，則對(duì)應(yīng)的兩邊是平行邊。習(xí) 題 9.41.設(shè)G=V,E是一個(gè)簡(jiǎn)單有向圖，V=v1, v2, v3, v4，鄰接矩陣如下： A(G= 求v1的出度deg(v1。 求v4的入度deg(v4。 由v1到v4長(zhǎng)度為2的路有幾條？解：（1）deg(v1=1；（2）deg(v4=2；（3），所以由v1到v4長(zhǎng)度為2的路有1條。2.有向圖G如圖9.27所示。 寫出G的鄰接矩陣。 根據(jù)鄰接

12、矩陣求各結(jié)點(diǎn)的出度和入度。 求G中長(zhǎng)度為3的路的總數(shù)，其中有多少條回路。 求G的可達(dá)性矩陣。 求G的完全關(guān)聯(lián)矩陣。 由完全關(guān)聯(lián)矩陣求各結(jié)點(diǎn)的出度和入度。解：（1）;（2）deg(v1=2；deg(v2=1；deg(v3=2；deg(v4=0；deg(v1=1；deg(v2=2；deg(v3=1；deg(v4=1；（3），所以G中長(zhǎng)度為3的路的總數(shù)是8條，其中有3條回路；（4）=所以G的可達(dá)性矩陣為；（5）G的完全關(guān)聯(lián)矩陣為（6）deg(v1=2；deg(v2=1；deg(v3=2；deg(v4=0；deg(v1=1；deg(v2=2；deg(v3=1；deg(v4=1。3.無(wú)向圖G如圖9.28

13、所示。 寫出G的鄰接矩陣。 根據(jù)鄰接矩陣求各結(jié)點(diǎn)的度數(shù)。 求G中長(zhǎng)度為3的路的總數(shù)，其中有多少條回路。 求G的連通矩陣。 求G的完全關(guān)聯(lián)矩陣。 由完全關(guān)聯(lián)矩陣求各結(jié)點(diǎn)的度數(shù)。(1；（2）deg(v1=3；deg(v2=3；deg(v3=2；deg(v4=3；（3），所以G中長(zhǎng)度為3的路共有66條，有12條回路；（4）=所以G的連通矩陣為；（5）G的完全關(guān)聯(lián)矩陣為（6）deg(v1=3；deg(v2=3；deg(v3=2；deg(v4=3。4.設(shè)G=V,E是一個(gè)簡(jiǎn)單有向圖，V=v1, v2, vn， P=(pijn×n是圖G的可達(dá)性矩陣， PT=(n×n是P的轉(zhuǎn)置矩陣。易知， pij1表示vi到vj是可達(dá)的；pji1表示vj到