資源描述：
《圖的矩陣表示及習題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、圖的矩陣表示圖是用三重組定義的，可以用圖形表示。此外，還可以用矩陣表示。使用矩陣表示圖，有利于用代數(shù)的方法研究圖的性質(zhì)，也有利于使用計算機對圖進行處理。矩陣是研究圖的重要工具之一。本節(jié)主要討論無向圖和有向圖的鄰接矩陣、有向圖的可達性矩陣、無向圖的連通矩陣、無向圖和有向圖的完全關聯(lián)矩陣。定義9.4.1設G=是一個簡單圖，V=ív1,v2,…,vnyA(G)=()n×n其中：i,j=1,…,n稱A(G)為G的鄰接矩陣。簡記為A。例如圖9.22的鄰接矩陣為：又如圖9.23(a)的鄰接矩陣為：由定義和以
2、上兩個例子容易看出鄰接矩陣具有以下性質(zhì)：①鄰接矩陣的元素全是0或1。這樣的矩陣叫布爾矩陣。鄰接矩陣是布爾矩陣。②無向圖的鄰接矩陣是對稱陣，有向圖的鄰接矩陣不一定是對稱陣。184③鄰接矩陣與結(jié)點在圖中標定次序有關。例如圖9.23(a)的鄰接矩陣是A(G)，若將圖9.23(a)中的接點v1和v2的標定次序調(diào)換，得到圖9.23(b)，圖9.23(b)的鄰接矩陣是A′(G)。考察A(G)和A′(G)發(fā)現(xiàn)，先將A(G)的第一行與第二行對調(diào)，再將第一列與第二列對調(diào)可得到A′(G)。稱A′(G)與A(G)是置換等價的。
3、一般地說，把n階方陣A的某些行對調(diào)，再把相應的列做同樣的對調(diào)，得到一個新的n階方陣A′，則稱A′與A是置換等價的。可以證明置換等價是n階布爾方陣集合上的等價關系。雖然，對于同一個圖，由于結(jié)點的標定次序不同，而得到不同的鄰接矩陣，但是這些鄰接矩陣是置換等價的。今后略去結(jié)點標定次序的任意性，取任意一個鄰接矩陣表示該圖。④對有向圖來說，鄰接矩陣A(G)的第i行1的個數(shù)是vi的出度，第j列1的個數(shù)是vj的入度。⑤零圖的鄰接矩陣的元素全為零，叫做零矩陣。反過來，如果一個圖的鄰接矩陣是零矩陣，則此圖一定是零圖。設G=
4、為有向圖，V=ív1,v2,…,vny，鄰接矩陣為A=(aij)n×n若aij=1，由鄰接矩陣的定義知，vi到vj有一條邊，即vi到vj有一條長度為1的路；若aij=0，則vi到vj無邊，即vi到vj無長度為1的路。故aij表示從vi到vj長度為1的路的條數(shù)。設A2=AA，A2=()n×n，按照矩陣乘法的定義，若aikakj=1，則aik=1且akj=1，vi到vk有邊且vk到vj有邊，從而vi到vj通過vk有一條長度為2的路；若=0，則aik=0或akj=0，vi到vk無邊或vk到vj無邊，因
5、而vi到vj通過vk無長度為2的路，k=1,…,n。故表示從vi到vj長度為2的路的條數(shù)。設A3=AA2，A3=()n×n，按照矩陣乘法的定義，若≠0，則=1且≠0，vi到vk有邊且vk到vj有路，由于是vk到vj長度為2的路的條數(shù)，因而表示vi到vj通過vk長度為3的路的條數(shù)；若=0,=0或=0，則vi到vk無邊或vk到vj無長度為2的路，所以vi到vj通過vk無路，k=1,…,n。故表示從vi到vj長度為3的路的條數(shù)。……可以證明，這個結(jié)論對無向圖也成立。因此有下列定理成立。定理9.4.1設A(G)是
6、圖G的鄰接矩陣，A(G)k=A(G)A(G)k-1，A(G)k的第i行，第j列元素等于從vi到vj長度為k的路的條數(shù)。其中為vi到自身長度為k的回路數(shù)。推論設G=是n階簡單有向圖，A是有向圖G的鄰接矩陣，Bk=A＋A2＋…＋Ak，184Bk=()n×n，則是G中由vi到vj長度小于等于k的路的條數(shù)。是G中長度小于等于k的路的總條數(shù)。是G中長度小于等于k的回路數(shù)?！纠?.4】設G=為簡單有向圖，圖形如圖9.24，寫出G的鄰接矩陣A，算出A2，A3，A4且確定v1到v2有多少條長度為3的路
7、?v1到v3有多少條長度為2的路?v2到自身長度為3和長度為4的回路各多少條?解：鄰接矩陣A和A2，A3，A4如下：=2，所以v1到v2長度為3的路有2條，它們分別是：v1v2v1v2和v1v2v3v2。=1，所以v1到v3長度為2的路有1條：v1v2v3。=0，v2到自身無長度為3的回路。=4，v2到自身有4條長度為4的回路，它們分別是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v3v2。定義9.4.2設G=是簡單有向圖，V=ív1,v2,…,vnyP(G)
8、=(pij)n×n其中：pij=i,j=1,…,n稱P(G)為G的可達性矩陣。簡記為P。在定義9.3.10中，規(guī)定了有向圖的任何結(jié)點自己和自己可達。所以可達性矩陣P(G)的主對角線元素全為1。設G=是n階簡單有向圖，V=ív1,v2,…,vny，由可達性矩陣的定義知，當i≠j時，如果vi到vj有路，則=1；如果vi到vj無路，則=0；又由定理9.2.1知，如果vi到vj有路，則必存在長度小于等于n–1的路。依據(jù)定理9
