【正文】 不同類的頂點都相鄰 。 規(guī)定 u 總是可達自身的 . 若 u 與 v 相互可達 , 記作 u ? v. ?? 與 ? 都是 V 上的關(guān)系 , 其中 ? 是等價關(guān)系 , 而 ? 未必是偏序關(guān)系 (因為它未必是反對稱的 ). 稱 u 到 v 長度最小的通路為 v 到 v 的 短程線 , 短程線的長度為 u 到 v 的 距離 d?u, v?. ? d?u, v? 滿足非負性和三角不等式 , 但不滿足對稱性 . ? ? ? ? ? 有向圖 D 稱為 ?弱連通的 , 若 D 的基圖是連通圖 . ?單連通的 , 若任意兩個頂點中至少一個可達另一個 . ?強連通的 , 若任意兩個頂點相互可達 . ? 強連通必定單連通 , 單連通必定弱連通 . shortest path, geosesy, distance, weakly connected, unilaterally connected, strongly connected. 強連通 單連通 弱連通 ? ? ? ? ? 弱連通 哪類連通 ? ? ? ? ? ? 強連通圖與單向連通圖的判別 定理 有向圖 D 是強連通圖當且僅當 D 中存在經(jīng)過每個頂點至少一次的回路 . 強連通 單連通 弱連通 定理 有向圖 D 是單向連通圖當且僅當 D 中存在經(jīng)過每個頂點至少一次的通路 . ? ? ? ? ? 定理 有向圖 D 是強連通圖當且僅當 D 中存在經(jīng)過每個頂點至少一次的回路 . 證 充分性顯然 . 下面證明必要性 . v1 v2 v3 vn ?1 ?2 ?3 ?n ?n ? 1 vn?1 ? = ?1 ? ?2 ? … ? ?n?1 ? ?n 必要性 : 由 D 的強連通性知 , vi ? vi+1, i = 1, 2, …, n ? 1, 設(shè) ?i 為 vi 到 vi+1 的通路 . 又因為 vn ? v1, 設(shè) ?n 為 vn 到 v1 的通路 , 則 ?1, ?2, …, ?n?1, ?n 相連所得的回路 ? 經(jīng)過 D 的 全部頂點 . ? ? ? ? ? 三、極大路徑法 設(shè) ?l 為無向圖 G 中一條路徑 , 若該路徑的某個端點與路徑外的頂點相鄰 , 就將它們擴到路徑中來 , 繼續(xù)這一過程直到路徑的兩個端點不與路徑外的頂點相鄰 . 所得路徑 ?l + k 叫做極大路徑 . 極大路徑法 : 利用極大路徑證明圖具有某些性質(zhì) . ?l ?有限圖中極大路徑一定存在 . ?l + k ? ? ? ? ? 例 8 設(shè)無向簡單圖 G 的最小度 ? (G) ? 3. 證明 G 中存在長度 ? 4 的圈 . 證 設(shè) G 是連通圖 (否則考慮其任一連通分支 ). 任取 一條 極大路徑 ? = v0v1… vl. 因 d(v0) ? ? ? 3, 故 ? 上至少有 3 個頂點與 v0 相鄰 : v1, vk, vt (k t), 則 v0v1… vk… vtv0 為一個圈且長度 ? 4. QED 無長為 4 的圈 ? = 2 v0 v1 vk vt vl 有長為 4的圈 ? ? 3 無長為 3的路徑 ? = 1 ? ? ? ? ? r 部圖 : 頂點集劃分成 r 類 , 同類頂點不相鄰 . 4 部圖 2 部圖 r 部圖 /rpartite graph, 二部圖 /bipartite graph 二部圖 ? ? ? ? ? 完全 r 部圖 : 頂點集劃分成 r 類 , 同類頂點不相鄰 。|?E39。|?V39。 是 G 的 邊割集 (簡稱 割集 ). 若 E39。39。 ? E39。) p(G), ② (極小性 )對任意的 E39。 = {v} 只含一個頂點 , 則稱 v 為 割點 . vertex cutset, cutvertex, edge cutset, cutedge (bridge). 定義 設(shè)無向圖 G = ?V, E?, 若存在 E39。 是 G 的 點割集 。39。 ? V39。) p(G), ② (極小性 )對任意的 V39。) p(G). ? ? ? ? ? 定義 設(shè)無向圖 G = ?V, E?, 若存在 V39。 ?圍長比周長容易確定些 ??周長有時候不容易確定 圍長是 3, 周長是 8. 圍長 /girth, 周長 /circumference 圍長 = 4, 周長 = 12. 最長的圈的長度叫做 周長 c(G),. ? ? ? ? ? （ 1） 頂點之間的連通關(guān)系 1. 無向圖 G = ?V, E? 中 , 若頂點 u 到 v 存在通路 , 則稱 u 和 v 是 連通的 , 記作 u ~ v. 規(guī)定每個頂點 v ~ v. 2. ~ 是 V 上的等價關(guān)系 R={u,v| u,v ?V且 u?v} , 把 V 劃分成 k 個等價類 , 把 G 分成 k 個 連通分支 , 連通分支數(shù) p(G) = k. 一、無向圖的連通性 ? ? ? ? ? (2) G的連通性與連通分支 ① 若 ?u,v?V， u?v，則稱 G連通 ② V/R={V1,V2,…, Vk}， ? 連通圖 , 非連通圖 (分離圖 ). (a) 連通 (b)不連通 p = 1 p = 3 通分支，其個數(shù) p(G)=k (k?1)； 稱 G[V1], G[V2], …, G[Vk] 為連 k=1， G 連通 ? ? ? ? ? 不連通 . 3個連通分支 . 不連通 . 2 個連通分支 . 連通否 ? 幾個連通分支 ? 連通 . 1 個連通分支 . ? ? ? ? ? ?無向圖中任意兩個頂點 u, v 間長度最小的通路叫做 u, v 之間的 短程線 , 短程線的長度 d(u, v) 稱為 u, v 之間的 距離 . 當 u, v 不連通時 , 規(guī)定 d(u, v) = ?. shortest path (geodesia), distance v1 v2 v3 v4 v5 d(v1, v1) = 0, d(v1, v2) = 1, d(v1, v3) = 2, d(v3, v4) = 3. 距離的性質(zhì) ? n 階圖中 , 兩點間距離可能的取值 : 0, 1, 2, …, n ? 1, ?. ? ? ? ? ? （ 3） . 無向圖的連通度 問題 如何衡量無向圖的連通的程度 ? ? ? ? ? ? 衡量的連通程度的兩個指標 : 點連通度 : 為了破壞連通性 , 至少要刪除多少個點 ? 邊連通度 : 為了破壞連通性 , 至少要刪除多少條邊 ? “破壞連通性”就是“變得較不連通” : p(G ? V39。 (c) 2, 2, 2, 0 (2) 3, 1, 1, 1 (1) 2, 2, 1, 1 (3) 2, 2, 2, 0 K4 例 (1) 畫出 4 階 3 條邊的所有非同構(gòu)的無向簡單圖 . (2) 畫出 3 階 2 條邊的所有非同構(gòu)的有向簡單圖 . ?d(v) = 2?2 = 4, ?+, ?? ? 4 ? 1 = 3. 度數(shù)列 1, 2, 1 2, 2, 0 入度列 0, 1, 1 0, 2, 0 1, 0, 1 1, 1, 0 出度列 1, 1, 0 1, 0, 1 0, 2, 0 1, 1, 0 ① ② ③ ④ ① ② ③ ④ ? 給定 n, m??+, 構(gòu)造出 n 階 m 條邊的所有非同構(gòu)的簡單圖 , 這問題目前還沒解決 . (2) 畫出 3 階 2條邊的所有非同構(gòu)的有向簡單圖 . 因為 (n ? 1) + (n ? 2) + … + 2 + 1 = n(n ? 1)/2, 也因為 Cn2 = n(n ? 1)/2. 還因為 Kn 每個頂點的度數(shù)是 n ? 1, 度數(shù)之和為 n(n ? 1). 根據(jù)握手定理 , 邊數(shù)是 n(n ? 1)/2. K5 例如 , |E(K5)| = 4 + 3 + 2 + 1 Kn 有 n(n?1)/2 條邊 = C52 = n(n ? 1)/2 = 10. 作業(yè)： 習題十四： 1（前兩小問）， 8， 12， 20 ? ? ? ? ? 定義： 圖中前后關(guān)聯(lián)的頂點與邊的 交替序列 叫做 通路 ? = v0e1v1e2… elvl, 其中 ei 關(guān)聯(lián)于 vi ?1 和 v