離散數學chppt課件-閱讀頁
2025-05-19 08:14本頁面
【正文】 是一一對應的 5 相關概念 1. 圖 ① 可用 G泛指圖（無向的或有向的） ② V(G), E(G), V(D), E(D) ③ n階圖 2. 有限圖 3. n 階零圖與平凡圖 4. 空圖 —— ? 5. 用 ek 表示無向邊或有向邊 6. 頂點與邊的關聯關系 ① 關聯、關聯次數 ② 環(huán) ③ 孤立點 7. 頂點之間的相鄰與鄰接關系 6 }{)()(})(),()(|{)(vvNvNvvuGEvuGVuuvNv????????的閉鄰域的鄰域})(|{)( 關聯與 veGEeevI ???}{)()()()()(})(,)(|{)(})(,)(|{)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD????????????????????????????的閉鄰域的鄰域的先驅元集的后繼元集8. 鄰域與關聯集 ① v?V(G) (G為無向圖 ) v 的關聯集 ② v?V(D) (D為有向圖 ) 9. 標定圖與非標定圖 10. 基圖 相關概念 7 多重圖與簡單圖 定義 (1) 無向圖中的平行邊及重數 (2) 有向圖中的平行邊及重數（注意方向性） (3) 多重圖 (4) 簡單圖 在定義 8 頂點的度數 定義 (1) 設 G=V,E為無向圖 , ?v?V, d(v)—— v的度數 , 簡稱度 (2) 設 D=V,E為有向圖 , ?v?V, d+(v)—— v的出度 d?(v)—— v的入度 d(v)—— v的度或度數 (3) ?(G), ?(G) (4) ?+(D), ?+(D), ??(D), ??(D), ?(D), ?(D) (5) 奇頂點度與偶度頂點 9 mvdnii 2)(1???mvdvdmvdniiniinii ???????????111)()(,2)( 且定理 設 G=V,E為任意無向圖， V={v1,v2,… ,vn}, |E|=m, 則 證 G中每條邊 (包括環(huán) ) 均有兩個端點，所以在計算 G中各頂點度數之和時，每條邊均提供 2度， m 條邊共提供 2m 度 . 本定理的證明類似于定理 握手定理 定理 設 D=V,E為任意有向圖， V={v1,v2,…, vn}, |E|=m, 則 10 握手定理推論 推論 任何圖 (無向或有向 ) 中，奇度頂點的個數是偶數 . 證 設 G=V,E為任意圖，令 V1={v | v?V? d(v)為奇數 } V2={v | v?V? d(v)為偶數 } 則 V1?V2=V, V1?V2=?，由握手定理可知 由于 2m, 均為偶數，所以 為偶數，但因為 V1中 頂點度數為奇數，所以 |V1|必為偶數 . ?????????21)()()(2VvVvVvvdvdvdm?? 2)(Vvvd ?? 1)(Vvvd11 例 1 無向圖 G有 16條邊， 3個 4度頂點， 4個 3度頂點，其余頂點度數均小于 3，問 G的階數 n為幾？ 解 本題的關鍵是應用握手定理 . 設除 3度與 4度頂點外，還有 x個頂點 v1, v2, …, vx， 則 d(vi) ? 2， i =1, 2, …, x， 于是得不等式 32 ? 24+2x 得 x ? 4, 階數 n ? 4+4+3=11. 握手定理應用 12 圖的度數列 1 . V={v1, v2, …, vn}為無向圖 G的頂點集，稱 d(v1), d(v2), …, d(vn)為 G的 度數列 2. V={v1, v2, …, vn}為有向圖 D的頂點集， D的 度數列 ： d(v1), d(v2), …, d(vn) D的 出度列 ： d+(v1), d+(v2), …, d+(vn) D的 入度列 ： d?(v1), d?(v2), …, d?(vn) 3. 非負整數列 d=(d1, d2, …, dn)是 可圖化的 ，是 可簡單圖化 的 . 易知： (2, 4, 6, 8, 10)， (1, 3, 3, 3, 4) 是可圖化的，后者又是可 簡單圖化的，而 (2, 2, 3, 4, 5)， (3, 3, 3, 4) 都不是可簡單圖化 的，特別是后者也不是可圖化的 13 圖的同構 定義 設 G1=V1,E1, G2=V2,E2為兩個無向圖 (兩個有向 圖 )，若存在雙射函數 f:V1?V2, 對于 vi,vj?V1, (vi,vj)?E1 當且僅當 (f(vi),f(vj))?E2 （ vi,vj?E1 當且僅當 f(vi),f(vj)?E2 ) 并且 , (vi,vj)（ vi,vj）與 (f(vi),f(vj))（ f(vi),f(vj)）的重數相 同，則稱 G1與 G2是 同構 的，記作 G1?G2. ? 圖之間的同構關系具有自反性、對稱性和傳遞性 . ? 能找到多條同構的必要條件，但它們全不是充分條件： ① 邊數相同，頂點數相同 。 ② 度數列相同
教學課件相關推薦
鄂ICP備17016276號-1