離散數(shù)學(xué)chppt課件(已修改)
2025-05-16 08:14 本頁面
【正文】 1 第五部分 圖論 本部分主要內(nèi)容 ? 圖的基本概念 ? 歐拉圖、哈密頓圖 ? 樹 ? 平面圖 ? 支配集、覆蓋集、獨(dú)立集、匹配與著色 2 第十四章 圖的基本概念 主要內(nèi)容 ? 圖 ? 通路與回路 ? 圖的連通性 ? 圖的矩陣表示 ? 圖的運(yùn)算 預(yù)備知識(shí) ? 多重集合 —— 元素可以重復(fù)出現(xiàn)的集合 ? 無序集 —— A?B={(x,y) | x?A?y?B} 3 圖 定義 無向圖 G = V,E, 其中 (1) V ? ?為頂點(diǎn)集，元素稱為 頂點(diǎn) (2) E為 V?V 的多重集，其元素稱為無向邊，簡稱 邊 實(shí)例 設(shè) V = {v1, v2, …, v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 則 G = V,E為一無向圖 4 有向圖 定義 有向圖 D=V,E, 只需注意 E是 V?V 的多重子集 圖 2表示的是一個(gè)有向圖，試寫出它的 V 和 E 注意：圖的數(shù)學(xué)定義與圖形表示，在同構(gòu)（待敘）的意義下 是一一對應(yīng)的 5 相關(guān)概念 1. 圖 ① 可用 G泛指圖（無向的或有向的） ② V(G), E(G), V(D), E(D) ③ n階圖 2. 有限圖 3. n 階零圖與平凡圖 4. 空圖 —— ? 5. 用 ek 表示無向邊或有向邊 6. 頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系 ① 關(guān)聯(lián)、關(guān)聯(lián)次數(shù) ② 環(huán) ③ 孤立點(diǎn) 7. 頂點(diǎn)之間的相鄰與鄰接關(guān)系 6 }{)()(})(),()(|{)(vvNvNvvuGEvuGVuuvNv????????的閉鄰域的鄰域})(|{)( 關(guān)聯(lián)與 veGEeevI ???}{)()()()()(})(,)(|{)(})(,)(|{)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD????????????????????????????的閉鄰域的鄰域的先驅(qū)元集的后繼元集8. 鄰域與關(guān)聯(lián)集 ① v?V(G) (G為無向圖 ) v 的關(guān)聯(lián)集 ② v?V(D) (D為有向圖 ) 9. 標(biāo)定圖與非標(biāo)定圖 10. 基圖 相關(guān)概念 7 多重圖與簡單圖 定義 (1) 無向圖中的平行邊及重?cái)?shù) (2) 有向圖中的平行邊及重?cái)?shù)（注意方向性） (3) 多重圖 (4) 簡單圖 在定義 8 頂點(diǎn)的度數(shù) 定義 (1) 設(shè) G=V,E為無向圖 , ?v?V, d(v)—— v的度數(shù) , 簡稱度 (2) 設(shè) D=V,E為有向圖 , ?v?V, d+(v)—— v的出度 d?(v)—— v的入度 d(v)—— v的度或度數(shù) (3) ?(G), ?(G) (4) ?+(D), ?+(D), ??(D), ??(D), ?(D), ?(D) (5) 奇頂點(diǎn)度與偶度頂點(diǎn) 9 mvdnii 2)(1???mvdvdmvdniiniinii ???????????111)()(,2)( 且定理 設(shè) G=V,E為任意無向圖， V={v1,v2,… ,vn}, |E|=m, 則 證 G中每條邊 (包括環(huán) ) 均有兩個(gè)端點(diǎn)，所以在計(jì)算 G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供 2度， m 條邊共提供 2m 度 . 本定理的證明類似于定理 握手定理 定理 設(shè) D=V,E為任意有向圖， V={v1,v2,…, vn}, |E|=m, 則 10 握手定理推論 推論 任何圖 (無向或有向 ) 中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù) . 證 設(shè) G=V,E為任意圖，令 V1={v | v?V? d(v)為奇數(shù) } V2={v | v?V? d(v)為偶數(shù) } 則 V1?V2=V, V1?V2=?，由握手定理可知 由于 2m, 均為偶數(shù)，所以 為偶數(shù)，但因?yàn)?V1中 頂點(diǎn)度數(shù)為奇數(shù)，所以 |V1|必為偶數(shù) . ?????????21)()()(2VvVvVvvdvdvdm?? 2)(Vvvd ?? 1)(Vvvd11 例 1 無向圖 G有 16條邊， 3個(gè) 4度頂點(diǎn)， 4個(gè) 3度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于 3，問 G的階數(shù) n為幾？ 解 本題的關(guān)鍵是應(yīng)用握手定理 . 設(shè)除 3度與 4度頂點(diǎn)外，還有 x個(gè)頂點(diǎn) v1, v2, …, vx， 則 d(vi) ? 2， i =1, 2, …, x， 于是得不等式 32 ? 24+2x 得 x ? 4, 階數(shù) n ? 4+4+3=11. 握手定理應(yīng)用 12 圖的度數(shù)列 1 . V={v1, v2, …, vn}為無向圖 G的頂點(diǎn)集，稱 d(v1), d(v2), …, d(vn)為 G的 度數(shù)列 2. V={v1, v2, …, vn}為有向圖 D的頂點(diǎn)集， D的 度數(shù)列 ： d(v1), d(v2), …, d
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1