離散數(shù)學(xué)課件圖論(3)-文庫吧
2025-01-01 20:24 本頁面
【正文】 集，稱 d(v1), d(v2), …, d(vn)為G的 度數(shù)序列 。 非負(fù)整數(shù)列 d=(d1, d2, …, dn)是 可圖化 的，是 可簡單圖化 的。 [n階 k正則圖 ] 一個(gè)無向簡單圖 G中 ,如果 Δ(G)=δ(G)=k，則稱 G為 k正則圖 。 Kn是 n?1正則圖 School of Information Science and Engineering 141 圖 練習(xí) : ， 可能是一個(gè)圖度數(shù)序列 ? 如果 是， 試畫出它的圖 。 哪些是 可 簡單圖 化的 ? a) (1, 2, 3, 4, 5) b) (2, 2, 2, 2, 2) c) (1, 2, 3, 2, 4) G中 ,有 10條邊 ， 4個(gè) 3度結(jié)點(diǎn) ,其余結(jié)點(diǎn)的度均小于或等于 2， 問 G中至少有多少個(gè)結(jié)點(diǎn) ？ 為什么 ？ School of Information Science and Engineering 141 圖 [圖的同構(gòu) ] 設(shè) G1=V1,E1, G2=V2,E2為兩個(gè)無向圖 (兩個(gè)有向 圖 )，若存在雙射函數(shù) f:V1?V2, 對于 vi,vj?V1, (vi,vj)?E1 當(dāng)且僅當(dāng) (f(vi),f(vj))?E2 （ vi,vj?E1 當(dāng)且僅當(dāng) f(vi),f(vj)?E2 ) 并且 , (vi,vj)（ vi,vj）與 (f(vi),f(vj))（ f(vi),f(vj)）的重?cái)?shù)相 同，則稱 G1與 G2是 同構(gòu) 的，記作 G1?G2。 ? 圖之間的同構(gòu)關(guān)系具有自反性、對稱性和傳遞性 ? 能找到同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件： ① 邊數(shù)相同，頂點(diǎn)數(shù)相同 。 ② 度數(shù)序列相同 。 ③ 對應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同，等等 ? 若破壞必要條件，則兩圖不同構(gòu) ? 判斷兩個(gè)圖同構(gòu)是個(gè)難題 School of Information Science and Engineering 141 圖 [圖同構(gòu)實(shí)例 ] (1) (2) (3) (4) 圖中， (1)與 (2)不同構(gòu)（度數(shù)列不同）， (3)與 (4)也不同構(gòu) . (1) (2) 問： 圖中 (1)與 (2)的度數(shù)序列相同，它們同構(gòu)嗎？為什么？ School of Information Science and Engineering 141 圖 [完全圖 ] ［無向完全圖］ G是個(gè)簡單圖 ， 如果每對不同 頂點(diǎn) 都 相鄰， 則稱 G是個(gè)無向完全圖。如果 G有 n個(gè)結(jié)點(diǎn) , 則記作 Kn。 簡單性質(zhì)： 邊數(shù) ［有向完全圖］ G是個(gè)有向簡單圖，如果任意兩個(gè)不同頂點(diǎn)之間都有方向相反的邊 ,則稱它是有向完全圖。 簡單性質(zhì)：邊數(shù) ［競賽圖］ 基圖為 Kn的有向簡單圖。 1,2 )1( ?????? nnnm ?1),1(2),1( ?????????? ?? nnnnm ?? School of Information Science and Engineering 141 圖 [子圖 ] 定義： G=V,E, G?=V?,E? (1) G??G —— G?為 G的 子圖 ， G為 G?的 母圖 (2) 若 G??G且 V?=V，則稱 G?為 G的 生成子圖 (3) 若 V??V或 E??E，稱 G?為 G的 真子圖 (4) V?（ V??V且 V???）的 導(dǎo)出子圖 ，記作 G[V?] (5) E?（ E??E且 E???）的 導(dǎo)出子圖 ，記作 G[E?] G2G1G3K5abaedbbccd eabccd e School of Information Science and Engineering 141 圖 例 畫出 K4的所有非同構(gòu)的生成子圖。 School of Information Science and Engineering 141 圖 [補(bǔ)圖 ] 定義： 設(shè) G=V,E為 n階無向簡單圖，以 V為頂點(diǎn)集，以所有使G成為完全圖 Kn的添加邊組成的集合為邊集的圖，稱為 G的補(bǔ)圖 ，記作 。 若 G? , 則稱 G是 自補(bǔ)圖 。 相對于 K4, 求上面圖中所有圖的補(bǔ)圖，并指出哪些是自補(bǔ)圖。 問：互為自補(bǔ)圖的兩個(gè)圖的邊數(shù)有何關(guān)系？ GG School of Information Science and Engineering 142 通路與回路 [定義 ] 給定圖 G=V,E（無向或有向的）， G中 頂點(diǎn)與 邊的交替序列 ? = v0e1v1e2… elvl， vi?1, vi 是 ei 的端點(diǎn)。 (1) 通路與回路： ? 為 通路 ；若 v0=vl， ? 為 回路 ， l 為 回路長 度 。 (2) 簡單通路與回路：所有邊各異， ? 為 簡單通路 ，又若 v0=vl，? 為 簡單回路。 (3) 初級通路 (路徑 )與初級回路 (圈 )： ? 中所有頂點(diǎn)各異，則稱 ? 為 初級通路 (路徑 )，又若除 v0=vl，所有的頂點(diǎn)各不相同且所有的邊各異，則稱 ? 為 初級回路 (圈 )。 (4) 復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)。 School of Information Science and Engineering 142 通路與回路 [表示法 ] ① 定義表示法 ② 只用邊表示法 ③ 只用頂點(diǎn)表示法（在簡單圖中） ④ 混合表示法 環(huán) （長為 1的圈）的長度為 1，兩條平行邊構(gòu)成的圈長度為 2，無向簡單圖中，圈長 ?3，有向簡單圖中圈的長度 ?2. [不同的圈 ]（以長度 ?3的為例） ① 定義意義下 無向圖：圖中長度為 l（ l?3）的圈，定義意義下為 2l個(gè) 有向圖：圖中長度為 l（ l?3）的圈，定義意義下為 l個(gè) ② 同構(gòu)意義下：長度相同的圈均為 1個(gè) School of Information Science and Engineering 142 通路與回路 [定理 ] 在 n 階圖 G中，若從頂點(diǎn)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1