第七章 圖的基本概念

第七章圖的基本概念3第一頁，共三十頁，2022年，8月28日7.3圖的矩陣表示給定一個圖G=<V，E>，使用圖形表示法很容易把圖的結(jié)構(gòu)展現(xiàn)出來，而且這種表示直觀明了。但這只在結(jié)點和邊(或弧)的數(shù)目相當小的情況下才是可行的。顯然這限制了圖的利用。本節(jié)提供另一種圖的表示法——圖的矩陣表示法。它不僅克服了圖形表示法的不足，而且這種表示可以充分利用現(xiàn)代工具電子計算機，以達到研究圖的目的。第二頁，共三十頁，2022年，8月28日無向圖的關(guān)聯(lián)矩陣注：自環(huán)取2。第三頁，共三十頁，2022年，8月28日第四頁，共三十頁，2022年，8月28日性質(zhì)：若第j列與第k列相同，則ej與ek為平行邊第五頁，共三十頁，2022年，8月28日有向圖的關(guān)聯(lián)矩陣第六頁，共三十頁，2022年，8月28日第七頁，共三十頁，2022年，8月28日性質(zhì)：第八頁，共三十頁，2022年，8月28日一個簡單圖G=<V，E>由V中每兩個結(jié)點間的鄰接關(guān)系唯一地確定，這種關(guān)系可以用一個矩陣給出，而矩陣形式與圖中結(jié)點的編序有密切關(guān)系，這是用矩陣表示圖值得注意的一點。第九頁，共三十頁，2022年，8月28日有向圖的鄰接矩陣第十頁，共三十頁，2022年，8月28日對于給定圖D，顯然不會因結(jié)點編序不同而使其結(jié)構(gòu)發(fā)生任何變化，即圖的結(jié)點所有不同的編序?qū)嶋H上仍表示同一個圖。換句話說，這些結(jié)點的不同編序的圖都是同構(gòu)的，并且它們的鄰接矩陣都是相似的。今后將略去這種由于V中結(jié)點編序而引起鄰接矩陣的任意性，而取該圖的任一個鄰接矩陣作為該圖的矩陣表示。第十一頁，共三十頁，2022年，8月28日第十二頁，共三十頁，2022年，8月28日性質(zhì)：A(D)中所有元素之和為D中長度為1的通路總數(shù)，其中主對角線元素之和為D中長度為1的回路（環(huán)）的總數(shù)。第十三頁，共三十頁，2022年，8月28日鄰接矩陣可展示相應(yīng)圖的一些性質(zhì)：若鄰接矩陣的元素全為零，則其對應(yīng)的圖是零圖；若鄰接矩陣的元素除主對角線元素外全為1，則其對應(yīng)的圖是連通的且為簡單完全圖。第十四頁，共三十頁，2022年，8月28日第十五頁，共三十頁，2022年，8月28日此外，當給定的簡單圖是無向圖時，鄰接矩陣是對稱矩陣；反之，若給定任何對稱矩陣A，顯然可以唯一地作出以A為其鄰接矩陣的簡單圖G。于是，所有n個結(jié)點的不同編序的簡單圖的集合與所有n階對稱矩陣的集合可建立一一對應(yīng)。第十六頁，共三十頁，2022年，8月28日當所給圖是簡單有向圖時，其鄰接矩陣并非一定是對稱矩陣，但所有n個結(jié)點的不同編序的簡單圖的集合，與所有n階鄰接矩陣的集合亦可建立一一對應(yīng)。不僅如此，通過對矩陣元素的一些計算還可以得到對應(yīng)圖的某些數(shù)量的特征。第十七頁，共三十頁，2022年，8月28日由給定有向圖D的鄰接矩陣A可計算出矩陣A的l次冪，即Al。第十八頁，共三十頁，2022年，8月28日在一些實際問題中，有時要判定圖中結(jié)點vi到結(jié)點vj是否可達，或者說vi到vj是否存在一要鏈（或通路）。如果要利用圖D的鄰接矩陣A，則應(yīng)計算A2，A3，···，An，···。當發(fā)現(xiàn)其中某個Ar中≥1，就表明vi可達vj或vi到vj存在一條鏈（或通路）。但這種計算繁瑣量大，又不知計算Ar到何時為止。第十九頁，共三十頁，2022年，8月28日根據(jù)定理10.2.2可知，對于有n個結(jié)點的圖，任何基本鏈（或通路）的長度不大于n-1和任何基本圈（或回路）的長度不大于n。因此，只需考慮就可以了，其中1≤r≤n。即只要計算Bn=A+A2+A3+···+An。第二十頁，共三十頁，2022年，8月28日如果關(guān)心的是結(jié)點間可達性或結(jié)點間是否有鏈（或路），至于結(jié)點間的鏈存在多少條及長度是多少無關(guān)緊要，那么便可用下面的定義圖的可達矩陣來表示結(jié)點間可達性。第二十一頁，共三十頁，2022年，8月28日給定有向圖D=<V，E>，將其結(jié)點按下標編序得V={v1，v2，…，vn}。定義一個n階方陣P=(pij)，其中1vi到vj可達Pij=0否則(Pii=1,i=1,2,…,n,若需要則添加）則稱矩陣P是圖D的可達矩陣。{有向圖的可達矩陣第二十二頁，共三十頁，2022年，8月28日可見，可達矩陣表明了圖中任意兩結(jié)點間是否至少存在一條鏈(或通路)以及在結(jié)點處是否有圈(或回路)。從圖D的鄰接矩陣A可以得到可達矩陣P，即令Bn=A+A2+A3+…+An，再從Bn中非零元素改為1而零元素不變(若需要，主對角線元素均改為1)，這種變換后的矩陣即是可達矩陣P。顯然可達矩陣是布爾矩陣。第二十三頁，共三十頁，2022年，8月28日應(yīng)用：求有向圖的強連通分支。

設(shè)P是D的可達矩陣，其元素pij,PT是P的轉(zhuǎn)置，其元素pijT,則圖D的強連通分支可從矩陣P∧PT求得。因從vi到vj可達，則pij=1，從vj到vi可達，則pji=1，即pijT=1，于是當且僅當vi和vj相互可達時，P∧PT的第(i,j)個元素的值為1給定簡單有向圖D中的任意結(jié)點vi，若P=(pij)是D的可達矩陣，PT=(pji)是P的轉(zhuǎn)置矩陣，則P∧PT的第i行元素為1的列號為下標的結(jié)點構(gòu)成了包含vi的強分圖第二十四頁，共三十頁，2022年，8月28日例如:求下列有向圖的通路總數(shù),回路總數(shù),可達矩陣,及強連通分支的頂點集.第二十五頁，共三十頁，2022年，8月28日

長度小于等于5的通路總數(shù)70長度小于等于5的回路總數(shù)12第二十六頁，共三十頁，2022年，8月28日該圖的強連通分支的頂點集為{v1},{v2},{v3,v4,v5}.第二十七頁，共三十頁，2022年，8月28日利用簡單有向圖的可達矩陣，能夠確定某過程是否為遞歸的。假設(shè)VP={p1,p2,···,pn}是程序P中的過程集合，做有向圖D=<VP,E>，其中piVP，i=1,2,···,n；<pi,pj>Epi調(diào)用pj。如果圖D中有包含pi的回路，則可斷言pi是遞歸的。為此，由圖G的鄰接矩陣A=(aij)計算出可達矩陣A+=()。如果A+中的主對角線上的某元素=1，則pi是遞歸的。第二十八頁，共三十頁，2022年，8月28日已知加權(quán)的簡單圖G=<V,E>，定義一個矩陣W=(wij)，其中：

w,w是邊[