大連理工Chapter7圖論

1、離散數(shù)學(xué)（圖論）Discrete Mathematics8/11/20221第七章 圖論圖是一類非常廣泛的數(shù)學(xué)模型,在現(xiàn)實中的許多問題,如電網(wǎng)絡(luò)問題,交通網(wǎng)絡(luò)問題,運輸?shù)膬?yōu)化問題,社會學(xué)中某類關(guān)系的研究,都可以用這類數(shù)學(xué)模型研究和處理。在計算機科學(xué)的許多領(lǐng)域,如開關(guān)理論與邏輯設(shè)計, 人工智能, 形式語言, 計算機圖形,操作系統(tǒng),編譯程序, 信息檢索等方面圖和圖的理論也有很多重要的應(yīng)用。8/11/202227.4圖的矩陣表示 給定一個圖G=，使用圖形表示法很容易把圖的結(jié)構(gòu)展現(xiàn)出來，而且這種表示直觀明了。 本節(jié)提供另一種圖的表示法圖的矩陣表示法。它不僅克服了圖形表示法的不足，而且這種表示可以充分利

2、用現(xiàn)代工具電子計算機，以達到研究圖的目的。一個簡單圖G=由V中每兩個結(jié)點間的鄰接關(guān)系惟一地確定，這種關(guān)系可以用一個矩陣給出，而矩陣形式與圖中結(jié)點的編序有密切關(guān)系,這是用矩陣表示圖值得注意的一點。8/11/20223定義7.4.1 給定簡單圖G=,V=v1,v2，vn，V中的結(jié)點按下標由小到大編序，則n階方陣A=(aij)稱為圖G的鄰接矩陣。其中 i，j=1，2，n。 有時為強調(diào)鄰接矩陣依賴于圖G，把圖G的鄰接矩陣記為A(G)。7.4圖的矩陣表示 8/11/20224例7.4.1 圖G=如圖7.4.1(a)所示， 7.4圖的矩陣表示 8/11/20225例7.4.1 它的鄰接矩陣A為 A= A=

3、對于圖G，不管它是有向圖還是無向圖，其鄰接矩陣都與圖中結(jié)點編序有關(guān)。 7.4圖的矩陣表示 8/11/20226簡單有向G=如圖7.4.2(a)所示,它的鄰接矩陣A 7.4圖的矩陣表示 8/11/20227鄰接矩陣可展示相應(yīng)圖的一些性質(zhì)：(1)若鄰接矩陣的元素全為零，則其對應(yīng)的圖是零圖；(2)若鄰接矩陣的元素除主對角線元素外全為1，則其對應(yīng)的 圖是連通的且為簡單完全圖。(3)當(dāng)給定的簡單圖是無向圖時，鄰接矩陣是對稱矩陣； 反之，若給定任何對稱矩陣A，顯然可以惟一地作出以A為其鄰接矩陣的簡單圖G。于是，所有n個結(jié)點的不同編序的簡單圖的集合與所有n階對稱矩陣的集合可建立一一對應(yīng)。(4)當(dāng)給定的圖是簡

4、單有向圖時，其鄰接矩陣并非一定是對稱矩陣，但所有n個結(jié)點的不同編序的簡單圖的集合與所有n階鄰接矩陣的集合亦可建立一一對應(yīng)。7.4圖的矩陣表示 8/11/20228通過對稱矩陣元素的一些計算還可以得到對應(yīng)圖的某些數(shù)量的特征。(5)在給定簡單有向圖的鄰接矩陣中，第i行元素是 由結(jié)點vi出發(fā)的弧所確定，故第i行中值為1的元素 數(shù)目等于結(jié)點vi的出度。(6) 第j列中值為1的元素數(shù)目等于結(jié)點vj的入度。 d+(vi)= 和 d-(vj)= 7.4圖的矩陣表示 8/11/20229由給定簡單圖G的鄰接矩陣A可計算出矩陣A的l次冪，即Al。其第i行第j列上的元素便是G中從第i個結(jié)點vi到第j個結(jié)點vj長度

