【正文】 例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。 注意 ：這三個(gè)條件并不是充分條件。 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ù)相同。 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 ′ ， 使得對(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 ′。 如果 X中的每一個(gè)結(jié)點(diǎn)與 Y中的全部結(jié)點(diǎn)都鄰接 ， 則稱 G為完全二部圖 ，并記為 Kn1,n2。 ? 這里 ， 當(dāng) G為有向圖時(shí) ， 則 Kn為有向完全圖；當(dāng) G為無(wú)向圖時(shí) ， 則 Kn為無(wú)向完全圖 。 2nP2nC 122022/2/13 計(jì)算機(jī)學(xué)院 47/63 補(bǔ)圖 ? 設(shè) G＝ V， E為具有 n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖 ,從完全圖 Kn中 刪去 G中的所有邊而得到的圖稱為 G相對(duì)于完全圖 Kn的補(bǔ)圖 ， 簡(jiǎn)稱 G的 補(bǔ)圖 ， 記為 。 無(wú)向完全圖 Kn的邊數(shù)為 = n(n1)，有向完全圖 Kn的邊數(shù)為 = n(n1)。 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。 2022/2/13 計(jì)算機(jī)學(xué)院 41/63 6) 設(shè) e是圖 G的一條邊 ， 從 G中刪去邊 e后得到的圖稱為 G刪邊子圖 ， 簡(jiǎn)記為 G－ e。 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)子圖 。 4) 設(shè) V2=V1且 E2=E1或 E2=?， 則稱 H是 G的平凡子圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 38/63 子圖 ? 定義 設(shè)有圖 G＝ V1 ,E1和圖 H＝ V2 ,E2。 2) 即 V2?V1或 E2?E1， 則稱 H是 G的真子圖 ， 記為 H?G。 4) 設(shè) V2=V1且 E2=E1或 E2=?， 則稱 H是 G的平凡子圖 。 v3 v2 v1 v5 v4 2022/2/13 計(jì)算機(jī)學(xué)院 36/63 子圖 ? 定義 設(shè)有圖 G＝ V1 ,E1和圖 H＝ V2 ,E2。 2022/2/13 計(jì)算機(jī)學(xué)院 34/63 度數(shù)序列 ?設(shè) V ＝ {v1, v2,… ,vn} 為圖 G 的 結(jié) 點(diǎn) 集 ， 稱(deg(v1),deg(v2),… ,deg(vn))為 G的 度數(shù)序列 。由于上式中的 2m和 |V2|(偶數(shù)之和為偶數(shù) )均為偶數(shù)，因而也為偶數(shù)。于是 |V1|為偶數(shù) (因?yàn)?V1中的結(jié)點(diǎn) v之 deg(v)都為奇數(shù) )，即奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)?！? 2022/2/13 計(jì)算機(jī)學(xué)院 31/63 推論 在圖 G＝ V， E中 ， 其 V＝ {v1,v2,v3,… ,vn}， E＝ {e1， e2， …… ， em}，度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。 設(shè) V1＝ {v|v?V且 deg(v)＝奇數(shù) }， V2＝ {v|v?V且deg(v)＝偶數(shù) }。 2022/2/13 計(jì)算機(jī)學(xué)院 23/63 3) 對(duì)于圖 G＝ V， E， 度數(shù)為 0的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)構(gòu)成的圖 G=（ V， ?） 稱為零圖；只由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為平凡圖； 4) 在圖 G＝ V， E中 ， 稱度數(shù)為奇數(shù)的結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn) ， 度數(shù)為偶數(shù)的結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn) 。 2) 在 有向圖 G＝ V， E中 ， 以結(jié)點(diǎn) v為始點(diǎn)引出的邊的條數(shù) ， 稱為該結(jié)點(diǎn)的 出度 ,記為 deg+(v)；以結(jié)點(diǎn) v為終點(diǎn)引入的邊的條數(shù) ， 稱為該結(jié)點(diǎn)的 入度 ,記為 deg(v)；而結(jié)點(diǎn)的引出度數(shù)和引入度數(shù)之和稱為該結(jié)點(diǎn)的 度數(shù) ， 記為 deg(v)，即 deg(v)＝ deg+(v)+deg(v)； 2022/2/13 計(jì)算機(jī)學(xué)院 21/63 3) 對(duì)于圖 G＝ V， E， 度數(shù)為 0的結(jié)點(diǎn)稱為 孤立結(jié)點(diǎn) ；只由孤立結(jié)點(diǎn)構(gòu)成的圖 G=（ V， ?） 稱為零圖； 只由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為 平凡圖； 4) 在圖 G＝ V， E中 ， 稱度數(shù)為奇數(shù)的結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn) ， 度數(shù)為偶數(shù)的結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn) 。 2022/2/13 計(jì)算機(jī)學(xué)院 18/63 圖的分類 (按權(quán) ) ? 賦權(quán)圖 G是一個(gè)三重組 V,E,g， 其中 V是結(jié)點(diǎn)集合 ，E是邊的集合 ， g是邊 E上的權(quán)值 。 6) 將多重圖和廣義圖中的平行邊代之以一條邊 ， 去掉環(huán) ，可以得到一個(gè)簡(jiǎn)單圖 ， 稱為原來(lái)圖的基圖 。 2) 在無(wú)向圖中 ， 兩個(gè)結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若有幾條邊 ， 則這幾條邊稱為 平行邊 ； 3) 含有平行邊的圖稱為多重圖； 4) 含有環(huán)的多重圖稱為廣義圖 （ 偽圖 ） ； 5) 滿足定義 。 v是邊 e的終點(diǎn) ， 統(tǒng)稱為 e的端點(diǎn)； e是 u的出邊 ， 是 v的入邊 。 v是邊 e的終點(diǎn) ， 統(tǒng)稱為 e的端點(diǎn)； e是 u的出邊 ， 是 v的入邊 。 v是邊 e的 終點(diǎn) ， 統(tǒng)稱為 e的 端點(diǎn) ； e是 u的出邊 ， 是 v的入邊 。 v是邊 e的終點(diǎn) ， 統(tǒng)稱為 e的端點(diǎn)； e是 u的出邊 ， 是 v的入邊 。