離散數(shù)學(xué)圖論ppt課件-資料下載頁
2025-05-02 05:11本頁面
【正文】 稱為 G的補圖 (或 G的 補 )， 記為 。 定義 Ｇ＝ Ｖ ， Ｅ 是圖 ， Ｇ ’ ＝ Ｖ ’ ， Ε’是Ｇ的子圖 ， Ｅ ” ＝Ｅ－Ｅ ’ ， Ｖ ” 是Ｅ ” 中邊所關(guān)聯(lián)的所有頂點集合 ， 則Ｇ ” ＝ Ｖ ” ， Ｅ ” 稱為Ｇ ’ 關(guān)于Ｇ的 相對補圖 。 關(guān)于完全圖的子圖的補圖稱為此子圖的 絕對補圖 。 五、補圖 G離散數(shù)學(xué) 18 例： 例： 在下圖 (a)、 (b)、 (c)、 (d)中 ， (a)與 (b)是互為補圖； (c)和 (d)是互為補圖 。 離散數(shù)學(xué) 19 六、圖的同構(gòu) 例 :如下圖所示 ， 圖 (a)、 圖 (b)、 圖 (c)和圖 (d)所表示的圖形實際上都是一樣的 。 離散數(shù)學(xué) 20 定義 定義 設(shè)有圖 G＝ V,E和圖 G1＝ V1,E1,如果存在雙射函數(shù) g:V→V 1, 使 得 對 于 任 意 的 邊 e ＝ (vi,vj)?E( 或vi,vj?E)當且僅當 e1＝ (g(vi),g(vj))?E1(或 g(vi),g(vj)?E1) 則稱 G和 G1同構(gòu) ， 記為 G≌ G1。 同構(gòu)的充要條件： 兩個圖的結(jié)點和邊分別存在一一對應(yīng) ，且保持關(guān)聯(lián)關(guān)系 。 離散數(shù)學(xué) 21 例： 例： 如圖 (a)、 (b)所示的兩個圖 G＝ V,E和 G1＝ V1,E1，證明 G≌ G1。 解 ：定義函數(shù) g:V→V 1， 滿足 g(vi)＝ vi’(i＝ 1， 2， 3， 4， 5)，可以驗證 g是一個滿足定義的雙射 ， 所以 G≌ G1。 離散數(shù)學(xué) 22 必要條件 兩個圖同構(gòu)的必要條件： 結(jié)點數(shù)目相同； 邊數(shù)相同； 度數(shù)相同的結(jié)點數(shù)相同。 注意 ：這三個條件并不是充分條件。例如下面兩個圖滿足這三個條件，但它們不同構(gòu)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1