【正文】 個結點的有向簡單圖 ， 若對于任意 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/63 補圖 ? 設 G＝ V， E為具有 n個結點的簡單圖 ,從完全圖 Kn中 刪去 G中的所有邊而得到的圖稱為 G相對于完全圖 Kn的補圖 ， 簡稱 G的 補圖 ， 記為 。 ? 這里 ， 當 G為有向圖時 ， 則 Kn為有向完全圖；當 G為無向圖時 ， 則 Kn為無向完全圖 。 ? 顯然 ， G與 互為補圖 ， 即 。 GG?GG2022/2/13 計算機學院 48/63 補圖 ? 設 G＝ V， E為具有 n個結點的簡單圖 ,從完全圖 Kn中刪去 G中的所有邊而得到的圖稱為 G相對于完全圖 Kn的補圖 ， 簡稱 G的補圖 ， 記為 。 ? 這里 ， 當 G為有向圖時 ， 則 Kn為有向完全圖；當 G為無向圖時 ， 則 Kn為無向完全圖 。 ? 顯然 ， G與 互為補圖 ， 即 。 GG?GG2022/2/13 計算機學院 49/63 例 2022/2/13 計算機學院 50/63 二部圖 設圖 G=V,E， 如果它的結點集可以劃分成兩個子集 X和 Y， 使得它的 每一條邊的一個關聯(lián)結點在 X中 ， 另一個關聯(lián)結點在 Y中 ， 則這樣的圖稱為 二部圖 。 設 |X|=n1， |Y|=n2。 如果 X中的每一個結點與 Y中的全部結點都鄰接 ， 則稱 G為完全二部圖 ，并記為 Kn1,n2。 2022/2/13 計算機學院 51/63 二部圖 設圖 G=V,E， 如果它的結點集可以劃分成兩個子集 X和 Y， 使得它的每一條邊的一個關聯(lián)結點在 X中 ， 另一個關聯(lián)結點在 Y中 ， 則這樣的圖稱為二部圖 。 設 |X|=n1， |Y|=n2。 如果 X中的每一個結點與 Y中的全部結點都鄰接 ， 則稱 G為 完全二部圖 ，并記為 Kn1,n2。 2022/2/13 計算機學院 52/63 圖的同構 a b c d a b c d a b c d a b c d 2022/2/13 計算機學院 53/63 定義 ?設兩個圖 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 計算機學院 54/63 定義 ?設兩個圖 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/63 例 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 計算機學院 56/63 例 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 計算機學院 57/63 兩個圖同構的必要條件 1) 結點數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結點數(shù)相同。 注意：這三個條件并不是充分條件。例如下面兩個圖滿足這三個條件，但它們不同構。 2022/2/13 計算機學院 58/63 兩個圖同構的必要條件 1) 結點數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結點數(shù)相同。 注意 ：這三個條件并不是充分條件。例如下面兩個圖滿足這三個條件，但它們不同構。 y x u v x y v u 2022/2/13 計算機學院 59/63 兩個圖同構的必要條件 1) 結點數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結點數(shù)相同。 注意 ：這三個條件并不是充分條件。例如下面兩個圖滿足這三個條件，但它們不同構。 y x u v x y v u 若圖的結點可以任意挪動位置，而邊 是完全彈性的，只要在不拉斷的條件下， 一個圖可以變形為另一個圖，那么這兩個 圖是同構的。 如下圖所示： 2022/2/13 計算機學院 60/63 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 計算機學院 61/63 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/63 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/63 習題 ?P206 3(1)(4)、 8