【正文】 ??????jijiij evevm不關聯(lián)若關聯(lián)若01完全關聯(lián)矩陣： 73 圖的矩陣表示 例： 從關聯(lián)矩陣研究圖形的性質(zhì) ： 1） M(G)中每列中有且僅有兩個 1，對應每邊關聯(lián)的兩個結(jié)點 2）每行中元素的和為對應結(jié)點的度數(shù) 3）元素全為 0的行對應結(jié)點為孤立結(jié)點 4）平行邊對應的列相同 5）結(jié)點 /邊編序不同，對應完全關聯(lián)矩陣只有行序 /列序的差別 v3v4e4v2v1e3e5e6e2e1v5e1 e2 e3 e4 e5 e6 v1 1 1 0 0 1 1 v2 1 1 1 0 0 0 v3 0 0 1 1 0 1 v4 0 0 0 1 1 0 v5 0 0 0 0 0 0 73 圖的矩陣表示 （ 2） G為有向圖 G=V,E， ， p*q階矩陣 M(G)=(mij)為 G的完全關聯(lián)矩陣，其中： },{ 21 pvvvV ?? },{ 21 qeeeE ??1 是 的 起 點－ 1 是 的 終 點0 若 不 關 聯(lián)iji j i jijvem v eve???? ????例： e1 e2 e3 e4 e5 e6 e7 v1 1 0 0 0 1 1 1 v2 1 1 0 0 0 0 0 v3 0 1 1 0 0 1 0 v4 0 0 1 1 0 0 1 v5 0 0 0 1 1 0 0 v5v4v3v2v1e7e5e6e4e3e2e173 圖的矩陣表示 有向圖完全關聯(lián)矩陣的一些性質(zhì) ： 1）每一列中一個值為 1，一個為 1，對應圖中的一條有向邊 2）把一行中的值為 1的元素相加，得到頂點的出度，把值為 1的元素相加，得到頂點的入度 3）一行中元素全為 0，對應孤立結(jié)點 4）平行邊對應的列相同 5）結(jié)點 /邊編序不同，對應完全關聯(lián)矩陣只有行序 /列序的 差別 73 圖的矩陣表示 完全關聯(lián)矩陣中的行相加運算： 有向圖：對應分量普通加法運算 無向圖：對應分量模 2加法運算 行相加運算相當于 G中對應 結(jié)點的合并 1i r j raa? ? ?說明 vi和 vj中只有一個結(jié)點是邊 er的端點，合并后仍是 er的端點 0i r j raa??有兩種情況： 1） vivj都不是 er的端點； 2） vivj都是 er的端點，合并后刪去自回路，對應邊消失 73 圖的矩陣表示 例 1：左圖合并 v4， v5后得到右圖，對應關聯(lián)矩陣為： e1 e2 e3 e4 e5 e6 e7 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 v1 v2 v3 v4,5 M(G) M(G’) V4V1V2V3V5e1e2e3e4e5e6e7V3e4V2V1V4 , 5e2e3e5e7e673 圖的矩陣表示 例 2：左圖合并 v2， v3且刪去自回路后得到右圖，關聯(lián)矩陣為： e1 e2 e3 e4 e5 e6 e7 e8 e9 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 v1 v2,3 v4 v5 v6 M(G) M(G’) 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 V2e3V3e7e8e9e4V6V1V4e1e2e6e5V5V1V2 , 3V6e2e7e8e9e1e4e5e6V4V573 圖的矩陣表示 例：計算右圖對應的完全關聯(lián)矩陣的秩。 由 歸 納 假 設 法 可 得 下 面 定 理 ：i j i kk j i jni j i k k jkv v v vv v v va a a A G i j????定理： A(G)是圖 G的鄰接矩陣，則 (A(G))l中的 i行， j列元素 aij(l)等于 G中 聯(lián)結(jié) vi與 vj的長度為 l的路的數(shù)目 在實際問題中，常需要考慮到節(jié)點之間是否存在路的問題。表 示 從 到 的 長 度 為 2 的 回 路 的 數(shù) 目 。 則 從 結(jié) 點 到 的 長 度 為 2 的 路的 數(shù) 目 為 ：nj i j in n j ik kjkij n nij i jii i ia a a a a a aA G i j A G aa v va v v??? ? ? ? ? ? ? ???1 1 2 212 2 ( 2 )( 2 )( 2 ) 正 好 為 ( ( ) ) 中 第 行 ， 第 列 的 元 素 ， 記 ( ( ) ) ( ) 。置換等價 是 n階布爾矩陣集合上的等價關系 對于有向圖，按照結(jié)點的不同次序?qū)懗龅泥徑泳仃囀侵脫Q等價的。 得證 第七章 圖論 ? 圖的基本概念 ? 路與回路 ? 圖的矩陣表示 ? 歐拉圖與哈密爾頓圖 73 圖的矩陣表示 1 與 鄰 接0 與 不 鄰 接 或 =??? ???ijijijvvav v i j設 G=V, E是一個簡單圖， V={v1, v2,…, vn} 是 G的 n個結(jié)點， 則 n階方陣 A(G)=(aij)稱為 G的鄰接矩陣 。 “ ? ”： 若不存在回路經(jīng)過 G中的所有結(jié)點，則必有一 回路不包含某個結(jié)點 v，且 v與回路上的各個結(jié)點不是相互可 達，矛盾！ 得證 72 路與回路 （ 2） 強分圖 ：具有強連通性質(zhì)的極大子圖 單側(cè)分圖 ：具有單側(cè)連通性質(zhì)的極大子圖 弱分圖 ：具有弱連通性質(zhì)的極大子圖 定理： 有向圖中的每個結(jié)點位于且只位于一個強分圖中 證明 ： 1）對于任意結(jié)點 v， G中所有與 v相互可達的結(jié)點的集合 S即為 G的一個強分圖，即有每個結(jié)點都位于一個強分圖中； 2）假設 v位于兩個不同的強分圖 S1， S2中，則 v與 S1， S2中 的每個結(jié)點都相互可達，可知 S1， S2中的所有結(jié)點通過 v都相互 可達。 可達性是否為等價關系？ ? 自反性，滿足 ? 傳遞性，滿足 ? 對稱性，不滿足（圖中e可達 g， g不可達 e) 不是等價關系 ehgf72 路與回路 距離 ： u可達 v， u和 v間的 最短路的長度 ，記為 du,v 若 u到 v不可達， 通常 記 du,v=∞ 圖的直徑 ： D=max du,v ? du,v≥0 ? du,u=0 ? du,v+dv,w≥du,w ? u， v彼此可達， du,v不一定等于 dv,u （如右圖中 de, f=1, df, e=2） 距離的概念對無向圖同樣適用 在無向圖中， du,v=dv,u，記為 d(u, v) ehgf72 路與回路 （ 1） 強連通 ：任意兩個結(jié)點互相可達 單側(cè)連通 ：任意兩個結(jié)點之間，至少有一個結(jié)點到另一個結(jié)點是可達的 弱連通 ：略去邊的方向，得到的無向圖是連通的 弱連通 單側(cè)連通 強連通 72 路與回路 定理 ：一個有向圖是強連通的，當且僅當 G中一個回路，它 至少包含每個結(jié)點一次。???? ?