5、為l的鏈(或路)的數(shù)目。定理7.4.1 設(shè)A為簡單圖G的鄰接矩陣，則Al中的i行j列元素aijl等于G中聯(lián)結(jié)vi到vj的長度為l的鏈(或路)的數(shù)目。 7.4圖的矩陣表示 8/11/202210例7.4.2 已知簡單有向圖G=如圖7.4.3所示，G的鄰接矩陣A是7.4圖的矩陣表示 8/11/202211在一些實際問題中，有時要判定圖中結(jié)點vi到結(jié)點vj是否可達，或者說vi到vj是否存在一條鏈(或路)。如果要利用圖G的鄰接矩陣A，則應(yīng)計算A2，A3，An，。當(dāng)發(fā)現(xiàn)其中某個Ar中 1，就表明vi可達vj或vi到vj存在一條鏈(或路)。 7.4圖的矩陣表示 8/11/202212但這種計算繁瑣量大，又

6、不知計算Ar到何時為止。根據(jù)定理7.2.2可知，對于有n個結(jié)點的圖，任何基本鏈(或路)的長度不大于n-1和任何基本圈(或回路)的長度不大于n。因此，只需考慮 就可以了，其中1rn。即只要計算Bn=A+A2+A3+An 。 7.4圖的矩陣表示 8/11/202213定義7.4.2 給定圖G=，將其結(jié)點按下標編序得V=v1，v2，vn。定義一個n階方陣P=(pij)，其中 則稱矩陣P是圖G的可達矩陣。7.4圖的矩陣表示 8/11/202214可達矩陣表明了圖中任意兩結(jié)點間是否至少存在一條鏈(或路)以及在結(jié)點處是否有圈(或回路)。從圖G的鄰接矩陣A可以得到可達矩陣P，即令 Bn=A+A2+A3+An

7、 ，再從Bn中非零元素改為1而零元素不變，這種變換后的矩陣即是可達矩陣P。7.4圖的矩陣表示 8/11/202215例7.4.3 設(shè)圖G的鄰接矩陣A是試求G的可達矩陣P。 7.4圖的矩陣表示 8/11/202216定義7.4.3 給定無環(huán)的有向圖D=，V=v1，v2，vm，E=e1，e2，en，令則稱B=(bij)mn是D的關(guān)聯(lián)矩陣。7.4圖的矩陣表示 8/11/202217例如，圖7.4.4所示的有向圖的關(guān)聯(lián)矩陣B(D)。7.4圖的矩陣表示 8/11/202218B(D)有如下性質(zhì)：bij=0，j=1，2，n，表明矩陣中每列元素 之和為0，從而矩陣所有元素之和為0。(+1)=(-1)=|E|

8、，表明有向圖的握手定理。第i行中，(+1)=d+(vi)，|(-1)|=d-(vi)。平行邊所對應(yīng)的列相同。7.4圖的矩陣表示 8/11/202219假設(shè)矩陣中的元素是屬于布爾代數(shù)的B中元素。其中B=0, 1,則稱該矩陣為布爾矩陣。顯然鄰接矩陣是一個布爾矩陣，同樣可達矩陣也是布爾矩陣。下面定義兩個布爾矩陣B與C的運算:令B與C的布爾和、布爾積分別記為BC和BC，其定義為 (BC)ij=bijcij (BC)ij= (bikckj)i，j=1，2，n。其中bij，cij分別B和C的i行j列元素。 7.4圖的矩陣表示 8/11/202220對于鄰接矩陣A，記A(1)=A，對任何r=2，3，有 A(

9、r-1)A=A(r)要注意的是Ar與A(r)的差別。Ar中表明從vi到vj長度為r的鏈(或路)的數(shù)目，A(r)中是指出了:若vi到vj至少存在一條鏈(或路)時， =1；則， =0。便得到可達矩陣P為: P=AA(2)A(3)A(n)= A(k)7.4圖的矩陣表示 8/11/202221例7.4.4 令鄰接矩陣A為試求A(2)，A(3)，A(4)和P。7.4圖的矩陣表示 8/11/202222Warshall算法-下面給出步驟便能計算P，其步驟如下:(1) PA(2) k1(3) i1(4) 若pik=1，對j = 1，2，n作pijpijpkj(5) ii+1，若in則轉(zhuǎn)(4)(6) kk+1，若