【文章內(nèi)容簡(jiǎn)介】 與 G2是同構(gòu)的，記作 : G1?G2 ? ? ? ? ? G = ?V, E? = ?{a, b, c, d}, {(a, b), (a, d), (b, c), (b, d), (c, d)}?. G39。 = ?V39。, E39。? = ?{a39。, b39。, c39。, d39。}, {(a39。, b39。), (a39。, d39。), (b39。, c39。), (b39。, d39。), (c39。, d39。)}?. G39。 f : V? V39。 a ? a39。 b ? b39。 c ? c39。 d ? d39。 G d a b c c39。 d39。 a39。 b39。 G ? G39。. 同構(gòu) 是在兩個(gè)圖的頂點(diǎn)之間建立的一一對(duì)應(yīng) , 使得頂點(diǎn)的鄰接情況是相同的 . ? 圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱性和傳遞性 . 下列各圖彼此同構(gòu) , 叫做 彼得松圖 . (1) (2) (3) 彼得松圖 / Petersen39。s graph 下列各圖彼此都不同構(gòu) . (4) (5) (6) 容易看出它們同構(gòu)嗎 ? 這兩個(gè)呢? 圖同構(gòu)的判別 尚未找到判斷圖同構(gòu)的好算法 . 能找到多條圖同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l 件： 階數(shù)相同；邊數(shù)相同； 度數(shù)列相同；對(duì)應(yīng)頂點(diǎn) 的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同， … … 若破壞必要條件，則兩圖不同構(gòu) 判斷兩個(gè)圖同構(gòu)是個(gè)難題 例 （ 1）無(wú)向完全圖 /plete graph 每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的無(wú)向簡(jiǎn)單圖，記作 Kn. K1 K2 K3 K4 K5 K6 完全圖 ( 1 ) ,2nnm ?? 1n?? ? ? ? Why? ? ? ? ? ? （ 2）有向完全圖 /plete digraph 每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的有向簡(jiǎn)單圖 . 1階 2階 3階 4階 1),1(2),1( ?????????? ?? nnnnm ??解 (1) ??d(v) = 2?3 = 6, ? ? 4 ? 1 = 3, ?度數(shù)列滿足 d1 + d2 + d3 + d4 = 6, 0 ? di ? 3, di 中有偶數(shù)個(gè)奇數(shù) . 可能的情況 : (a) 3, 1, 1, 1。 (b) 2, 2, 1, 1。 (c) 2, 2, 2, 0 (2) 3, 1, 1, 1 (1) 2, 2, 1, 1 (3) 2, 2, 2, 0 K4 例 (1) 畫(huà)出 4 階 3 條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖 . (2) 畫(huà)出 3 階 2 條邊的所有非同構(gòu)的有向簡(jiǎn)單圖 . ?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)的簡(jiǎn)單圖 , 這問(wèn)題目前還沒(méi)解決 . (2) 畫(huà)出 3 階 2條邊的所有非同構(gòu)的有向簡(jiǎn)單圖 . 因?yàn)? (n ? 1) + (n ? 2) + … + 2 + 1 = n(n ? 1)/2, 也因?yàn)? Cn2 = n(n ? 1)/2. 還因?yàn)? Kn 每個(gè)頂點(diǎn)的度數(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è)： 習(xí)題十四： 1（前兩小問(wèn)）， 8， 12， 20 ? ? ? ? ? 定義： 圖中前后關(guān)聯(lián)的頂點(diǎn)與邊的 交替序列 叫做 通路 ? = v0e1v1e2… elvl, 其中 ei 關(guān)聯(lián)于 vi ?1 和 vi. 始點(diǎn) , 終點(diǎn) , 長(zhǎng)度 l. e6 v1 v2 v3 e3 e1 e4 e5 e2 e7 v4 G 1. 路的定義 ? ? ? ? ? ?簡(jiǎn)單路 : “沿途 ”邊不重復(fù) . ?初級(jí)路 : 點(diǎn)不重復(fù) , 因而邊也不重復(fù) . ?回路 : 始點(diǎn)與終點(diǎn)相同 . 簡(jiǎn)單回路 : 邊不重復(fù) . 初級(jí)回路 或 圈 : 點(diǎn)不重復(fù) . ?初級(jí)的一定是簡(jiǎn)單的 , 反之不然 . 簡(jiǎn)單路 初級(jí)路 ? ? ? ? ? ?復(fù)雜通路 ,復(fù)雜回路 : 有邊重復(fù) . ?有向圖中 , 通路 , 回路及其分類與上面類似 , 但要求 沿途 有向邊方向一致 . 復(fù)雜通路 . l = 6. 簡(jiǎn)單通路 , l = 4. 初級(jí)路 , l = 3. 復(fù)雜回路 , l = 5. 圈 (初級(jí)回路 ), l = 3. ? ? ? ? ? 2. 路的分類 路 復(fù)雜路 (邊重復(fù) ) 簡(jiǎn)單路 (邊不重，跡 ) 初級(jí) 路 ( 點(diǎn)不重 ) 非初級(jí)路 (點(diǎn)重復(fù) ) u v 頂點(diǎn) u 到 v 有 7 條初級(jí)路 , 有無(wú)窮多條復(fù)雜路 . 有 7+2=9 條簡(jiǎn)單路 , ? ? ? ? ? 關(guān)于圈的說(shuō)明: 長(zhǎng)為 1 的圈 長(zhǎng)為 2 的圈 圈長(zhǎng)是 3 復(fù)雜回路 簡(jiǎn)單回路 初級(jí)回路 (圈 ) ?長(zhǎng)為 1 的圈是環(huán) . ??無(wú)向圖中 , 長(zhǎng)為 2 的圈是一對(duì)平行邊 . ???簡(jiǎn)單無(wú)向圖中 , 圈的長(zhǎng)度至少是 3. 圍長(zhǎng) 。 周長(zhǎng) 奇圈 ,偶圈 . ? ? ? ? ? (2) 頂點(diǎn)排列順序不同的圈是不同的 . K3中有 6 個(gè)不同的圈 , 它們相互同構(gòu) , 圈長(zhǎng)都是 3. (1) Kn (n ? 3)中有幾個(gè)不同構(gòu)的圈 ? (2) K3 中有幾個(gè)在定義意義下不同的圈 ? K5 解 (1) 長(zhǎng)度相同的圈是同構(gòu)的 , 長(zhǎng)度不同的圈是不同構(gòu)的 . Kn (n ? 3)中含長(zhǎng)度為 3, 4, …, n 的圈 , 故有 n ? 2 個(gè)不同構(gòu)的圈 . a c b a c b a c b a c b a c b a c b 例 例 ? ? ? ? ? u v w 定理 在 n 階圖中 , 若從頂點(diǎn) u 到 v 存在通路 , 則從 u 到 v 存在長(zhǎng)度小于等于 (n ? 1) 的通路 . 證 設(shè) ? 是從 u 到 v 的路中長(zhǎng)度最小的一條 (因?yàn)樽匀粩?shù)的良序性 , 這個(gè)最小長(zhǎng)度是存在的 ), 則 ? 一定是初級(jí)路 (點(diǎn)不重復(fù) ), 沿途最多有 n 個(gè)點(diǎn) , 故 ? 的長(zhǎng)度 ? (n ? 1). ? 3. 關(guān)于路的定理 推論 在 n 階圖中 , 若從頂點(diǎn) u 到 v 存在通路 , 則從 u 到 v 存在長(zhǎng)度小于等于 (n ? 1) 的初級(jí)通路（路徑） . ? ? ? ? ? 定理 在 n 階圖中 , 若存在 v 到自身的回路 , 則一定存在 v 到自身長(zhǎng)度 ? n 的回路 . 證 考慮 v 到自身 的回路中長(zhǎng)度最小的一條 , 除始點(diǎn)和終點(diǎn)外 , 沿途點(diǎn)不重復(fù) , 最多有 n 個(gè)點(diǎn) . 推論 在 n 階圖中 , 若存在 v 到自身的回路 , 則一定存在 v 到自身長(zhǎng)度 ? n 的初級(jí)回路（圈） . ? ? ? ? ? 簡(jiǎn)單圖 G中最短的圈的長(zhǎng)度叫做 圍長(zhǎng) g(G)。 ?圍長(zhǎng)比周長(zhǎng)容易確定些 ??周長(zhǎng)有時(shí)候不容易確定 圍長(zhǎng)是 3, 周長(zhǎng)是 8. 圍長(zhǎng) /girth, 周長(zhǎng) /circumference 圍長(zhǎng) = 4, 周長(zhǎng) = 12. 最長(zhǎng)的圈的長(zhǎng)度叫做 周長(zhǎng) c(G),. ? ? ? ? ? （ 1） 頂點(diǎn)之間的連通關(guān)系 1. 無(wú)向圖 G = ?V, E? 中 , 若頂點(diǎn) u 到 v 存在通路 , 則稱 u 和 v 是 連通的 , 記作 u ~ v. 規(guī)定每個(gè)頂點(diǎn) v ~ v. 2. ~ 是 V 上的等價(jià)關(guān)系 R={u,v| u,v ?V且 u?v} , 把 V 劃分成 k 個(gè)等價(jià)類 , 把 G 分成 k 個(gè) 連通分支 , 連通分支數(shù) p(G) = k. 一、無(wú)向圖的連通性 ? ? ? ? ? (2) G的連通性與連通分支 ① 若 ?u,v?V， u?v，則稱 G連通