【正文】 nected. ? ? ? ? ? 點連通度是多少 ? ? = 1 ? = 2 ? = 3 ? = 3 ? = 1 ? ? ? ? ? 邊連通度是多少 ? ? = 3 ? = 2 ? = 3 ? = 3 ? = 1 ? = 2 ? = 3 ? = 1 ? = 3 ? = 3 ? ? ? ? ? 定理 (Whitney公式 ) 對于任何無向圖 G, 有 ?(G) ? ?(G) ? ? (G). ? = 2 ? = 3 ? = 4 ? ? ? ? ? 二、 有向圖的連通性 ?在有向圖中 , 若從頂點 u 到 v 存在通路 , 則稱 u 可達 v, 記作 u ? v。 且無平行邊 . G = ?V1, V2, E? 互補頂點子集 : V1, V2. ? ? ? ? ? 例 9 二部圖 ? 同色頂點不相鄰 構成兩個互補頂點子集 因此是二部圖 . 與上圖同構的圖 ? ? ? ? ? 由定理 ，哪些是完 全二部圖？哪些圖是同構的？ 定理 . 無向圖 G=V, E 是二部圖當且僅當 G中無奇圈 . 完 ? ? ? ? ? 1. 非負性 : d(u, v) ? 0 (當且僅當 u = v 時 , 等號成立 ). 距離的性質 : 2. 對稱性 : d(u, v) = d(v, u). 3. 三角不等式 : d(u, v) + d(v, w) ? d(u, w). 完 ? ? ? ? ? 一、無向圖的關聯(lián)矩陣（對圖無限制） 定義 無向圖 G=V, E， |V|=n， |E|=m，令 mij 為 vi 與 ej的關聯(lián)次數(shù)，稱 (mij)n?m為 G 的關聯(lián)矩陣，記 為 M(G). 圖的矩陣表示 ? ? ? ? ? v1 v2 v4 v3 e1 e2 e3 e4 e 5 1 1 1 0 00 1 1 1 0()1 0 0 1 20 0 0 0 0MG?????????例 平行邊的列相同)4(2)3(), . . . ,2,1()()2(), . . . ,2,1(2)1(,11mmnivdmmjmjiijimj ijni ij??????????性質： ? ? ? ? ? ???????的終點為，不關聯(lián)與，的始點為jijijiijevevevm10,1有向圖的關聯(lián)矩陣（無環(huán)） 定義 有向圖 D=V,E，令 二、有向圖的關聯(lián)矩陣 則稱 ( mij )n?m為 D 的關聯(lián)矩陣，記為 M(D). ? ? ? ? ? ?? ???????????? ????jiijmjmj iijiijni ijmnivdmvdmmjm,1 110)3(,...,2,1),()1(),()1()2(),...,2,1(0)1((4) 平行邊對應的列相同 性質 v4 v1 v2 v3 e1 e2 e3 e4 e5 1 1 0 0 01 0 1 1 1()0 0 0 0 10 1 1 1 0MD?????????? ????? ? ? ? ? 定義 設有向圖 D=V,E, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令 ai j為頂點 vi 鄰接到頂點 vj 邊的條數(shù)，稱為 D 的鄰接矩陣，記作 A(D)，或簡記為 A. 三、有向圖的領接矩陣 ? ? ? ? ? v2 v1 v4 v3 1 2 1 00 0 1 0()0 0 0 10 0 1 0AD?????????????的回路數(shù)中長度為的通路數(shù)中長度為1)4(1)3(, . . . ,2,1),()2(, . . . ,2,1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij????????????????????? ? ? ? ? 推論 設 Bl=A+A2+…+ Al（ l?1），則 Bl中元素 為 D中長度為 l 的通路總數(shù)， )(lija)(liia??? ?ninjlija1 1)(??niliia1)(??? ?ninjlijb1 1)(??niliib1)(定理 設 A為有向圖 D 的鄰接矩陣， V={v1, v2, …, vn}為頂點集，則 A 的 l 次冪 Al（ l?1）中元素 為 D中 vi 到 vj長度為 l 的通路數(shù)，其中 為 vi到自身長度為 l 的回路數(shù)，而 為 D中長度小于或等于 l 的回路數(shù) 為 D中長度小于或等于 l 的通路數(shù) . 鄰接矩陣的應用 為 D 中長度為 l 的回路總數(shù) . ? ? ? ? ? 例 5 有向圖 D如圖所示，求 A, A2, A3, A4，并回答諸問題： (1) D 中長度為 1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？ (2) D 中長度小于或等于 4的通路為多少條？其中有多少條回路？ 實例 ? ? ? ? ? ????????????????????????????????????????????????????1004010410050001010310030104000110020102100300010101100101020001432AAAA(1) D中長度為 1的通路為 8條，其中有 1條是回路 . D中長度為 2的通路為 11條，其中有 3條是回路 . D中長度為 3和 4的通路分別為 14和 17條，回路分別 為 1與 3條 . (2) D中長度小于等于 4的通路為 50條，其中有 8條是回路 . 實例求解 ? ? ? ? ? 1,0,ijijvvp ????可 達否 則?????????????1101110111110001P定義 設 D = V, E 為有向圖 . V = { v1 , v2 , …, vn }, 令 四、有向圖的可達矩陣（無限制） 稱 (pij)n?n 為 D的可達矩陣，記作 P(D)，簡記為 P. 由于 ?vi?V， vi?vi，所以 P(D)主對角線上的元素全為 1. 由定義不難看出 , D 強連通當且僅當 P(D)為全 1矩陣 . 下圖所示有向圖 D 的可達矩陣為 ? ? ? ? ? 有向圖的鄰接矩陣與可達矩陣的關系？ 作業(yè)： 習題十四： 35， 39， 45 ? ? ? ? ? 無向圖的關聯(lián)矩陣 定義 無向圖 G=V, E， |V|=n， |E|=m，令 mij 為 vi 與 ej的關聯(lián)次數(shù)，稱 (mij)n?m為 G 的關聯(lián)矩陣，記 為 M(G). （對圖無限制） ? ? ? ? ? v1 v2 v4 v3 e1 e2 e3 e4 e 5 1 1 1 0 00 1 1 1 0()1 0 0 1 20 0 0 0 0MG?????????例 1( 1 ) 2 ( 1 , 2 , . . . , )niji m j m? ???性質： 1,( 2 ) ( ) ( 1 , 2 , . . . , )( 3 ) 2( 4 )mij ijijijm d v i nmm??????平 行 的 列 相 同完 , 作業(yè)： 習題十四： 21， 33，