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