離散數(shù)學(xué)圖的基本概念(編輯修改稿)
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)(定理 設(shè) 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)(推論 設(shè) Bl=A+A2+… +Al(l?1), 則 Bl中元素 為 D中長度小于或等于 l 的通路數(shù) ， 為 D中長度小于或等于 l 的回路數(shù) . 26 例 (續(xù) ) 長度 通路 回路 ????????????????????????????????????????????????????1004010410050001010310030104000110020102100300010101100101020001432AAAA合計(jì) 50 8 1 8 1 2 11 3 3 14 1 4 17 3 27 有向圖的可達(dá)矩陣 ????否則可達(dá),1,0 jiijvvp定義 設(shè) D=V,E為有向圖 , V={v1, v2, … , vn}, 令 稱 (pij)n?n為 D的可達(dá)矩陣 , 記作 P(D), 簡記為 P. 性質(zhì) : P(D)主對角線上的元素全為 1. D強(qiáng)連通當(dāng)且僅當(dāng) P(D)的元素全為 1. 28 有向圖的可達(dá)矩陣 (續(xù) ) 例 右圖所示的有向圖 D的可達(dá)矩陣為 ?????????????1101110111110001P29 如何求有向圖的可達(dá)矩陣 ? 設(shè) D=V,E為有向圖， |V|=n, A為 D的鄰接矩陣； ?先求 R＝（ rij）＝ A+A2+...+An ?再求可達(dá)矩陣 P＝（ pij） ( ) 。 ( )1000ij ijijijijP p R rrpr????? ???30 最短路徑及關(guān)鍵路徑 對于有向圖或無向圖 G的每條邊，附加一個實(shí)數(shù) w(e)，則稱w(e)為邊 e上的 權(quán) . G連同附加在各邊上的實(shí)數(shù)，稱為 帶權(quán)圖 . 設(shè)帶權(quán)圖 G=V,E,W,G中每條邊的權(quán)都大于等于 ,v為 G中任意兩個頂點(diǎn)，從 u到 v的所有通路中帶權(quán)最小的通路稱為 u到 v的 最短路徑 . 求給定兩個頂點(diǎn)之間的最短路徑，稱為 最短路徑問題 . 31 算法： Dijkstra(標(biāo)號法 ) 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前 提 ： 把 點(diǎn) 分 為 和 兩 個 集 合 ； 中 的 點(diǎn) 到 的 最 短 路 徑 已 經(jīng) 確 定 ； 初 始 時 ， 只 有 在 中 ； 中 的 點(diǎn) 到 的 最 短 路 徑 確 定 后 ， 稱 獲 得 標(biāo) 號 ， 同 時 把 移 動 到 中如 果 頂 點(diǎn) 與 v 不 相 鄰 ， 則 w=為 頂 點(diǎn) 到 頂 點(diǎn) 最 短 路 徑
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1