離散數(shù)學(xué)圖的概念與表-資料下載頁
2025-01-16 20:15本頁面
【正文】 矩陣表明了圖中任意兩結(jié)點(diǎn)間是否至少存在一條鏈 (或路 )以及在結(jié)點(diǎn)處是否有圈 (或回路 )。 從圖 G的鄰接矩陣 A可以得到可達(dá)矩陣 P，即令 Bn=A+A2+A3+…+ An，再從 Bn中非零元素改為 1而零元素不變，這種變換后的矩陣即是可達(dá)矩陣 P。 假 設(shè) 矩 陣 中 的 元 素 是 屬 于 布 爾 代 數(shù)B,?,?,ˉ,0,1的 B中元素 ， 其中 B={0,1}， 則稱該矩陣為布爾矩陣 。 顯然鄰接矩陣是一個(gè)布爾矩陣 ， 同樣可達(dá)矩陣也是布爾矩陣 。 下面定義兩個(gè)布爾矩陣 B與 C的運(yùn)算： 令 B和 C的布爾和、布爾積分別記為 B?C和BoC，其定義為 (B?C)ij=bij?cij (B ? C)ij= (bik?ckj) i,j=1,2,,n。其中 bij， cij分別是 B和 C的 i行 j列元素。 特別地，對(duì)于鄰接矩陣 A，記 A ? A=A(2)，對(duì)任何 r=2,3,,有 A(r1) ? A=A(r) 要注意的是 Ar與 A(r)的差別。 Ar中 表明從vi到 vj長度為 r的鏈（或路）的數(shù)目，而 A(r)中 是指出：若 vi到 vj至少存在一條鏈（或路）時(shí)， =1，否則， =0。 由上說明，便得到可達(dá)矩陣 P為： P=A?A(2)?A(3)??A(n)= A(k) 對(duì)于簡單有向圖 G=V,E， 顯然有E?V?V。 因此 ， 弧集合 E可解釋成 B中的二元關(guān)系 ， 而二元關(guān)系是可用矩陣表示的 ，通常稱這種矩陣為關(guān)系矩陣 ， 其定義如下： 設(shè)兩個(gè)有限集合 X={x1,x2,,xm}和Y={y1,y2,,yn}，則關(guān)系 R?X?Y的關(guān)系矩陣MR=(rij)，其中 1, xi,yi?R rij= 0, 否則 i=1,2,,m； j=1,2,,n。 { 由定義可知，關(guān)系 R與其關(guān)系矩陣 MR是一一對(duì)應(yīng)的，即可以相互確定。 根據(jù)集合論可知，對(duì)于域 F(R)=V而 |V|=n的關(guān)系 R的傳遞閉包 R+可計(jì)算如下： R+=R∪ R2∪ R3∪ ∪ Rk (k≤n) 于是，關(guān)系 R1和 R2的關(guān)系矩陣分別為 A1和A2，則關(guān)系 R1∪ R2的關(guān)系矩陣為 A1?A2。用歸納法可以證明 R+的關(guān)系矩陣是 = ? ? ?? 對(duì)于 G=V,E的鄰接矩陣 A是關(guān)系 E的關(guān)系矩陣，因?yàn)?E2=EoE，即若存在一個(gè)結(jié)點(diǎn) vk，使得 viEvk，和 vkEvj，則必有 viE2vj，亦即從 vi到 vj若至少存在一條長度為 2的鏈（或路），那么 E2的關(guān)系矩陣中的 (i,j)元素值為 1。這表明矩陣 A(2)是關(guān)系 E2的關(guān)系矩陣。以此類推， A(k)是 Ek的關(guān)系矩陣， k=2,3,,n。因此 A+=A?A(2)?A(3)??A(n) 亦即 A+=A?A(2)?A(3)??A(n)=P 可見，關(guān)系 E的傳遞閉包 E+的關(guān)系矩陣 A+與可達(dá)矩陣相同。 為了計(jì)算 A+或 P，自然可先依次求得 A(2)，A(3)， ， A(n)，然后再計(jì)算 A(k)，其結(jié)果即為所求，這是計(jì)算 A+或 P的一種方法，還可介紹一種現(xiàn)有效的方法 — Warshall算法，它由鄰接矩陣 A依下面給出的步驟便能計(jì)算 A+。其步驟如下： (1) P?A (2) k?1 (3) i?1 (4) 若 pik=1，對(duì) j=1,2,,n作 pij?pij?pkj (5) i?i+1，若 i≤n則轉(zhuǎn) (4) (6) k?k+1，若 k≤n則轉(zhuǎn)到 (3)，否則停止。 該算法的關(guān)鍵的一步是 (4)，它判定如果pik=1，將第 i行和第 k行的各對(duì)應(yīng)元素作布爾和或邏輯加后送到第 i行中去。 給定關(guān)系 E1和關(guān)系 E2， 它們的關(guān)系矩陣分別為A=(aij)和 B=(bij)， 則關(guān)系交 E1∩E2的關(guān)系矩陣記為 A∧ B，其定義如下： (A∧ B)ij=aij∧ bij 于是 ， 由可達(dá)矩陣和利用關(guān)系交的關(guān)系矩陣可求出包含圖中任何指定結(jié)點(diǎn)的強(qiáng)分圖 。 定理 給定簡單有向圖 G中的任意結(jié)點(diǎn) vi， 若P=(pij)是 G的可達(dá)矩陣 ， PT=(pji)是 P的轉(zhuǎn)置矩陣 ， 則P∧ PT的第 i行元素為 1的列號(hào)為下標(biāo)的結(jié)點(diǎn)構(gòu)成了包含 vi的強(qiáng)分圖 。 利用簡單有向圖的可達(dá)矩陣 ， 能夠確定某過程是否為遞歸的 。 假設(shè) VP={p1,p2,,pn}是程序 P中的過程集合 ，做有向圖 G=VP,E， 其中 pi?VP， i=1,2,,n；pi,pj?E?pi調(diào)用 pj。 如果圖 G中有包含 pi的回路 ， 則可斷言 pi是遞歸的 。 為此 ， 由圖 G的鄰接矩陣 A=(aij)計(jì)算出可達(dá)矩陣 A+=( )。 如果 A+中的主對(duì)角線上的某元素 =1， 則 pi是遞歸的 。 在圖的矩陣表示中 ， 除鄰接矩陣外 ，還有關(guān)聯(lián)矩陣 、 圈 （ 或回路 ） 矩陣 、 權(quán)矩陣等 ， 在此就不都予涉及了 ， 只是再給出權(quán)矩陣的概念以結(jié)束本小節(jié) 。 已知加權(quán)的簡單圖 G=V,E，定義一個(gè)矩陣 W=(wij)，其中： w, w是邊 [vi,vj]（或弧 vi,vj） ?E 的權(quán) wij= 0， vi與 vj不相鄰 則稱 W為圖 G的權(quán)矩陣 {
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1