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

設P是D的可達矩陣，其元素pij,PT是P的轉置，其元素pijT,則圖D的強連通分支可從矩陣P∧PT求得。因從vi到vj可達，則pij=1，從vj到vi可達，則pji=1，即pijT=1，于是當且僅當vi和vj相互可達時，P∧PT的第(i,j)個元素的值為1定理7.3.2給定簡單有向圖D中的任意結點vi，若P=(pij)是D的可達矩陣，PT=(pji)是P的轉置矩陣，則P∧PT的第i行元素為1的列號為下標的結點構成了包含vi的強分圖第24頁，課件共30頁，創作于2023年2月例如:求下列有向圖的通路總數,回路總數,可達矩陣,及強連通分支的頂點集.第25頁，課件共30頁，創作于2023年2月

長度小于等于5的通路總數70長度小于等于5的回路總數12第26頁，課件共30頁，創作于2023年2月該圖的強連通分支的頂點集為{v1},{v2},{v3,v4,v5}.第27頁，課件共30頁，創作于2023年2月利用簡單有向圖的可達矩陣，能夠確定某過程是否為遞歸的。假設VP={p1,p2,···,pn}是程序P中的過程集合，做有向圖D=<VP,E>，其中pi

VP，i=1,2,···,n；<pi,pj>

E

pi調用pj。如果圖D中有包含pi的回路，則可斷言pi是遞歸的。為此，由圖G的鄰接矩陣A=(aij)計算出可達矩陣A+=()。如果A+中的主對角線上的某元素=1，則pi是遞歸的。第28頁，課件共30頁，創作于2023年2月已知加權的簡單圖G=<V,E>，定義一個矩陣W=(wij)，其中：

w,w是邊