離散數(shù)學圖的概念與表-預覽頁
【正文】 圖 返回 返回 圖 鏈 (或路 )與圈 (或回路 ) 在無向圖 (或有向圖 )的研究中 ， 常常考慮從一個結點出發(fā) ， 沿著一些邊 (或弧 )連續(xù)移動而達到另一個指定結點 ， 這種依次由結點和邊 (或弧 )組成的序列 ， 便形成了鏈 (或路 )的概念 。若 v0=vm時，該鏈 (或路 )稱為圈 (或回路 )。 可以看出，對于簡單圖來說，鏈 (或路 )和圈 (或回路 )能夠僅用結點序列表示之。 定義 在一個圖中 ， 若從 vi到 vj存在任何一條鏈 (或路 )， 則稱從 vi到 vj是可達的 ， 或簡稱 vi可達 vj。 定義 若圖 G只有一個連通分圖，則稱 G是連通圖；否則，稱圖 G為非連通圖或分離圖。 定義 給定連通無向圖 G=V， E， S?V。 對于連通的非平凡圖 G， 稱 ?(G)= {|S||S是 G的分離結點集 }為圖 G的結點連通度 ， 它表明產(chǎn)生不連通圖而需要刪去結點的最少數(shù)目 。 下面是由惠特尼 ()于 1932年得到的關于結點連通度、邊連通度和最小度的不等式聯(lián)系的定理： 定理 對于任何一個無向圖 G，有?(G)≤?(G)≤δ(G)。 定理 連通無向圖 G中的一條邊 e是割邊 ?e不包含在圖的任何基本圈中 。 對于給定的有向力 G， 要略去 G中每條邊的方向便得到一個無向圖 G1， 稱 G1是 G的基礎圖 。 令 G是簡單有向圖 ， 對于某種性質(zhì)而言 ， 若 G中再沒有其它包含子圖 G1的真子圖具有這種性質(zhì) ， 則稱 G1是G的關于該性質(zhì)的極大子圖 。 類似地可以證明下面兩個定理： 定理 簡單有向圖中的每個結點和每條弧至少位于一個單向分圖中。 距離滿足下列性質(zhì)： du， v≥0 du， u=0 du， v+dv， w≥du， w 如果 u不可達 v，則 du， v=+∞。實際上，程序共享計算機系統(tǒng)中的資源，如磁帶機、磁盤設備、 CPU、主存貯器和編譯程序等。如程序 A控制著資源 r1，請求資源 r2；但程序 B控制著資源r2，請求資源 r1。在請求的時間里，被請求的資源是不能利用的，程序控制著可利用的資源，但對不可利用的資源則必須等待。把每個資源 ri看作圖中一個結點，其中 i=1， 2， … ， n。 于是，可得到資源分配圖 Gt=Rt,E，如圖。 一個簡單圖 G=V， E由 V中每兩個結點間的鄰接關系唯一地確定，這種關系可以用一個矩陣給出，而矩陣形式與圖中結點的編序有密切關系，這是用矩陣表示圖值得注意的一點。 有關圖同構的判斷問題的討論可以參考以下網(wǎng)址： / 鄰接矩陣可展示相應圖的一些性質(zhì)： 若鄰接矩陣的元素全為零，則其對應的圖是零圖； 若鄰接矩陣的元素除主對角線元素外全為 1，則其對應的圖是連通的且為簡單完全圖； 當給定的簡單圖是無向圖時，鄰接矩陣是對稱矩陣； 問題 當給定的簡單圖是有向圖時，鄰接矩陣不是對稱矩陣； 以上結論是否成立？ 當給定的圖是多重圖時，如何用鄰接矩陣表示？ 在給定簡單有向圖的鄰接矩陣中，第 i行元素是由結點 vi出發(fā)的弧所確定，故第 i行中值為 1的元素數(shù)目等于結點 vi的出度。若第 i行第 j列上的元素 alij便是 G中從第i個結點 vi到第 j個結點 vj長度為 l的鏈（或路）的數(shù)目。 如果要利用圖 G的鄰接矩陣 A， 則應計算 A2， A3， 根據(jù)定理 ，對于有 n個結點的圖，任何基本鏈（或路）的長度不大于 n1和任何基本圈（或回路）的長度不大于 n。定義一個 n階方陣 P=(pij)，其中 1 vi到 vj可達 Pij= 0 否則 則稱矩陣 P是圖 G的可達矩陣。 顯然鄰接矩陣是一個布爾矩陣 ， 同樣可達矩陣也是布爾矩陣 。,n。,m； j=1,2, { 由定義可知，關系 R與其關系矩陣 MR是一一對應的，即可以相互確定?！?Rk (k≤n) 于是，關系 R1和 R2的關系矩陣分別為 A1和A2，則關系 R1∪ R2的關系矩陣為 A1?A2。? 對于 G=V,E的鄰接矩陣 A是關系 E的關系矩陣，因為 E2=EoE，即若存在一個結點 vk，使得 viEvk，和 vkEvj，則必有 viE2vj，亦即從 vi到 vj若至少存在一條長度為 2的鏈（或路），那么 E2的關系矩陣中的 (i,j)元素值為 1。?A(n)=P 可見，關系 E的傳遞閉包 E+的關系矩陣 A+與可達矩陣相同。 A(n)，然后再計算 A(k)，其結果即為所求，這是計算 A+或 P的一種方法，還可介紹一種現(xiàn)有效的方法 — Warshall算法，它由鄰接矩陣 A依下面給出的步驟便能計算 A+。,n作 pij?pij?pkj (5) i?i+1，若 i≤n則轉(zhuǎn) (4) (6) k?k+1，若 k≤n則轉(zhuǎn)到 (3)，否則停止。 利用簡單有向圖的可達矩陣 ， 能夠確定某過程是否為遞歸的 。,pn}是程序 P中的過程集合 ，做有向圖 G=VP,E， 其中 pi?VP， i=1,2, 如果圖 G中有包含 pi的回路 ， 則可斷言 pi是遞歸的 。 已知加權的簡單圖 G=V,E，定義一個矩陣 W=(wij)，其中： w, w是邊 [vi,vj]（或弧 vi,vj） ?E 的權 wij= 0， vi與 vj不相鄰 則稱 W為圖 G的權矩陣 {
環(huán)評公示相關推薦
鄂ICP備17016276號-1