圖的矩陣表示計(jì)算機(jī)科學(xué)領(lǐng)域有許多算法涉及圖。計(jì)算機(jī)存儲(chǔ)圖的一種最簡(jiǎn)單有效的方法就是矩陣。矩陣是由數(shù)字組成的矩陣表格，一般用大寫字母表示。（元素、行、列）。圖論有效地利用了矩陣，將其作為表達(dá)圖及其性質(zhì)的有效工具和手段。

定義10.18設(shè)G＝(V,E)為簡(jiǎn)單圖，它有n個(gè)結(jié)點(diǎn)V＝{v1,v2,…,vn}，，則n階方陣稱為G的鄰接矩陣。其中v2v4v5v3v1v2v4v5v3v1無(wú)向圖有向圖

如果給定的圖是零圖，則其對(duì)應(yīng)的矩陣中所有的元素都為零，它是一個(gè)零矩陣，反之亦然，即鄰接矩陣為零矩陣的圖必是零圖。v1v2v4v3G1v2v1v4v3G2用圖形表示圖的方法，關(guān)于結(jié)點(diǎn)間的通路很容易在圖形中看出來(lái)，但在鄰接矩陣中就需經(jīng)過(guò)計(jì)算。設(shè)有向圖G的結(jié)點(diǎn)集V＝{v1,v2,…,vn}，它的鄰接矩陣為：A(G)＝(aij)n×n，現(xiàn)在我們來(lái)計(jì)算從結(jié)點(diǎn)vi

到結(jié)點(diǎn)vj

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

到結(jié)點(diǎn)vj

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

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

到結(jié)點(diǎn)vj

的長(zhǎng)度為2的路的數(shù)目等于：按照矩陣的乘法規(guī)則，這恰好是矩陣中的第i行，第j列的元素。表示從結(jié)點(diǎn)vi

到結(jié)點(diǎn)vj

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

到結(jié)點(diǎn)vi

的長(zhǎng)度為2的回路的數(shù)目。從結(jié)點(diǎn)vi

到結(jié)點(diǎn)vj

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

到結(jié)點(diǎn)vk

的長(zhǎng)度為1的路，和從結(jié)點(diǎn)vk

到結(jié)點(diǎn)vj

的長(zhǎng)度為2的路，故從結(jié)點(diǎn)vi

到結(jié)點(diǎn)vj的一條長(zhǎng)度為3的路的數(shù)目：即：一般地有上述這個(gè)結(jié)論對(duì)無(wú)向圖也成立。定理10.10設(shè)A(G)為圖G的鄰接矩陣，則(A(G))l中的i行j列元素等于G中連接結(jié)點(diǎn)vi與vj的長(zhǎng)度為l的路的數(shù)目。證明：歸納法證明。(1)當(dāng)l＝2時(shí)，由上得知是顯然成立。(2)設(shè)命題對(duì)l成立，由

故根據(jù)鄰接矩陣的定義aik表示連接vi與vk長(zhǎng)度為1的路的數(shù)目，而是連接vk與vj長(zhǎng)度為l的路的數(shù)目，式中每一項(xiàng)表示由vi經(jīng)過(guò)一條邊到vk，再由vk經(jīng)過(guò)長(zhǎng)度為l的路到vj的，總長(zhǎng)度為l

1的路的數(shù)目。對(duì)所有的k求和，即是所有從vi到v的長(zhǎng)度為l

