運(yùn)籌學(xué)第06章圖論概述-展示頁
2025-05-26 22:15本頁面
【正文】 的圖稱為無圈圖或稱為 林 ?一個連通的無圈圖稱為 樹 ?一個林的每個連通子圖都是一個樹 ?定理 ：關(guān)于樹的以下描述是等價的 ?無圈連通圖 (定義 ) ?無圈圖 G， q(G)=p(G)1(定義 +對頂點(diǎn)個數(shù)用歸納法 ) ?連通圖 G， q(G)=p(G)1(定義 +對頂點(diǎn)個數(shù)用歸納法 ) ?無圈，但增加一條邊可以得到唯一的圈 (定義 +對頂點(diǎn)個數(shù)用歸納法 ) ?連通，但去掉一條邊就不連通 (反證法 ) ?每一對頂點(diǎn)之間有且僅有一條初等鏈 (反證法 ) 圖的基本概念 (13) ?若 T是圖 G的部分圖，且 T是樹，則稱 T為 G的生成樹 (書上稱為部分樹 ) 圖的存儲方式 (1) ?計算機(jī)中存儲圖一般采用矩陣存儲 ?常用的存儲方法有兩種 ?鄰接矩陣 ?關(guān)聯(lián)矩陣 圖的存儲方式 (2) ?對于無向圖，鄰接矩陣存儲方式如下 ?若頂點(diǎn) vi 和 vj 之間沒有邊，則 aij =aji=0 ?若頂點(diǎn) vi 和 vj 之間存在 n條邊，則 aij =aji=n ?注： 一般 i≤ j ?????????????????1100110210020210110210020Av1 v2 v3 v4 v5 圖的存儲方式 (3) v1 v2 v3 v4 v5 ?對于有向圖，鄰接矩陣存儲方式如下 ?若頂點(diǎn) vi 和 vj 之間沒有弧，則 aij =0 ?若頂點(diǎn) vi 和 vj 之間存在 n條弧 (vi , vj )，則 aij =n ?注： 允許 i = j ?????????????????0000011200000100100110010A圖的存儲方式 (4) ?對于無向圖，關(guān)聯(lián)矩陣存儲方式如下 ?若頂點(diǎn) vi 不和邊 ej 相關(guān)聯(lián)，則 bij =0 ?若頂點(diǎn) vi 和邊 ej 相關(guān)聯(lián)，則 bij =1 ?????????????????111000000001111000000011100000100111010000011Bv1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 e9 e9 關(guān)聯(lián)的頂點(diǎn)個數(shù)為 1，是自環(huán) 圖的存儲方式 (5) ?對于有向圖，關(guān)聯(lián)矩陣存儲方式如下 ?若頂點(diǎn) vi 不和弧 ej 相關(guān)聯(lián)，則 bij =0 ?若頂點(diǎn) vi 是弧 ej 的起點(diǎn)，則 bij =1 ?若頂點(diǎn) vi 是弧 ej 的終點(diǎn)，則 bij =1 ?若頂點(diǎn) vi 既是弧 ej 的起點(diǎn)又是弧 ej 的終點(diǎn)，則bij =2 ?????????????????????????011000000202111000000011100000100111010000011Bv1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 e7 e8 e9 簡單圖的權(quán)值矩陣 (1) ?對于賦權(quán)簡單圖，權(quán)值矩陣存儲方式如下 ?若頂點(diǎn) vi 和 vj 之間沒有邊，則 wij =0 ?若頂點(diǎn) vi 和 vj 之間有邊 (vi , vj ) ，則 wij =相應(yīng)邊的權(quán)值 ?注： 無向圖和有向圖均適用，有向圖要注意邊的方向 簡單圖的權(quán)值矩陣 (2) ?????????????????0600760520050400240370030Wv1 v2 v3 v4 v5 3 7 6 2 4 5 v1 v2 v3 v4 v5 3 7 6 2 4 5 ?????????????????0000060520000400202170000W最短路線問題 ?一般針對賦權(quán)連通圖 (有向圖或無向圖皆可 ) ，求兩點(diǎn)之間所經(jīng)路線權(quán)值之和為最小的路線 ?求解該問題可以采用上一章介紹的動態(tài)規(guī)劃的方法 ?該方法適用于無 負(fù)初等回路 (指所有邊的權(quán)值之和為負(fù)值的初等回路 )的賦權(quán)連通圖 (有向圖或無向圖皆可 )；若有負(fù)初等回路，則不存在最短路線 ?該方法需要人工劃分階段，適合人工計算 ?書上介紹的三種算法，不需要明確的劃分階段，較為適合計算機(jī)運(yùn)算 狄克斯拉 (Dijkstra)算法 (1) ?該算法有兩個依據(jù) ?從 v1 到 vn 的最短路線也是從 vn 到 v1 的最短路線 ?對于無向圖必定成立 ?對于有向圖而言， vn 到 v1 的最短路線是指將圖中弧的方向反過來，但權(quán)值不變時的最短路線 ?以 vn 為起點(diǎn)， v1 為終點(diǎn)應(yīng)用動態(tài)規(guī)劃的最優(yōu)性原理 ?第一條依據(jù)保證了按這種方法求得的結(jié)果是從 v1 到 vn 的最短路線 狄克斯拉 (Dijkstra)算法 (2) ?算法步驟 ?已知網(wǎng)絡(luò)的距離矩陣 L=(lij)， lij表示 vi到 vj的弧上的距離權(quán)值 ?令 i=1， S1={v1}， S2={v2, v3, …, v n}，令 P(v1)=0，T(vj)=∞（ vj∈ S2） ?令 T(vj)=min{T(vj)， P(vi)+lij | vj∈ S2} ?令 vk=min{T(vj)| vj∈ S2}， P(vk)=T(vk) ?若 vk=vn，則已經(jīng)找到 v1到 vn的最短距離 P(vk) ?否則，令 i=k，從 S2中刪去 vi，轉(zhuǎn)上一步 狄克斯拉 (Dijkstra)算法 (3) ?該算法適用于無負(fù)初等回路的賦權(quán)連通圖 (有向圖或無向圖皆可 )，但算法本身不能判定圖中是否存在負(fù)初等回路 ?因此，該算法一般應(yīng)用于無負(fù)權(quán)值的賦權(quán)連通有向圖或無向圖 示例 () s a b c d t 5 8 3 9 1 4 9 5 4 3 ?路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長度，試用 Dijkstra 算法求s到 t的最短路線 示例 () s a b c d t 初始值 T( ) 第 1次 P( )+ lij T( ) 第 2次 P( )+ lij T( ) 第 3次 P( )+ lij
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1