離散數(shù)學(xué)課件圖論(3)(已修改)
2025-01-28 20:24 本頁面
【正文】 第四部分 圖論 School of Information Science and Engineering 圖 論 實例 1： 多用戶操作系統(tǒng)中的進(jìn)程狀態(tài)變換 I/O完成請求I/O就 緒 r 執(zhí) 行 e等 待 w進(jìn) 程 調(diào) 度r ew School of Information Science and Engineering 實例 2： “ 七橋問題 ” －哥尼斯堡城的普雷格爾河 圖 論 A B C D A B C D e1 e5 e7 e6 e3 e4 e2 V={A, B, C, D} E={e1, e2, e3, e4, e5 , e6, e7} 后來歐拉證明這樣的路徑根本不存在。 School of Information Science and Engineering 圖 論 實例 3： 在機械加工中，經(jīng)常需要在一塊金屬薄板上鉆若干孔 （或者是機械手在印刷電路板上安裝電子元件） ? 問如何確定鉆孔的次序 ,使之加工的時間最短？ ? 類似的問題： 旅行最優(yōu)問題 , 工程最優(yōu)問題 , 成本最低 .… ... School of Information Science and Engineering 第十四章 圖的基本概念 ?主要內(nèi)容 ? 圖 ? 通路與回路 ? 圖的連通性 ? 圖的矩陣表示 School of Information Science and Engineering 141 圖 ［定義］ 一個圖表示為 G=V(G), E(G), 其中 V(G): G的結(jié)點的非空集合，簡記成 V。 E(G): 是 G的邊的集合， 有時簡記成 E。 ?結(jié)點 (Vertices)： 用 ? 表示 , 旁邊標(biāo)上該結(jié)點的名稱。 ?邊 (Edges) 有向邊 : 帶箭頭的弧線。 從 u到 v的邊 表示成 u,v 無向邊 :不帶箭頭的弧線。 u和 v間的邊 表示成 (u,v) School of Information Science and Engineering 141 圖 實例 1. 設(shè) V1= {v1, v2, …, v5}, E1 = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 則 G1 = V1, E1 為一無向圖 2. 設(shè) V2 = {a, b, c, d}, E2 = {a,a, a,b,a,b,c,b, c,d,d,c,a,d} 則 G2 = V2, E2 為一有向圖 School of Information Science and Engineering 141 圖 相關(guān)概念 ： 1. 圖 ① 可用 G泛指圖（無向的 G或有向的 D ） ② V(G), E(G), V(D), E(D) ③ n階圖 2. n 階零圖與平凡圖（ n 為頂點個數(shù)） 3. 用 ek 表示無向邊或有向邊 4. 頂點與邊的關(guān)聯(lián)關(guān)系 ① 關(guān)聯(lián)、關(guān)聯(lián)次數(shù) ② 環(huán) ③ 孤立點 5. 頂點之間的相鄰與鄰接關(guān)系 School of Information Science and Engineering 141 圖 6. 鄰域與關(guān)聯(lián)集 ① v?V(G) (G為無向圖 ) }{)()(})(),()(|{)(vvNvNvvuGEvuGVuuvNv????????的閉鄰域的鄰域})(|{)( 關(guān)聯(lián)與 veGEeevI ???v 的關(guān)聯(lián)集 }{)()()()()(})(,)(|{)(})(,)(|{)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD????????????????????????????的閉鄰域的鄰域的先驅(qū)元集的后繼元集② v?V(D) (D為有向圖 ) 7. 標(biāo)定圖與非標(biāo)定圖 8. 基圖 School of Information Science and Engineering 141 圖 ?多重圖與簡單圖 簡單圖 ：不含有環(huán)和平行邊的圖。 多重圖 ：含有平行邊的圖。 School of Information Science and Engineering 141 圖 [定義 ] (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) 奇度頂點與偶度頂點 School of Information Science and Engineering 141 圖 [握手定理 ] mvdnii 2)(1???定理 設(shè) G=V,E為任意無向圖， V={v1,v2,… ,vn}, |E|=m, 則 證明： G中每條邊 (包括環(huán) ) 均有兩個端點，所以在計算 G中各頂點度數(shù)之和時，每條邊均提供 2度， m 條邊共提供 2m 度。 定理 設(shè) D=V,E為任意有向圖， V={v1,v2,…, vn}, |E|=m, 則 mvdvdmvdniiniinii ???????????111)()(,2)( 且推論 任何圖 (無向或有向 ) 中，奇度頂點的個數(shù)是偶數(shù)。 School of Information Science and Engineering 141 圖 [無向圖的結(jié)點度序列 ] V={v1, v2, …, vn}為無向圖 G的頂點
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1