圖的基本概念ppt課件-文庫吧資料
2025-05-12 23:18本頁面
【正文】 =V’,E’, G’是 G的子圖 ,如果 V’=V, 則稱 G’是 G的生成子圖 . 上例中 , G1是 K5的生成子圖 . 十 . 補(bǔ)圖 由 G的所有結(jié)點和為使 G變成完全圖 ,所需要添加的那些 邊組成的圖 , 稱之為 G相對完全圖的補(bǔ)圖 ,簡稱 G的補(bǔ)圖 , 記作 . G ? ? ? ? ? K5 ? ? ? ? ? G ? ? ? ? ? G *十一 .相對補(bǔ)圖 設(shè) G1=V1,E1是圖 G=V,E的子圖 ,如果有 G2=V2,E2 使得 E2=EE1且 V2中僅包含 E2中的邊所關(guān)聯(lián)的結(jié)點 ,則稱 G2是 G1相對 G的補(bǔ)圖 . 可見 G2是 G3相對 G的補(bǔ)圖 . G3也是 G2相對 G的補(bǔ)圖 . 而 G1不是 G3相對 G的補(bǔ)圖 (多了一個結(jié)點 ). 但是 G3是 G1相對 G的補(bǔ)圖 . 可見 : 相對補(bǔ)圖無相互性 . ?a b? ?c d? ?e G G1 ?a b? ?c d? ?e ?c d? b? ?e G2 ?a b? ?c d? ?e G3 十二 . 圖的同構(gòu) 設(shè) G=V,E和 G’=V’,E’是圖 ,如果存在雙射 f:V?V’ 且 任何 vi,vj∈ V,若邊 (vi,vj)∈ E,當(dāng)且僅當(dāng) 邊 (f(vi),f(vj))∈ E’, (或 若邊 vi,vj∈ E,當(dāng)且僅當(dāng) 邊 f(vi),f(vj)∈ E’),則稱 G與 G’同構(gòu) ,記作 G≌ G’. (同構(gòu)圖要保持邊的“關(guān)聯(lián)”關(guān)系 ) 例如 :右邊所示的兩個圖 : G=V,E G’=V’,E’ 構(gòu)造映射 f:V?V’ 兩個圖同構(gòu)的必要條件 : . . . 4. 對應(yīng)的結(jié)點的度數(shù)相等 . a? ?b c? ?d 1? ?4 3? ?2 a ?1 b ?2 c ?3 d ?4 a ?1 b ?2 c ?3 d ?4 下面是同構(gòu)的圖 : 右面兩個圖不同構(gòu) : 左圖中四個 3度結(jié)點 構(gòu)成四邊形 ,而右圖 , 則不然 . 練習(xí) :請畫出 K4的所有不同構(gòu)的生成子圖 . a? ?f b? ?e c? ?d ?3 ?5 1? ?6 2? 4? ?3 1? ?2 ?a b? ?c ? ? ? ? ? ? ? ? ? ? ?a b? ?e c? ?d ?1 3? ?4 5? ?2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 練習(xí) :請畫出 K4的所有不同構(gòu)的生成子圖 . 本節(jié)要求 :準(zhǔn)確掌握如下基本概念和定理 : ,無向邊 ,孤立結(jié)點 ,平行邊 ,環(huán) . ,無向圖 ,零圖 ,平凡圖 ,簡單圖 ,多重圖 ,完全圖 ,子圖 ,生成子圖 ,補(bǔ)圖 ,相對補(bǔ)圖
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1