【正文】 邊 (對于有向圖中 ， 任何兩結點間不多于一條同向弧 )， 并且任何結點無環(huán) ， 則圖 G稱為簡單圖；若兩結點間多于一條邊 (對于有向圖中 ， 兩結點間多于一條同向弧 )圖 G稱為多重圖 ， 并把聯(lián)結兩結點之間的多條邊或弧 ， 稱為平行邊或弧 ， 平行邊或弧的條數(shù)稱為重數(shù) 。 若一個圖中只含一個孤立結點 ， 該圖稱為平凡圖 。 定義 在無向圖 G=V， E中 ， 如果每個結點的度是 k， 即 (?v)(v∈ V→ d(v)=k)， 則圖 G稱為 k度正則圖 。 如果 E2=EE1且 G2=E2， 則稱圖 G2是相對于圖 G的子圖 G1的補圖 。 顯然 ， 兩圖的同構是相互的 ， 即 G1同構于 G2， G2同構于 G1。因此在 (a)中度數(shù)為 3的結點 x與兩個度數(shù)為 1的結點鄰接，而 (b)中度數(shù)為 3的結點 y僅與一個度數(shù)為 1的結點鄰接。 顯然，每條基本鏈 (或基本路 )必定是簡單鏈 (或簡單路 )。 對于無向圖 G來說 ， 不難證明結點間的可達性是結點集合上的等價關系 。若圖 G的分離結點集 S={v}，則稱 v是G的割點。 定理 一個連通無向圖 G中的邊 e在兩個結點 u和 w， 使得聯(lián)結 u與 w的每條鏈都經(jīng)過 e。 從上面定義可知 ， 若圖 G是強連通的 ， 則它必是單向連通的 ， 但反之未必真；若圖 G是單向連通的 ， 則它必是弱連通的 ， 反之不真 。 如果結點 u可達結點 v，它們之間可能存在不止一條鏈 (或路 )。當一個程序要求使用某種資源，它要發(fā)出請求，操作系統(tǒng)必須保證這一請求得到滿足。 Rt={r1， r2， … ， rn}是系統(tǒng)在時刻 t的資源集合。于是，對于圖 ， Gt是強連通的，即處于死鎖狀態(tài)。 即 d+(vi)= 和 d(vj)= 。即只要計算 Bn=A+A2+A3+ 從圖 G的鄰接矩陣 A可以得到可達矩陣 P，即令 Bn=A+A2+A3+…+ An，再從 Bn中非零元素改為 1而零元素不變，這種變換后的矩陣即是可達矩陣 P。 特別地，對于鄰接矩陣 A，記 A ? A=A(2)，對任何 r=2,3,?A(n)= A(k) 對于簡單有向圖 G=V,E， 顯然有E?V?V。以此類推， A(k)是 Ek的關系矩陣， k=2,3, 如果 A+中的主對角線上的某元素 =1， 則 pi是遞歸的 。 給定關系 E1和關系 E2， 它們的關系矩陣分別為A=(aij)和 B=(bij)， 則關系交 E1∩E2的關系矩陣記為 A∧ B，其定義如下： (A∧ B)ij=aij∧ bij 于是 ， 由可達矩陣和利用關系交的關系矩陣可求出包含圖中任何指定結點的強分圖 。因此 A+=A?A(2)?A(3)?,xm}和Y={y1,y2, Ar中 表明從vi到 vj長度為 r的鏈（或路）的數(shù)目，而 A(r)中 是指出：若 vi到 vj至少存在一條鏈（或路）時， =1，否則， =0。 如果關心的是結點間可達性或結點間是否有鏈（或路），至于結點間的鏈存在多少條及長度是多少無關緊要，那么便可用下面的定義圖的可達矩陣來表示結點間可達性。 當發(fā)現(xiàn)其中某個 Ar中 ≥1， 就表明 vi可達 vj或 vi到 vj存在一條鏈 （ 或路 ） 。 定理 設 A為簡單圖 G的鄰接矩陣，則 Al中的 i行 j列元素 alij等于 G中聯(lián)結 vi到 vj的長度為 l的鏈 (或路 )的數(shù)目。其中 i， j=1， 2， … ， n 有時為強調(diào)鄰接矩陣依賴于圖 G，把圖 G的鄰接矩陣記為 A(G)。 例如，令 Rt={r1,r2,r3,r4}， Qt={p1,p2,p3,p4}。然而沖突的請求必須解決，資源分配圖有助發(fā)現(xiàn)和糾正死鎖。 下面給出簡單有向圖的一個應用 —— 資源分配圖。 定理 簡單有向圖中的任一個結點恰位于一個強分圖中 。 一般說來 ， 不是對稱的 。 類似地定義邊連通度 ?(G)= {|T||T是 G的分離邊集 }，它表明產(chǎn)生不連通圖而需要刪去邊的最少數(shù)目。 所謂從圖G=V,E中刪去結點集 S， 是指作 VS以及從 E中刪去與S中的全部結點相聯(lián)結的邊而得到的子圖 ， 記作 GS；特別當 S=|v|時 ， 簡記為 Gv；所謂從圖 G=V,E中刪去邊集 （ 或弧集 ） T， 是指作 ET， 且 T中的全部邊所關聯(lián)的結點仍在 V中而得到的子圖 ， 記為 GT；特別當 T={e}時 ，簡記作 Ge。 定理 在一個具有 n個結點的圖中 ， 則 (1) 任何基本鏈 (或路 )的長度均不大于 n1。令v0， v1， … ， vm∈ V，邊 (或弧 )e1， e2， … ， em∈ E，其中vi1， vi是 ei的結點，交替序列 v0e1v1e2v2… emvm稱為連接 v0到 vm的鏈 (或路 )。請讀者證明圖 。 因此 ， 對于給定的兩個圖 ， 在它們的圖形表示中 ， 即在用小圓圈表示結點和用直線或曲線表示聯(lián)結兩個結點的邊的圖解中 ， 看起來很不一樣 ， 但實際上卻是表示同一個圖 。 (3) 如果 V2=V1， E2?E1， 則稱 G2為 G1的生成子圖 ，記為 G2 G1。 顯然，對于孤立結點的度數(shù)為零。 若|V|=n， 該圖記作 Kn。而聯(lián)結一結點與它自身的一條邊，稱為環(huán)。 因為它顯得太抽象 ， 不便于理解 ， 所以有必要給出另外的回答 。若邊 e∈ E與無序結點對 〔 vi， vj〕 相聯(lián)系，則 φ(e)=〔 vi， vj〕 ，這時邊 e稱為無向邊，有時簡稱為邊；若邊 e∈ E與有序結點對 vi， vj相聯(lián)系，則 φ(e)=vi， vj，此時邊 e稱為有向邊或弧