離散數(shù)學圖的基本概念(編輯修改稿)
2025-02-12 20:22 本頁面
【文章內(nèi)容簡介】 矩陣 23 v2 v1 v4 v3 1 2 1 00 0 1 0()0 0 0 10 0 1 0AD?????????24 D中的通路及回路數(shù) )(lija)(liia? ?? ?ninjlija1 1)(??niliia1)(定理 設 A為 n階有向圖 D的鄰接矩陣 , 則 Al(l?1)中 元素 為 D中 vi到 vj長度為 l 的通路數(shù) ， 為 vi到自身長度為 l 的回路數(shù) ， 為 D中長度為 l 的通路總數(shù) ， 為 D中長度為 l 的回路總數(shù) . 25 D中的通路及回路數(shù) (續(xù) ) 例 有向圖 D如圖所示 , 求 A, A2, A3, A4, 并回答問題： (1) D中長度為 1, 2, 3, 4的通路各有多 少條 ？ 其中回路分別為多少條 ？ (2) D中長度小于或等于 4的通路為多 少條？其中有多少條回路？ ? ?? ?ninjlijb1 1)(??niliib1)(推論 設 Bl=A+A2+… +Al(l?1), 則 Bl中元素 為 D中長度小于或等于 l 的通路數(shù) ， 為 D中長度小于或等于 l 的回路數(shù) . 26 例 (續(xù) ) 長度 通路 回路 ????????????????????????????????????????????????????1004010410050001010310030104000110020102100300010101100101020001432AAAA合計 50 8 1 8 1 2 11 3 3 14 1 4 17 3 27 有向圖的可達矩陣 ????否則可達,1,0 jiijvvp定義 設 D=V,E為有向圖 , V={v1, v2, … , vn}, 令 稱 (pij)n?n為 D的可達矩陣 , 記作 P(D), 簡記為 P. 性質(zhì) : P(D)主對角線上的元素全為 1. D強連通當且僅當 P(D)的元素全為 1. 28 有向圖的可達矩陣 (續(xù) ) 例 右圖所示的有向圖 D的可達矩陣為 ?????????????1101110111110001P29 如何求有向圖的可達矩陣 ? 設 D=V,E為有向圖， |V|=n, A為 D的鄰接矩陣； ?先求 R＝（ rij）＝ A+A2+...+An ?再求可達矩陣 P＝（ pij） ( ) 。 ( )1000ij ijijijijP p R rrpr????? ???30 最短路徑及關鍵路徑 對于有向圖或無向圖 G的每條邊，附加一個實數(shù) w(e)，則稱w(e)為邊 e上的 權 . G連同附加在各邊上的實數(shù)，稱為 帶權圖 . 設帶權圖 G=V,E,W,G中每條邊的權都大于等于 ,v為 G中任意兩個頂點，從 u到 v的所有通路中帶權最小的通路稱為 u到 v的 最短路徑 . 求給定兩個頂點之間的最短路徑，稱為 最短路徑問題 . 31 算法： Dijkstra(標號法 ) 11 i 1ii( ) * ( ) *1( ) *()1P T P Vv P T V VV P v P1.2.irri i i i irirjvl v v v l vr p llv?j ij前 提 ： 把 點 分 為 和 兩 個 集 合 ； 中 的 點 到 的 最 短 路 徑 已 經(jīng) 確 定 ； 初 始 時 ， 只 有 在 中 ； 中 的 點 到 的 最 短 路 徑 確 定 后 ， 稱 獲 得 標 號 ， 同 時 把 移 動 到 中如 果 頂 點 與 v 不 相 鄰 ， 則 w=為 頂 點 到 頂 點 最 短 路 徑
規(guī)章制度相關推薦
鄂ICP備17016276號-1