【文章內(nèi)容簡介】 的情況下 ， 也記為 Kn。 無向完全圖 Kn的邊數(shù)為 = n(n1)，有向完全圖 Kn的邊數(shù)為 = n(n1)。 2nP2nC 122022/2/13 計算機學院 46/172 完全圖 1. 設 G＝ V,E為一個具有 n個結(jié)點的無向簡單圖 ， 如果 G中任一個結(jié)點都與其余 n1個結(jié)點相鄰接 ， 則稱 G為無向完全圖 ， 簡稱 G為完全圖 ， 記為 Kn。 2. 設 G＝ V,E為一個具有 n個結(jié)點的有向簡單圖 ， 若對于任意 u,v?V(u?v)， 既有有向邊u,v， 又有有向邊 v,u， 則稱 G為 有向完全圖 ， 在不發(fā)生誤解的情況下 ， 也記為 Kn。 無向完全圖 Kn的邊數(shù)為 = n(n1)，有向完全圖 Kn的邊數(shù)為 = n(n1)。 2nP2nC 122022/2/13 計算機學院 47/172 完全圖 1. 設 G＝ V,E為一個具有 n個結(jié)點的無向簡單圖 ， 如果 G中任一個結(jié)點都與其余 n1個結(jié)點相鄰接 ， 則稱 G為無向完全圖 ， 簡稱 G為完全圖 ， 記為 Kn。 2. 設 G＝ V,E為一個具有 n個結(jié)點的有向簡單圖 ， 若對于任意 u,v?V(u?v)， 既有有向邊u,v， 又有有向邊 v,u， 則稱 G為有向完全圖 ， 在不發(fā)生誤解的情況下 ， 也記為 Kn。 無向完全圖 Kn的 邊數(shù) 為 = n(n1)，有向完全圖 Kn的 邊數(shù) 為 = n(n1)。 2nP2nC 122022/2/13 計算機學院 48/172 補圖 ? 設 G＝ V， E為具有 n個結(jié)點的簡單圖 ,從完全圖 Kn中 刪去 G中的所有邊而得到的圖稱為 G相對于完全圖 Kn的補圖 ， 簡稱 G的 補圖 ， 記為 。 ? 這里 ， 當 G為有向圖時 ， 則 Kn為有向完全圖；當 G為無向圖時 ， 則 Kn為無向完全圖 。 ? 顯然 ， G與 互為補圖 ， 即 。 GG?GG2022/2/13 計算機學院 49/172 補圖 ? 設 G＝ V， E為具有 n個結(jié)點的簡單圖 ,從完全圖 Kn中刪去 G中的所有邊而得到的圖稱為 G相對于完全圖 Kn的補圖 ， 簡稱 G的補圖 ， 記為 。 ? 這里 ， 當 G為有向圖時 ， 則 Kn為有向完全圖；當 G為無向圖時 ， 則 Kn為無向完全圖 。 ? 顯然 ， G與 互為補圖 ， 即 。 GG?GG2022/2/13 計算機學院 50/172 例 2022/2/13 計算機學院 51/172 二部圖 設圖 G=V,E， 如果它的結(jié)點集可以劃分成兩個子集 X和 Y， 使得它的 每一條邊的一個關聯(lián)結(jié)點在 X中 ， 另一個關聯(lián)結(jié)點在 Y中 ， 則這樣的圖稱為 二部圖 。 設 |X|=n1， |Y|=n2。 如果 X中的每一個結(jié)點與 Y中的全部結(jié)點都鄰接 ， 則稱 G為完全二部圖 ，并記為 Kn1,n2。 2022/2/13 計算機學院 52/172 二部圖 設圖 G=V,E， 如果它的結(jié)點集可以劃分成兩個子集 X和 Y， 使得它的每一條邊的一個關聯(lián)結(jié)點在 X中 ， 另一個關聯(lián)結(jié)點在 Y中 ， 則這樣的圖稱為二部圖 。 設 |X|=n1， |Y|=n2。 如果 X中的每一個結(jié)點與 Y中的全部結(jié)點都鄰接 ， 則稱 G為 完全二部圖 ，并記為 Kn1,n2。 2022/2/13 計算機學院 53/172 圖的同構 a b c d a b c d a b c d a b c d 2022/2/13 計算機學院 54/172 定義 ?設兩個圖 G=V,E和 G′ =V′ ,E′ ， 如果存在雙射函數(shù) g： V→V ′ ， 使得對于任意的 e=(vi,vj) （ 或者 vi,vj ） ∈ E 當且僅當 e′ ＝(g(vi),g(vj)) （ 或者 g(vi),g(vj)） ∈ E′， 則稱 G與 G′同構 ， 記為 G≌G ′。 （ 同構是指兩個圖的邊 11對應 ） ?圖的同構關系是圖集上的等價關系 。 2022/2/13 計算機學院 55/172 定義 ?設兩個圖 G=V,E和 G′ =V′ ,E′ ， 如果存在雙射函數(shù) g： V→V ′ ， 使得對于任意的 e=(vi,vj) （ 或者 vi,vj） ∈ E當且僅當 e′ ＝ (g(vi),g(vj)) （ 或者 g(vi),g(vj)） ∈ E′， 則稱 G與 G′同構 ，記為 G≌G ′。 （ 同構是指兩個圖的邊 11對應 ） ?圖的同構關系是圖集上的等價關系 。 2022/2/13 計算機學院 56/172 例 G1≌ G2： a→v 1， b→v 2， c→v 3， d→v 4， e→v 5 a b d c e v4 v1 v3 v2 v5 G1 G2 a b d c e G3 G4 v4 v1 v3 v2 v5 G3≌G 4： a→v 1， b→v 4，c→v 2， d→v 5，e→v 3； 2022/2/13 計算機學院 57/172 例 G5≌ G6： a→v 1， b→v 2， c→v 3， d→v 4， e→v 7， f→v 6， g→v 9， h→v 8， i→v 5， j→v 10 a b d c e f g j h i G5 G6 v8 v1 v10 v2 v7 v3 v4 v5 v6 v9 彼得森圖 2022/2/13 計算機學院 58/172 兩個圖同構的必要條件 1) 結(jié)點數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結(jié)點數(shù)相同。 注意：這三個條件并不是充分條件。例如下面兩個圖滿足這三個條件，但它們不同構。 2022/2/13 計算機學院 59/172 兩個圖同構的必要條件 1) 結(jié)點數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結(jié)點數(shù)相同。 注意 ：這三個條件并不是充分條件。例如下面兩個圖滿足這三個條件，但它們不同構。 y x u v x y v u 2022/2/13 計算機學院 60/172 兩個圖同構的必要條件 1) 結(jié)點數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結(jié)點數(shù)相同。 注意 ：這三個條件并不是充分條件。例如下面兩個圖滿足這三個條件，但它們不同構。 y x u v x y v u 若圖的結(jié)點可以任意挪動位置，而邊 是完全彈性的，只要在不拉斷的條件下， 一個圖可以變形為另一個圖，那么這兩個 圖是同構的。 如下圖所示： 2022/2/13 計算機學院 61/172 a b c d a b c d a b d c e f v1 v2 v3 v4 v5 v6 G7 G8 G7與 G8不同構 為什么？ 例 2022/2/13 計算機學院 62/172 a b c d a b c d a b d c e f v1 v2 v3 v4 v5 v6 G7 G8 G7與 G8不同構 為什么？ 例 2022/2/13 計算機學院 63/172 a b c d a b c d a b d c e f v1 v2 v3 v4 v5 v6 G7 G8 G7與 G8不同構 為什么？ 例 這說明上述三個條件僅僅是必要而不充分 2022/2/13 計算機學院 64/172 習題 ?P206 3(1)(4)、 8 2022/2/13 計算機學院 65/172 167。 道路與回路 2022/2/13 計算機學院 66/172 167。 道路與回路 ?定義 圖 G＝ V,E中 結(jié)點和邊 相繼交錯出現(xiàn)的序列 P=v0e1v1e2v2… ekvk， 若 P中邊 ei的兩端點是 vi1和 vi（ G是有向圖時要求 vi1與 vi分別是 ei的始點和終點 ， 即方向一致 。 ） ， 則稱 P為結(jié)點 v0到結(jié)點 vk的 道路 。 簡記為 〈 v0， vk〉 。 ?v0和 vk分別稱為此道路的起點和終點 ， 統(tǒng)稱為道路的端點 。 其余結(jié)點稱為內(nèi)部結(jié)點 。 ?道路中邊的數(shù)目 k稱為此道路的長度 。 ?如 P=v0， 稱為零道路 ， 其長度為零 。 ?若 v0≠vk， 稱為開道路 ， 否則稱為閉道路 。 2022/2/13 計算機學院 67/172 167。 道路與回路 ?定義 圖 G＝ V,E中結(jié)點和邊相繼交錯出現(xiàn)的序列 P=v0e1v1e2v2… ekvk， 若 P中邊 ei的兩端點是 vi1和 vi（ G是有向圖時要求 vi1與 vi分別是 ei的始點和終點 ， 即方向一致 。 ） ， 則稱 P為結(jié)點 v0到結(jié)點 vk的道路 。 簡記為 〈 v0， vk〉 。 ?v0和 vk分別稱為此道路的 起點 和 終點 ， 統(tǒng)稱為道路的 端點 。 其余結(jié)點稱為 內(nèi)部結(jié)點 。 ?道路中 邊的數(shù)目 k稱為此 道路的長度 。 ?如 P=v0， 稱為 零道路 ， 其長度為零 。 ?若 v0≠vk， 稱為 開道路 ， 否則稱為 閉道路 。 2022/2/13 計算機學院 68/172 簡單道路與基本道路 ?若道路中的所有邊 e1， e2， … ， ek（ 有向邊 ）互不相同 ， 則稱此道路為 簡單道路 ；閉的簡單道路稱為 回路 。 ?若道路中的所有結(jié)點 v0， v1， … ， vk互不相同（ 從而所有邊互不相同 ） ， 則稱此道路為基本道路；若回路中除 v0＝ vk外的所有結(jié)點 v0，v1， … ， vk1互不相同 （ 從而所有邊互不相同 ） ， 則稱此回路為基本回路或者圈 。 ?基本道路 (或基本回路 )一定是簡單道路 (或簡單回路 )， 但反之則不一定 。 為什么 ？ 2022/2/13 計算機學院 69/172 簡單道路與基本道路 ?若道路中的所有邊 e1， e2， … ， ek（ 有向邊 ）互不相同 ， 則稱此道路為簡單道路；閉的簡單道路稱為回路 。 ?若道路中的所有結(jié)點 v0， v1， … ， vk互不相同（ 從而所有邊互不相同 ） ， 則稱此道路為 基本道路 ；若回路中除 v0＝ vk外的所有結(jié)點 v0，v1， … ， vk1互不相同 （ 從而所有邊互不相同 ） ， 則稱此回路為 基本回路 或者 圈 。 ?基本道路 (或基本回路 )一定是簡單道路 (或簡單回路 )， 但反之則不一定 。 為什么 ？ 2022/2/13 計算機學院 70/172 簡單道路與基本道路 ?若道路中的所有邊 e1， e2， … ， ek（ 有向邊 ）互不相同 ， 則稱此道路為簡單道路；閉的簡單道路稱為回路 。 ?若道路中的所有結(jié)點 v0， v1， … ， vk互不相同（ 從而所有邊互不相同 ） ， 則稱此道路為基本道路；若回路中除 v0＝ vk外的所有結(jié)點 v0，v1， … ， vk1互不相同 （ 從而所有邊互不相同 ） ， 則稱此回路為基本回路或者圈 。 ?基本道路 (或基本回路 )一定是簡單道路 (或簡單回路 )， 但反之則不一定 。 為什么 ？ 2022/2/13 計算機學院 71/172 例 在圖 G1中： v1e1v2e2v3e3v4e4v5e7v6： 基本道路 v1e1v2e5v4e3v3e2v2e9v6: 簡單道路 V2e10v2e2v3e3v4e5v2: 回路 V2e2v3e3v4e5v2: 圈 e1 v6 v1 v4 v3 v2 G1 e2 e5 e3 e9 e7 e6 e8 v5 e4 v7 e10 2022/2/13 計算機學院 72/172 G2 v4 v1 v3 v2 v5 e1 e2 e3 e4 e5 e7 e8 e6 e9 在圖 G2中： v1e2v5e3v2e6v4e8v3e9v3e5v2e1v1： 回路 v5e3v2e4v5： 圈 2022/2/13 計算機學院 73/172 注： 1) 在 不 會 引 起 誤 解 的 情 況 下 ， 一 條 道 路v0e1v1e2v2… envn也 可以用邊的序列 e1e2… en來表示 ， 這種表示方法對于有向圖來說較為方便 。 2) 在簡單圖中 ， 一條道路 v0e1v1e2v2… envn也可以用結(jié)點的序列 v0v1v2… vn來表示 。 2022/2/13 計算機學院 74/172 注： 1) 在 不