離散數(shù)學(xué)圖的概念與表(完整版)
【正文】 ， vi稱(chēng)為弧 e的始結(jié)點(diǎn)，vj稱(chēng)為弧 e的終結(jié)點(diǎn)。 定義 給每條邊或弧都賦予權(quán)的圖 G=V，E， 稱(chēng)為加權(quán)圖 ， 記為 G=V， E， W， 其中 W表示各邊之權(quán)的集合 。 定義 在有向圖 G=V， E中 ， 對(duì)任意結(jié)點(diǎn)v∈ V， 以 v為始結(jié)點(diǎn)的弧的條數(shù) ， 稱(chēng)為結(jié)點(diǎn) v的出度 ， 記為 d+(v)；以 v為終結(jié)點(diǎn)的弧的條條數(shù) ， 稱(chēng)為 v的入度 ， 記作 d(v)；結(jié)點(diǎn) v的出度與入度之和 ， 稱(chēng)為結(jié)點(diǎn)的度數(shù) ，記為 d(v)， 顯然 d(v)=d+(v)+d(v)。 顯然 ， 對(duì)于 k度正則圖 G， Δ(G)=δ(G)=k。 定義 給定圖 G=V， E， 若存在圖G1=V， E1， 并且 E1∩E=?和圖 V， E1∪ E是完全圖 ， 則 G1稱(chēng)為相對(duì)于完全圖的 G的補(bǔ)圖 ，簡(jiǎn)稱(chēng) G1是 G的補(bǔ)圖 ， 并記為 G1= 。 由同構(gòu)的定義可知 ， 不僅結(jié)點(diǎn)之間要具有一一對(duì)應(yīng)關(guān)系 ， 而且要求這種對(duì)應(yīng)關(guān)系保持結(jié)點(diǎn)間的鄰接關(guān)系 。 尋找一種簡(jiǎn)單有效的方法來(lái)判定圖的同構(gòu)，至今仍是圖論中懸而未決的重要課題。 定義 在一圈 (或回路 )中，若出現(xiàn)的每條邊(或弧 )恰好一次，稱(chēng)該圈 (或回路 )為簡(jiǎn)單圈 (或簡(jiǎn)單回路 )；若出現(xiàn)的每個(gè)結(jié)點(diǎn)恰好一次，稱(chēng)該圈 (或回路 )為基本圈(或基本回路 )。 因此它將結(jié)點(diǎn)集合給出一個(gè)劃分 ， 并且劃分中的每個(gè)元素形成一個(gè)誘導(dǎo)子圖；兩結(jié)點(diǎn)之間是可達(dá)的當(dāng)且僅當(dāng)它們屬于同一個(gè)子圖 ， 稱(chēng)這種子圖為圖 G的連通分圖 ， 圖 G的連通分圖的個(gè)數(shù) ， 記為ω(G)。 類(lèi)似地可定義圖 G的分離邊集 T；若圖 G的分離邊集 T={e}，則稱(chēng) e是 G的割邊或橋。 下面再給出一個(gè)判定一條邊是割邊的充要條件 。 定理 有向圖 G是強(qiáng)連通的 ?G中有一回路 ，它至少通過(guò)每個(gè)結(jié)點(diǎn)一次 。在所有這些鏈 (或路 )中，最短鏈 (或路 )的長(zhǎng)度稱(chēng)為結(jié)點(diǎn) u和 v之間的距離或短程線或測(cè)地線，記作du， v。 對(duì)資源的請(qǐng)求可能發(fā)生沖突。資源分配圖 Gt=Rt， E是有向圖，它表示了時(shí)間 t系統(tǒng)中資源分配狀態(tài)。 圖 圖的矩陣表示 為什么要用矩陣來(lái)表示圖 ？ 給定一個(gè)圖 G=V， E， 使用 G=V，E這種表示法存在兩個(gè)缺陷： 在圖比較復(fù)雜時(shí)不夠直觀； 不方便計(jì)算 。 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 由給定簡(jiǎn)單圖 G的鄰接矩陣 A可計(jì)算出矩陣 A的 l次冪，即 Al。An， 假 設(shè) 矩 陣 中 的 元 素 是 屬 于 布 爾 代 數(shù)B,?,?,ˉ,0,1的 B中元素 ， 其中 B={0,1}， 則稱(chēng)該矩陣為布爾矩陣 。 因此 ， 弧集合 E可解釋成 B中的二元關(guān)系 ， 而二元關(guān)系是可用矩陣表示的 ，通常稱(chēng)這種矩陣為關(guān)系矩陣 ， 其定義如下： 設(shè)兩個(gè)有限集合 X={x1,x2, 在圖的矩陣表示中 ， 除鄰接矩陣外 ，還有關(guān)聯(lián)矩陣 、 圈 （ 或回路 ） 矩陣 、 權(quán)矩陣等 ， 在此就不都予涉及了 ， 只是再給出權(quán)矩陣的概念以結(jié)束本小節(jié) 。 該算法的關(guān)鍵的一步是 (4)，它判定如果pik=1，將第 i行和第 k行的各對(duì)應(yīng)元素作布爾和或邏輯加后送到第 i行中去。 為了計(jì)算 A+或 P，自然可先依次求得 A(2)，A(3)， ,n。用歸納法可以證明 R+的關(guān)系矩陣是 = ? ? ?,有 A(r1) ? A=A(r) 要注意的是 Ar與 A(r)的差別。 下面定義兩個(gè)布爾矩陣 B與 C的運(yùn)算： 令 B和 C的布爾和、布爾積分別記為 B?C和BoC，其定義為 (B?C)ij=bij?cij (B ? C)ij= (bik?ckj) i,j=1,2,+An。為說(shuō)明此事實(shí)，今給出下面定理。 定義 給定簡(jiǎn)單圖 G=V， E， V={v1，v2， … ， vn}， V中的結(jié)點(diǎn)按下標(biāo)由小到大編序，則 n階方陣 A=(aij)稱(chēng)為圖 G的鄰接矩陣。ri， rj表示有向邊， ri， rj∈ E當(dāng)且僅當(dāng)程序pk∈ Qt已分配到資源 ri且等待資源 rj。這種情況稱(chēng)為處于死鎖狀態(tài)。 此外，要注意，即使 u與 v相互可達(dá)， du，v未必等于 dv， u。 定義 在簡(jiǎn)單有向圖中 ， 具有強(qiáng)連通性質(zhì)的極大子圖 ， 稱(chēng)為強(qiáng)分圖；具有單向連通性質(zhì)的極大子圖 ，稱(chēng)為單向分圖；具有弱連通性質(zhì)的極大子圖 ， 稱(chēng)為弱分
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1