【正文】 ,pn}是程序 P中的過程集合 ，做有向圖 G=VP,E， 其中 pi?VP， i=1,2,?A(n)=P 可見，關(guān)系 E的傳遞閉包 E+的關(guān)系矩陣 A+與可達矩陣相同?！?Rk (k≤n) 于是，關(guān)系 R1和 R2的關(guān)系矩陣分別為 A1和A2，則關(guān)系 R1∪ R2的關(guān)系矩陣為 A1?A2。 顯然鄰接矩陣是一個布爾矩陣 ， 同樣可達矩陣也是布爾矩陣 。 一個簡單圖 G=V， E由 V中每兩個結(jié)點間的鄰接關(guān)系唯一地確定，這種關(guān)系可以用一個矩陣給出，而矩陣形式與圖中結(jié)點的編序有密切關(guān)系，這是用矩陣表示圖值得注意的一點。如程序 A控制著資源 r1，請求資源 r2；但程序 B控制著資源r2，請求資源 r1。 令 G是簡單有向圖 ， 對于某種性質(zhì)而言 ， 若 G中再沒有其它包含子圖 G1的真子圖具有這種性質(zhì) ， 則稱 G1是G的關(guān)于該性質(zhì)的極大子圖 。 對于連通的非平凡圖 G， 稱 ?(G)= {|S||S是 G的分離結(jié)點集 }為圖 G的結(jié)點連通度 ， 它表明產(chǎn)生不連通圖而需要刪去結(jié)點的最少數(shù)目 。 可以看出，對于簡單圖來說，鏈 (或路 )和圈 (或回路 )能夠僅用結(jié)點序列表示之。對于有向圖的同構(gòu)還要求保持邊的方向 。 定義 給定無向圖 G1=V1， E1和 G2=V2，E2， 于是 (1) 如果 V2?V1和 E2?E1， 則稱 G2為 G1的子圖 ， 記為 G2?G1。 加權(quán)圖在實際中有許多應用 ， 如在輸油管系統(tǒng)圖中權(quán)表示單位時間流經(jīng)管中的石油數(shù)量；在城市街道中 ，權(quán)表示表示通行車輛密度；在航空交通圖中 ， 權(quán)表示兩城市的距離等等 。第十六章 圖的概念與表示 圖的基本概念 鏈 (或路 )與圈 (或回路 ) 圖的矩陣表示 退出 圖的基本概念 什么是圖 ?可用一句話概括 ， 即：圖是用點和線來刻劃離散事物集合中的每對事物間以某種方式相聯(lián)系的數(shù)學模型 。 定義 在無向圖 G=V， E中 ， 如果 V中的每個結(jié)點都與其余的所有結(jié)點鄰接 ， 即 (?vi)(?vj)(vi， vj∈ V→ 〔 vi， vj〕 ∈ E) 則該圖稱為無向完全圖 ， 記作 K|V|。 (2) 如果 V2?V1， E2?E1且 E2≠E1， 則稱 G2為 G1的真子圖 ， 記為 G2?G1。 一般說來 ， 證明兩個圖是同構(gòu)的并非是輕而易舉的事情 ， 往往需要花些氣力 。 定理 在一個圖中 ， 若從結(jié)點 vi到結(jié)點 vj存在一條鏈 (或路 )， 則必有一條從 vi到 vj的基本鏈 (或基本路 )。于是 ， 對于分離圖 G， ?(G)=0；對于存在割點的連通圖 G， ?(G)=1。 定義 在簡單有向圖中 ， 具有強連通性質(zhì)的極大子圖 ， 稱為強分圖；具有單向連通性質(zhì)的極大子圖 ，稱為單向分圖；具有弱連通性質(zhì)的極大子圖 ， 稱為弱分圖 。這種情況稱為處于死鎖狀態(tài)。 定義 給定簡單圖 G=V， E， V={v1，v2， … ， vn}， V中的結(jié)點按下標由小到大編序，則 n階方陣 A=(aij)稱為圖 G的鄰接矩陣。 下面定義兩個布爾矩陣 B與 C的運算： 令 B和 C的布爾和、布爾積分別記為 B?C和BoC，其定義為 (B?C)ij=bij?cij (B ? C)ij= (bik?ckj) i,j=1,2,用歸納法可以證明 R+的關(guān)系矩陣是 = ? ? ? 為了計算 A+或 P，自然可先依次求得 A(2)，A(3)， 因此 ， 弧集合 E可解釋成 B中的二元關(guān)系 ， 而二元關(guān)系是可用矩陣表示的 ，通常稱這種矩陣為關(guān)系矩陣 ， 其定義如下： 設(shè)兩個有限集合 X={x1,x2, 假 設(shè) 矩 陣 中 的 元 素 是 屬 于 布 爾 代 數(shù)B,?,?,ˉ,0,1的 B中元素 ， 其中 B={0,1}， 則稱該矩陣為布爾矩陣 。An， 圖 圖的矩陣表示 為什么要用矩陣來表示圖 ？ 給定一個圖 G=V， E， 使用 G=V，E這種表示法存在兩個缺陷： 在圖比較復雜時不夠直觀； 不方便計算 。 對資源的請求可能發(fā)生沖突。 定理 有向圖 G是強連通的 ?G中有一回路 ，它至少通過每個結(jié)點一次 。 類似地可定義圖 G的分離邊集 T；若圖 G的分離邊集 T={e}，則稱 e是 G的割邊或橋。 定義 在一圈 (或回路 )中，若出現(xiàn)的每條邊(或弧 )恰好一次，稱該圈 (或回路 )為簡單圈 (或簡單回路 )；若出現(xiàn)的每個結(jié)點恰好一次，稱該圈 (或回路 )為基本圈(或基本回路 )。 由同構(gòu)的定義可知 ， 不僅結(jié)點之間要具有一一對應關(guān)系 ， 而且要求這種對應關(guān)系保持結(jié)點間的鄰接關(guān)系 。 顯然 ， 對于 k度正則圖 G， Δ(G)=δ(G)=k。 定義 給每條邊或弧都賦予權(quán)的圖 G=V，E， 稱為加權(quán)圖 ， 記為 G=V， E， W， 其中 W表示各邊之權(quán)的集合 。 因為它顯得太抽象 ， 不便于理解 ， 所以有必要給出另外的回答 。 若|V|=n， 該圖記作 Kn。 (3) 如果 V2=V1， E2?E1， 則稱 G2為 G1的生成子圖 ，記為 G2 G1。請讀者證明圖 。 定理 在一個具有 n個結(jié)點的圖中 ， 則 (1) 任何基本鏈 (或路 )的長度均不大于 n1。 類似地定義邊連通度 ?(G)= {|T||T是 G的分離邊集 }，它表明產(chǎn)生不連通圖而需要刪去邊的最少數(shù)目。 定理 簡單有向圖中的任一個結(jié)點恰位于一個強分圖中 。然而沖突的請求必須解決，資源分配圖有助發(fā)現(xiàn)和糾正死鎖。其中 i， j=1， 2， … ，