圖論基本概念ppt課件-文庫(kù)吧資料
2025-05-09 22:00本頁(yè)面
【正文】 均為偶數(shù)，所以 為偶數(shù)，但因?yàn)?V1中 頂點(diǎn)度數(shù)為奇數(shù)，所以 |V1|必為偶數(shù) . ?????????21)()()(2VvVvVvvdvdvdm?? 2)(Vvvd ?? 1)(Vvvd14 圖的度數(shù)列 1 . V={v1, v2, …, vn}為無(wú)向圖 G的頂點(diǎn)集，稱(chēng) d(v1), d(v2), …, d(vn)為 G的 度數(shù)列 2. V={v1, v2, …, vn}為有向圖 D的頂點(diǎn)集， D的 度數(shù)列 ： d(v1), d(v2), …, d(vn) D的 出度列 ： d+(v1), d+(v2), …, d+(vn) D的 入度列 ： d?(v1), d?(v2), …, d?(vn) 3. 非負(fù)整數(shù)列 d=(d1, d2, …, dn)是 可圖化的 ，是 可簡(jiǎn)單圖化 的 . 易知： (2, 4, 6, 8, 10)， (1, 3, 3, 3, 4) 是可圖化的，后者又是可 簡(jiǎn)單圖化的，而 (2, 2, 3, 4, 5)， (3, 3, 3, 4) 都不是可簡(jiǎn)單圖化 的，特別是后者也不是可圖化的 15 圖的同構(gòu) 定義 設(shè) G1=V1,E1, G2=V2,E2為兩個(gè)無(wú)向圖 (兩個(gè)有向 圖 )，若存在雙射函數(shù) f:V1?V2, 對(duì)于 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ù)相 同，則稱(chēng) G1與 G2是 同構(gòu) 的，記作 G1?G2. ? 圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱(chēng)性和傳遞性 . ? 能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件： ① 邊數(shù)相同，頂點(diǎn)數(shù)相同 。 ③ 對(duì)應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同，等等 若破壞必要條件，則兩圖不同構(gòu) ? 判斷兩個(gè)圖同構(gòu)是個(gè)難題 16 圖同構(gòu)的實(shí)例 圖中 (1)與 (2)的度數(shù)列相同，它們同構(gòu)嗎？為什么？ (1) (2) (3) (4) 圖中， (1)與 (2)不同構(gòu)（度數(shù)列不同）， (3)與 (4)也不同構(gòu) . (1) (2) 17 n 階完全圖與競(jìng)賽圖 定義 (1) n (n?1) 階無(wú)向完全圖 —— 每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的無(wú)向簡(jiǎn)單圖，記作 Kn. 簡(jiǎn)單性質(zhì)：邊數(shù) (2) n (n?1)階 有向完全圖 —— 每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的有向簡(jiǎn)單圖 . 簡(jiǎn)單性質(zhì)： (3) n (n?1) 階 競(jìng)賽圖 —— 基圖為 Kn的有向簡(jiǎn)單圖 . 簡(jiǎn)單性質(zhì)：邊數(shù) 1,2 )1( ?????? nnnm ?1),1(2),1( ?????????? ?? nnnnm ?? 1,2 )1( ?????? nnnm ?18 n 階 k 正則圖 (1)為 K5， (2)為 3階有向完全圖， (3)為 4階競(jìng)賽圖 . (1) (2) (3) 定義 n 階 k正則圖 —— ?=?=k 的無(wú)向簡(jiǎn)單圖 簡(jiǎn)單性質(zhì)：邊數(shù)（由握手定理得） Kn是 n?1正則圖， 彼得松圖（見(jiàn)書(shū)上圖 (1) 所示，記住它） 2nkm ?19 子圖 定義 G=V,E, G?=V?,E? (1) G??G —— G?為 G的 子圖 ， G為 G?的 母圖 (2) 若 G??G且 V?=V，則稱(chēng) G?為 G的 生成子圖 (3) 若 V??V或 E??E，稱(chēng) G?為 G的 真子圖 (4) V?（ V??V且 V???）的 導(dǎo)出子圖 ，記作 G[V?] (5) E?（ E??E且 E???）的 導(dǎo)出子圖 ，記作 G[E?] 20 例 2 畫(huà)出 K4的所有非同構(gòu)的生成子圖 實(shí)例 21 補(bǔ)圖 定義 設(shè) G=V,E為 n階無(wú)向簡(jiǎn)單圖，以 V為頂點(diǎn)集，以所有使 G成為完全圖 Kn的添加邊組成的集合為邊集的圖，稱(chēng)為 G的 補(bǔ)圖 ，記作 . 若 G? , 則稱(chēng) G是 自補(bǔ)圖 . 相對(duì)于 K4, 求上面圖中所有圖的補(bǔ)圖，并指出哪些是自補(bǔ)圖 . 問(wèn)：互為自補(bǔ)圖的兩個(gè)圖的邊數(shù)有何關(guān)系？ GG22 通路與回路 定義 給定圖 G=V,E（無(wú)向或有向的）， G中 頂點(diǎn)與 邊的交替序列 ? = v0e1v1e2… elvl， vi?1, vi 是 ei 的端點(diǎn) . (1) 通路與回路： ? 為 通路 ；若 v0=vl， ? 為 回路 ， l 為 回路長(zhǎng) 度 . (2) 簡(jiǎn)單通路與回路：所有邊各異， ? 為 簡(jiǎn)單通路 ，又若 v0=vl，? 為 簡(jiǎn)單回路 (3) 初級(jí)通路 (路徑 )與初級(jí)回路 (圈 )： ? 中所有頂點(diǎn)各異，則稱(chēng) ? 為 初級(jí)通路 (路徑 )，又若除 v0=vl，所有的頂點(diǎn)各不相同且所有的邊各異，則稱(chēng) ? 為 初級(jí)回路 (圈 ) (4) 復(fù)雜通路與回路：有邊重復(fù)出現(xiàn) 23 幾點(diǎn)說(shuō)明 表示法 ① 定義表示法 ② 只用邊表示法 ③ 只用頂點(diǎn)表示法（在簡(jiǎn)單圖中） ④ 混合表示法 環(huán) （長(zhǎng)為 1的圈）的長(zhǎng)度為 1，兩條平行邊構(gòu)成的圈長(zhǎng)度為 2，無(wú)向簡(jiǎn)單圖中，圈長(zhǎng) ?3，有向簡(jiǎn)單圖中圈的長(zhǎng)度 ?2. 不同的圈（以長(zhǎng)度 ?3的為例） ① 定義意義下 無(wú)向圖：圖中長(zhǎng)度為 l（ l?3）的圈，定義意義下為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1