離散數(shù)學(xué)圖的概念與表(文件)
【正文】 今后將略去這種由于 V中結(jié)點(diǎn)編序而引起鄰接矩陣的任意性 ， 而取該圖的任一個鄰接矩陣作為該圖的矩陣表示 。 v1 v2 v3 0 1 0 1 0 1 0 1 0 A= G A2= 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 . = 1 0 1 0 2 0 1 0 1 A3= 1 0 1 0 2 0 1 0 1 0 1 0 1 0 1 0 1 0 . = 0 2 0 2 0 2 0 2 0 v1 v2 v3 0 2 0 2 0 2 0 2 0 A3= G A4= 0 2 0 2 0 2 0 2 0 0 1 0 1 0 1 0 1 0 . = 2 0 2 0 4 0 2 0 2 A5= 2 0 2 0 4 0 2 0 2 0 1 0 1 0 1 0 1 0 . = 0 4 0 4 0 4 0 4 0 由給定簡單圖 G的鄰接矩陣 A可計算出矩陣 A的 l次冪，即 Al。 在一些實(shí)際問題中 ， 有時要判定圖中結(jié)點(diǎn) vi到結(jié)點(diǎn)vj是否可達(dá) ， 或者說 vi到 vj是否存在一要鏈 （ 或路 ） 。An， 但這種計算繁瑣量大 ， 又不知計算 Ar到何時為止 。 定義 給定圖 G=V， E，將其結(jié)點(diǎn)按下標(biāo)編序得 V={v1， v2， … ， vn}。 假 設(shè) 矩 陣 中 的 元 素 是 屬 于 布 爾 代 數(shù)B,?,?,ˉ,0,1的 B中元素 ， 其中 B={0,1}， 則稱該矩陣為布爾矩陣 。 由上說明，便得到可達(dá)矩陣 P為： P=A?A(2)?A(3)? 因此 ， 弧集合 E可解釋成 B中的二元關(guān)系 ， 而二元關(guān)系是可用矩陣表示的 ，通常稱這種矩陣為關(guān)系矩陣 ， 其定義如下： 設(shè)兩個有限集合 X={x1,x2,n。 定理 給定簡單有向圖 G中的任意結(jié)點(diǎn) vi， 若P=(pij)是 G的可達(dá)矩陣 ， PT=(pji)是 P的轉(zhuǎn)置矩陣 ， 則P∧ PT的第 i行元素為 1的列號為下標(biāo)的結(jié)點(diǎn)構(gòu)成了包含 vi的強(qiáng)分圖 。,n；pi,pj?E?pi調(diào)用 pj。 在圖的矩陣表示中 ， 除鄰接矩陣外 ，還有關(guān)聯(lián)矩陣 、 圈 （ 或回路 ） 矩陣 、 權(quán)矩陣等 ， 在此就不都予涉及了 ， 只是再給出權(quán)矩陣的概念以結(jié)束本小節(jié) 。 為此 ， 由圖 G的鄰接矩陣 A=(aij)計算出可達(dá)矩陣 A+=( )。 假設(shè) VP={p1,p2, 該算法的關(guān)鍵的一步是 (4)，它判定如果pik=1，將第 i行和第 k行的各對應(yīng)元素作布爾和或邏輯加后送到第 i行中去。其步驟如下： (1) P?A (2) k?1 (3) i?1 (4) 若 pik=1，對 j=1,2, 為了計算 A+或 P，自然可先依次求得 A(2)，A(3)， ?A(n) 亦即 A+=A?A(2)?A(3)?,n。這表明矩陣 A(2)是關(guān)系 E2的關(guān)系矩陣。用歸納法可以證明 R+的關(guān)系矩陣是 = ? ? ? 根據(jù)集合論可知，對于域 F(R)=V而 |V|=n的關(guān)系 R的傳遞閉包 R+可計算如下： R+=R∪ R2∪ R3∪ ,yn}，則關(guān)系 R?X?Y的關(guān)系矩陣MR=(rij)，其中 1, xi,yi?R rij= 0, 否則 i=1,2,有 A(r1) ? A=A(r) 要注意的是 Ar與 A(r)的差別。其中 bij， cij分別是 B和 C的 i行 j列元素。 下面定義兩個布爾矩陣 B與 C的運(yùn)算： 令 B和 C的布爾和、布爾積分別記為 B?C和BoC，其定義為 (B?C)ij=bij?cij (B ? C)ij= (bik?ckj) i,j=1,2, { 可見，可達(dá)矩陣表明了圖中任意兩結(jié)點(diǎn)間是否至少存在一條鏈 (或路 )以及在結(jié)點(diǎn)處是否有圈 (或回路 )。+An。因此，只需考慮 就可以了，其中 1≤r≤n。為說明此事實(shí)，今給出下面定理。同理，第 j列中值為 1的元素數(shù)目等于結(jié)點(diǎn) vj的入度。 定義 給定簡單圖 G=V， E， V={v1，v2， … ， vn}， V中的結(jié)點(diǎn)按下標(biāo)由小到大編序，則 n階方陣 A=(aij)稱為圖 G的鄰接矩陣。 能夠證明，在時刻 t計算機(jī)系統(tǒng)處于死鎖狀態(tài) ?資源分配圖 Gt中包含強(qiáng)分圖。ri， rj表示有向邊， ri， rj∈ E當(dāng)且僅當(dāng)程序pk∈ Qt已分配到資源 ri且等待資源 rj。 令 Pt={p1， p2， … ， pm}表示計算機(jī)系統(tǒng)在時間 t的程序集合， Qt?Pt是運(yùn)行的程序集合，或者說在時刻 t至少分配一部分所請求的資源的程序集合。這種情況稱為處于死鎖狀態(tài)。操作系統(tǒng)對這些資源負(fù)責(zé)分配給各個程序。 此外，要注意，即使 u與 v相互可達(dá)， du，v未必等于 dv， u。 定理 簡單有向圖中的每個結(jié)點(diǎn)和每條弧恰位于一個弱分圖中。 定義 在簡單有向圖中 ， 具有強(qiáng)連通性質(zhì)的極大子圖 ， 稱為強(qiáng)分圖；具有單向連通性質(zhì)的極大子圖 ，稱為單向分圖；具有弱連通性質(zhì)的極大子圖 ， 稱
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1