1的路的數(shù)目，故命題對(duì)成立?！纠?0.6】給定一圖G＝(V,E)如下圖所示。v3v1v2v4v5解：從矩陣中可以看到，v1與v2之間有兩條長(zhǎng)度為3的路，結(jié)點(diǎn)v1與v3之間有一條長(zhǎng)度為2的路，在結(jié)點(diǎn)v2有四條長(zhǎng)度為4的回路。在許多問(wèn)題中需要判斷有向圖的一個(gè)結(jié)點(diǎn)vi到另一個(gè)結(jié)點(diǎn)vj是否存在路的問(wèn)題。如果利用圖G的鄰接矩陣A，則可計(jì)算A，A2，A3，…，An，…，當(dāng)發(fā)現(xiàn)其中的某個(gè)Al的aij(l)≥1，就表明結(jié)點(diǎn)vi到vj可達(dá)。但這種計(jì)算比較繁瑣，且Al不知計(jì)算到何時(shí)為止。從前面得知，如果有向圖G有n個(gè)結(jié)點(diǎn) V＝{v1,v2,…,vn} vi到vj有一條路，則必有一條長(zhǎng)度不超過(guò)n的通路，因此只要考察aij(l)就可以了，其中1≤l≤n。對(duì)于有向圖G中任意兩個(gè)結(jié)點(diǎn)之間的可達(dá)性，亦可用可達(dá)矩陣。 定義10.19令G＝<V,E>是一個(gè)簡(jiǎn)單有向圖，，假定V

的結(jié)點(diǎn)已編序，即V＝{v1,v2,…,vn}，定義一個(gè)n×n矩陣。其中稱矩陣P是圖G的可達(dá)性矩陣。 可達(dá)性矩陣表明了圖中任意兩個(gè)結(jié)點(diǎn)間是否至少存在一條路以及在任何結(jié)點(diǎn)上是否存在回路。一般地可由圖G的鄰接矩陣A得到可達(dá)性矩陣P。即令Bn＝A

A2

…

An，在從Bn

中將不為0的元素改為1，而為零的元素不變，這樣改換的矩陣即為可達(dá)性矩陣P。 Warshall算法可以由鄰接矩陣求可達(dá)性矩陣P?！纠?0.7】求下圖的可達(dá)性矩陣。p2p1p3p5p4解：同理可證：由此看出，如果把鄰接矩陣看作是結(jié)點(diǎn)集V上關(guān)系R的關(guān)系矩陣，則可達(dá)性矩陣P即為，因此可達(dá)矩陣亦可用Warshall算法計(jì)算?？蛇_(dá)性矩陣的概念可以推廣到無(wú)向圖中，只要將無(wú)向圖的每一條邊看成是具有相反方向的兩條邊，這樣，一個(gè)無(wú)向圖就可以看成是有向圖。無(wú)向圖的鄰接矩陣是一個(gè)對(duì)稱矩陣，其可達(dá)矩陣稱為連通矩陣。對(duì)于一個(gè)無(wú)向圖G，除了可用鄰接矩陣以外，還對(duì)應(yīng)著一個(gè)稱為圖G的完全關(guān)聯(lián)矩陣，假定圖G無(wú)自回路，如因某種運(yùn)算得到自回路，則將它刪去。定義10.20給定無(wú)向圖G，令v1,v2,…,vp

和e1,e2,…,eq

分別記為G的結(jié)點(diǎn)和邊，則矩陣M(G)＝(mij)，其中稱M(G)為完全關(guān)聯(lián)矩陣。無(wú)向圖及其完全關(guān)聯(lián)矩陣v2v1e3e4e2e1e1e2e3e4v11101v21110V30011v3從關(guān)聯(lián)矩陣中可以看出圖形的一些性質(zhì)： （1）圖中每一邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)，故M(G)的每一列只有兩個(gè)1。 （2）每一行元素的和數(shù)對(duì)應(yīng)于結(jié)點(diǎn)的度數(shù)。 （3）一行中的元素全為0，其對(duì)應(yīng)的結(jié)點(diǎn)為孤立點(diǎn)。 （4）兩個(gè)平行邊其對(duì)應(yīng)的兩列相同。 （5）同一圖當(dāng)結(jié)點(diǎn)或邊的編序不同，其對(duì)應(yīng)M(G)僅有行序、列序的差別。 當(dāng)一個(gè)圖是有向圖時(shí)，亦可用結(jié)點(diǎn)和邊的關(guān)聯(lián)矩陣來(lái)表示。定義10.21給定簡(jiǎn)單有向圖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簡(jiǎn)單有向圖及其完全關(guān)聯(lián)矩陣 有向圖的完全關(guān)聯(lián)矩陣也有類于無(wú)向圖的一些性質(zhì)。定義10.22對(duì)圖G的完全關(guān)聯(lián)矩陣中的兩行相加