【正文】 個(gè)結(jié)點(diǎn)的有向簡單圖 ， 若對于任意 u,v?V(u?v)， 既有有向邊u,v， 又有有向邊 v,u， 則稱 G為有向完全圖 ， 在不發(fā)生誤解的情況下 ， 也記為 Kn。 無向完全圖 Kn的 邊數(shù) 為 = n(n1)，有向完全圖 Kn的 邊數(shù) 為 = n(n1)。 2nP2nC 122022/2/13 計(jì)算機(jī)學(xué)院 47/63 補(bǔ)圖 ? 設(shè) G＝ V， E為具有 n個(gè)結(jié)點(diǎn)的簡單圖 ,從完全圖 Kn中 刪去 G中的所有邊而得到的圖稱為 G相對于完全圖 Kn的補(bǔ)圖 ， 簡稱 G的 補(bǔ)圖 ， 記為 。 ? 這里 ， 當(dāng) G為有向圖時(shí) ， 則 Kn為有向完全圖；當(dāng) G為無向圖時(shí) ， 則 Kn為無向完全圖 。 ? 顯然 ， G與 互為補(bǔ)圖 ， 即 。 GG?GG2022/2/13 計(jì)算機(jī)學(xué)院 48/63 補(bǔ)圖 ? 設(shè) G＝ V， E為具有 n個(gè)結(jié)點(diǎn)的簡單圖 ,從完全圖 Kn中刪去 G中的所有邊而得到的圖稱為 G相對于完全圖 Kn的補(bǔ)圖 ， 簡稱 G的補(bǔ)圖 ， 記為 。 ? 這里 ， 當(dāng) G為有向圖時(shí) ， 則 Kn為有向完全圖；當(dāng) G為無向圖時(shí) ， 則 Kn為無向完全圖 。 ? 顯然 ， G與 互為補(bǔ)圖 ， 即 。 GG?GG2022/2/13 計(jì)算機(jī)學(xué)院 49/63 例 2022/2/13 計(jì)算機(jī)學(xué)院 50/63 二部圖 設(shè)圖 G=V,E， 如果它的結(jié)點(diǎn)集可以劃分成兩個(gè)子集 X和 Y， 使得它的 每一條邊的一個(gè)關(guān)聯(lián)結(jié)點(diǎn)在 X中 ， 另一個(gè)關(guān)聯(lián)結(jié)點(diǎn)在 Y中 ， 則這樣的圖稱為 二部圖 。 設(shè) |X|=n1， |Y|=n2。 如果 X中的每一個(gè)結(jié)點(diǎn)與 Y中的全部結(jié)點(diǎn)都鄰接 ， 則稱 G為完全二部圖 ，并記為 Kn1,n2。 2022/2/13 計(jì)算機(jī)學(xué)院 51/63 二部圖 設(shè)圖 G=V,E， 如果它的結(jié)點(diǎn)集可以劃分成兩個(gè)子集 X和 Y， 使得它的每一條邊的一個(gè)關(guān)聯(lián)結(jié)點(diǎn)在 X中 ， 另一個(gè)關(guān)聯(lián)結(jié)點(diǎn)在 Y中 ， 則這樣的圖稱為二部圖 。 設(shè) |X|=n1， |Y|=n2。 如果 X中的每一個(gè)結(jié)點(diǎn)與 Y中的全部結(jié)點(diǎn)都鄰接 ， 則稱 G為 完全二部圖 ，并記為 Kn1,n2。 2022/2/13 計(jì)算機(jī)學(xué)院 52/63 圖的同構(gòu) a b c d a b c d a b c d a b c d 2022/2/13 計(jì)算機(jī)學(xué)院 53/63 定義 ?設(shè)兩個(gè)圖 G=V,E和 G′ =V′ ,E′ ， 如果存在雙射函數(shù) g： V→V ′ ， 使得對于任意的 e=(vi,vj) （ 或者 vi,vj ） ∈ E 當(dāng)且僅當(dāng) e′ ＝(g(vi),g(vj)) （ 或者 g(vi),g(vj)） ∈ E′， 則稱 G與 G′同構(gòu) ， 記為 G≌G ′。 （ 同構(gòu)是指兩個(gè)圖的邊 11對應(yīng) ） ?圖的同構(gòu)關(guān)系是圖集上的等價(jià)關(guān)系 。 2022/2/13 計(jì)算機(jī)學(xué)院 54/63 定義 ?設(shè)兩個(gè)圖 G=V,E和 G′ =V′ ,E′ ， 如果存在雙射函數(shù) g： V→V ′ ， 使得對于任意的 e=(vi,vj) （ 或者 vi,vj） ∈ E當(dāng)且僅當(dāng) e′ ＝ (g(vi),g(vj)) （ 或者 g(vi),g(vj)） ∈ E′， 則稱 G與 G′同構(gòu) ，記為 G≌G ′。 （ 同構(gòu)是指兩個(gè)圖的邊 11對應(yīng) ） ?圖的同構(gòu)關(guān)系是圖集上的等價(jià)關(guān)系 。 2022/2/13 計(jì)算機(jī)學(xué)院 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 計(jì)算機(jī)學(xué)院 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 計(jì)算機(jī)學(xué)院 57/63 兩個(gè)圖同構(gòu)的必要條件 1) 結(jié)點(diǎn)數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結(jié)點(diǎn)數(shù)相同。 注意：這三個(gè)條件并不是充分條件。例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。 2022/2/13 計(jì)算機(jī)學(xué)院 58/63 兩個(gè)圖同構(gòu)的必要條件 1) 結(jié)點(diǎn)數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結(jié)點(diǎn)數(shù)相同。 注意 ：這三個(gè)條件并不是充分條件。例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。 y x u v x y v u 2022/2/13 計(jì)算機(jī)學(xué)院 59/63 兩個(gè)圖同構(gòu)的必要條件 1) 結(jié)點(diǎn)數(shù)目相同； 2) 邊數(shù)相同； 3) 度數(shù)相同的結(jié)點(diǎn)數(shù)相同。 注意 ：這三個(gè)條件并不是充分條件。例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。 y x u v x y v u 若圖的結(jié)點(diǎn)可以任意挪動位置，而邊 是完全彈性的，只要在不拉斷的條件下， 一個(gè)圖可以變形為另一個(gè)圖，那么這兩個(gè) 圖是同構(gòu)的。 如下圖所示： 2022/2/13 計(jì)算機(jī)學(xué)院 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不同構(gòu) 為什么？ 例 2022/2/13 計(jì)算機(jī)學(xué)院 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不同構(gòu) 為什么？ 例 2022/2/13 計(jì)算機(jī)學(xué)院 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不同構(gòu) 為什么？ 例 這說明上述三個(gè)條件僅僅是必要而不充分 2022/2/13 計(jì)算機(jī)學(xué)院 63/63 習(xí)題 ?P206 3(1)(4)、 8