【正文】 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ō)較為方便 。 ?若道路中的所有結(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互不相同 （ 從而所有邊互不相同 ） ， 則稱此回路為基本回路或者圈 。 ?若 v0≠vk， 稱為 開道路 ， 否則稱為 閉道路 。 ?道路中 邊的數(shù)目 k稱為此 道路的長(zhǎng)度 。 ?v0和 vk分別稱為此道路的 起點(diǎn) 和 終點(diǎn) ， 統(tǒng)稱為道路的 端點(diǎn) 。 ） ， 則稱 P為結(jié)點(diǎn) v0到結(jié)點(diǎn) vk的道路 。 2022/2/13 計(jì)算機(jī)學(xué)院 67/172 167。 ?如 P=v0， 稱為零道路 ， 其長(zhǎng)度為零 。 其余結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn) 。 簡(jiǎn)記為 〈 v0， vk〉 。 道路與回路 ?定義 圖 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) ， 即方向一致 。 如下圖所示： 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。例如下面兩個(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)。 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ù)相同。 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 ′。 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 ′。 設(shè) |X|=n1， |Y|=n2。 如果 X中的每一個(gè)結(jié)點(diǎn)與 Y中的全部結(jié)點(diǎn)都鄰接 ， 則稱 G為完全二部圖 ，并記為 Kn1,n2。 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中 ， 則這樣的圖稱為 二部圖 。 ? 這里 ， 當(dāng) G為有向圖時(shí) ， 則 Kn為有向完全圖；當(dāng) G為無(wú)向圖時(shí) ， 則 Kn為無(wú)向完全圖 。 ? 顯然 ， G與 互為補(bǔ)圖 ， 即 。 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ǔ)圖 ， 記為 。 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é)院 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。 8) 圖 G＝ V， E ， T?E且 T≠ ?， 則 G（ T） 是一個(gè)以 T為邊集 ， 以 T中各邊關(guān)聯(lián)的全部結(jié)點(diǎn)為結(jié)點(diǎn)集的圖 ，稱為 G的 邊誘導(dǎo)子圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 42/172 6) 設(shè) e是圖 G的一條邊 ， 從 G中刪去邊 e后得到的圖稱為 G刪邊子圖 ， 簡(jiǎn)記為 G－ e。 7) 圖 G＝ V， E ， S?V， 則 G(S)=(S， E′ )是一個(gè)以 S為結(jié)點(diǎn) ， 以 E′ ={uv|u,v?S,uv?E}為邊集的圖 ， 稱為 G的 點(diǎn)誘導(dǎo)子圖 。 8) 圖 G＝ V， E ， T?E且 T≠ ?， 則 G（ T） 是一個(gè)以 T為邊集 ， 以 T中各邊關(guān)聯(lián)的全部結(jié)點(diǎn)為結(jié)點(diǎn)集的圖 ，稱為 G的邊誘導(dǎo)子圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 40/172 6) 設(shè) e是圖 G的一條邊 ， 從 G中刪去邊 e后得到的圖稱為 G刪邊子圖 ， 簡(jiǎn)記為 G－ e。 4) 設(shè) V2=V1且 E2=E1或 E2=?， 則稱 H是 G的平凡子圖 。 2) 即 V2?V1或 E2?E1， 則稱 H是 G的真子圖 ， 記為 H?G。 2022/2/13 計(jì)算機(jī)學(xué)院 39/172 子圖 ? 定義 設(shè)有圖 G＝ V1 ,E1和圖 H＝ V2 ,E2。 4) 設(shè) V2=V1且 E2=E1或 E2=?， 則稱 H是 G的 平凡子圖 。 2) 即 V2?V1或 E2?E1， 則稱 H是 G的真子圖 ， 記為 H?G。 2022/2/13 計(jì)算機(jī)學(xué)院 38/172 子圖 ? 定義 設(shè)有圖 G＝ V1 ,E1和圖 H＝ V2 ,E2。 4) 設(shè) V2=V1且 E2=E1或 E2=?， 則稱 H是 G的平凡子圖 。 2) 即 V2?V1或 E2?E1， 則稱 H是 G的 真子圖 ， 記為 H?G。 v3 v2 v1 v5 v4 2022/2/13 計(jì)算機(jī)學(xué)院 37/172 子圖 ? 定義 設(shè)有圖 G＝ V1 ,E1和圖 H＝ V2 ,E2。 v3 v2 v1 v5 v4 2022/2/13 計(jì)算機(jī)學(xué)院 36/172 度數(shù)序列 ?設(shè) V ＝ {v1, v2,… ,vn} 為圖 G 的結(jié)點(diǎn)集 ， 稱(deg(v1),deg(v2),… ,deg(vn))為 G的度數(shù)序列 。 2022/2/13 計(jì)算機(jī)學(xué)院 35/172 度數(shù)序列 ?設(shè) V ＝ {v1, v2,… ,vn} 為圖 G 的 結(jié) 點(diǎn) 集 ， 稱(deg(v1),deg(v2),… ,deg(vn))為 G的 度數(shù)序列 。 ■ 2022/2/13 計(jì)算機(jī)學(xué)院 34/172 d e g ( ) d e g ( )v V v Vv v m???????? ，? 定理 ： 對(duì)于任何（ n,m）有向圖 G =（ V， E），則所有結(jié)點(diǎn)的引出度數(shù)之和等于所有結(jié)點(diǎn)的引入度數(shù)之和，所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍，即： d e g ( ) d e g ( ) d e g ( ) 2v V v V v Vv v v m??? ? ?? ? ?? ? ? 。由于上式中的 2m和 |V2|(偶數(shù)之和為偶數(shù) )均為偶數(shù)，因而也為偶數(shù)。 證明 設(shè) V1＝ {v|v?V且 deg(v)＝奇數(shù) }， V2＝ {v|v?V且deg(v)＝偶數(shù) }。于是 |V1|為偶數(shù) (因?yàn)?V1中的結(jié)點(diǎn) v之 deg(v)都為奇數(shù) )，即奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。顯然， V1∩V 2＝ Φ ，且 V1∪V 2＝ V，于是有： 12d e g ( ) d e g ( ) d e g ( ) 2v V v V v Vv v v m? ? ?? ? ?? ? ? ?！? 2022/2/13 計(jì)算機(jī)學(xué)院 32/172 推論 在圖 G＝ V， E中 ， 其 V＝ {v1,v2,v3,… ,vn}， E＝ {e1， e2， …… ， em}，度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。由于上式中的 2m和 |V2|(偶數(shù)之和為偶數(shù) )均為偶數(shù)，因而也為偶數(shù)。 設(shè) V1＝ {v|v?V且 deg(v)＝奇數(shù) }， V2＝ {v|v?V且deg(v)＝偶數(shù) }。 2022/2/13 計(jì)算機(jī)學(xué)院 25/172 例 deg(v1)＝ 3， deg+(v1)＝ 2， d