《圖論與網(wǎng)絡(luò)分析》PPT課件

圖 論 與 網(wǎng) 絡(luò) 分 析 （ Graph Theory and Network Analysis）教 學(xué) 要 求 ：了 解 圖 論 的 基 本 概 念 ， 理 論 和 方 法 以 及 應(yīng) 用掌 握 最 小 樹 以 及 最 短 路 問 題 等 模 型 及 其 基 本 算 法 。掌 握 歐 拉 道 路 、 回 路 的 判 斷 和 構(gòu) 造 方 法 18世 紀(jì) ， 哥 尼 斯 堡 城 中 有 一 條 普 雷 格 爾 河 ， 河 上 有 七 座 橋 將 河 中 的兩 個(gè) 小 島 與 河 岸 連 接 起 來 。 人 們 提 出 了 這 樣 的 問 題 ： 一 個(gè) 散 步 者 能 否從 某 地 出 發(fā) ， 走 遍 七 橋 且 每 座 橋 恰 好 經(jīng) 過 一 次 ， 最 后 回 到 原 地 ？ 陸 地 A陸 地 B島 D 島 C AD B C 1736年 瑞 士 數(shù) 學(xué) 家 歐 拉 將 兩 岸 和 小 島 抽 象 為 四 個(gè) 點(diǎn) ，將 橋 抽 象 為 七 條 邊 ， 此 問 題 歸 結(jié) 為 一 筆 畫 問 題 。圖 論 起 源 第 一 節(jié) 圖 論 的 概 念圖 論 的 圖 與 一 般 幾 何 圖 形 或 函 數(shù) 圖 形 是 完 全 不 同 的n 圖 論 中 的 圖 :由 一 些 點(diǎn) 和 連 接 點(diǎn) 的 線 所 組 成 的 “ 圖 形 ”n 點(diǎn) 和 線 的 位 置 是 任 意 的n 線 的 曲 直 、 長(zhǎng) 短 與 實(shí) 際 無 關(guān) ， 代 表 的 只 是 點(diǎn) 與 點(diǎn) 之間 的 相 互 關(guān) 系v1 v2v 3 v4 v1v2v3 v4 3 4 512 無 向 圖 的 基 本 概 念 G=(V,E) V=viG的 頂 點(diǎn) 集 合E=ek G的 邊 集 合 ，且 ek=（ vi,vj） 為 無 序 二 元 組 ,表 示 ek連 接 vi,vjn(G)=|V|=nG的 頂 點(diǎn) 數(shù)m(G)=|E|=mG的 邊 數(shù)頂 點(diǎn) 相 鄰 兩 頂 點(diǎn) 之 間 有 一 條 邊 ，頂 點(diǎn) 為 該 邊 的 端 點(diǎn) ， 邊與 其 端 點(diǎn) 關(guān) 聯(lián) 。邊 相 鄰e1e2 e3e4e5 e6 e7 兩 邊 與 同 一 頂 點(diǎn) 關(guān) 聯(lián) ，即 兩 邊 有 共 同 的 端 點(diǎn) 。環(huán) 兩 端 點(diǎn) 重 合 為 一 點(diǎn) 的 邊 ，如 e1多 重 邊 兩 點(diǎn) 之 間 多 于 一 條 邊 ， 如e6， e7簡(jiǎn) 單 圖 不 含 環(huán) 和 多 重 邊 的 圖 ， 去掉 e 和 e7.（ 不 特 指都 是 簡(jiǎn) 單 圖 ）完 全 圖 每 對(duì) 頂 點(diǎn) 之 間 都 有 邊 相 連的 無 向 簡(jiǎn) 單 圖 ， n個(gè) 頂 點(diǎn)的 無 向 完 全 圖 記 為 Kn次 與 頂 點(diǎn) v相 關(guān) 聯(lián) 的 邊 數(shù) ， 即以 v為 頂 點(diǎn) 的 邊 數(shù) 記 為 d(v),環(huán) 記 2次 。 d(1)=4.奇 點(diǎn) ， 偶 點(diǎn) 次 為 奇 數(shù) 的 點(diǎn) 為 奇 點(diǎn) ， 次 為偶 數(shù) 的 點(diǎn) 為 偶 點(diǎn) 。次 為 1的 點(diǎn) 為 懸 掛 點(diǎn) 。若 4， 5之 間 有 一 條 邊 ， 則 5為 懸 掛 點(diǎn) 。孤 立 點(diǎn) 次 為 0的 點(diǎn) 為 孤 立 點(diǎn) ， 5為 孤立 點(diǎn) 。Kn有 邊 條2nC 懸 掛 點(diǎn) 無 向 圖 的 基 本 概 念 二 部 圖 ： 圖 G=(V,E)， 頂 點(diǎn) 集 合 V可 分 為 兩 個(gè) 非空 子 集 X,Y， 知 X Y=V， XY=， E中 每 條 邊的 兩 個(gè) 端 點(diǎn) ， 一 個(gè) 在 X中 ， 一 個(gè) 在 Y中 ， 則 稱 G為二 部 圖 ， 記 為 G=（ X,Y,E）v1 v2v 3 v4 v2v4 v3 v1 有 向 圖 的 基 本 概 念 G=(V,E) V=vi： G的 頂 點(diǎn) 集 合E=ek： G的 有 向 邊 (弧 )集 合 ，且 ek=（ vi,vj） 為 有 序 二 元 組 ,表 示 弧 ek從 vi（ 始 點(diǎn) ） 指 向 vj（ 終 點(diǎn) ）環(huán)有 向 圖 中 ， 始 點(diǎn) 、 終 點(diǎn) 重合 的 弧 為 環(huán) ， 如 e1多 重 邊始 點(diǎn) 和 終 點(diǎn) 都 相 同 的 弧 為多 重 邊 ， 如 e6， e7非 多重 邊 。 簡(jiǎn) 單 有 向 圖不 含 環(huán) 和 多 重 邊 的 有 向 圖 ，去 掉 e1有 向 完 全 圖以 任 意 點(diǎn) 為 始 點(diǎn) ， 另 一 點(diǎn) 為終 點(diǎn) 都 有 一 條 弧 的 簡(jiǎn) 單 有向 圖 ， n個(gè) 頂 點(diǎn) 的 有 向 完全 圖 有 弧 n(n-1)條出 次 ， 入 次 ， 次 3 4 512 e1e2 e3e4e5 e6 e7 以 頂 點(diǎn) v為 始 點(diǎn) 的 弧 數(shù) 為 v的 出 次 ， 記為 ； 以 頂 點(diǎn) v為 終 點(diǎn) 的 弧 數(shù) 為 v的 入 次 ， 記 為 ； 頂 點(diǎn) v的 出 次與 入 次 之 和 為 點(diǎn) v的 次 。( )d v ( )d v 網(wǎng) 絡(luò) （ 賦 權(quán) 圖 ）在 無 向 圖 的 邊 （ 或 有 向 圖 的 弧 ） 上 標(biāo) 上 實(shí) 數(shù) ，稱 為 該 邊 （ 或 弧 ） 的 權(quán) ， 無 向 （ 有 向 ） 圖 連同 它 邊 上 的 權(quán) 稱 為 一 個(gè) 網(wǎng) 絡(luò) 賦 權(quán) 圖 ， 簡(jiǎn) 稱 網(wǎng)絡(luò) 。 （ 無 向 網(wǎng) 絡(luò) ， 有 向 網(wǎng) 絡(luò) ） 子 圖( , ), , ,( , ),G V E E E V V E VG V E GV V G G 若 且 中 的 邊 僅 與中 的 頂 點(diǎn) 關(guān) 聯(lián) ， 稱 為 的 一 個(gè) 子 圖 。特 別 ， 若 則 為 的 生 成 子 圖 (支 撐 子 圖 ) 3 4 512 e1e2 e3e4e5 e6 e7 412e2 e3e4e5 3 412e2 e3e4e5 道 路 ， 回 路 3 4 512 e1e2 e3e4e5 e6 e7 110 1 1 2 00( , , , , , , , )( , )kti i i i i ik ikit i it i iki ikGv e v e v e ve v v v vv v 圖 中 的 一 個(gè) 點(diǎn) 邊 交 替 序 列（ 其 中 ） 為 連 接 與 的 一 條 鏈 。該 鏈 中 點(diǎn) 不 重 ， 邊 不 重 為 初 等 鏈 ；該 鏈 中 與 為 同 一 點(diǎn) 時(shí) 為 圈 ；圈 中 點(diǎn) 邊 不 重 為 初 等 圈 ；無 向 圖 鏈 和 圈 也 稱 為 道 路 和 回 路 。G有 向 圖 不 考 慮 方 向 ， 同 樣 定 義 鏈 和 圈 ，若 鏈 、 圈 上 弧 方 向 相 同 時(shí) ， 稱 為 道 路 、 回 路 。 連 通 圖p點(diǎn) i和 j點(diǎn) 是 連 通 的 ： i,j之 間 存 在 一 條 鏈pG是 連 通 的 ： G中 任 意 兩 點(diǎn) 都 是 連 通 的 p不 連 通 圖 可 以 分 為 若 干 連 通 子 圖 ， 每 個(gè) 稱為 原 圖 的 分 圖 。 關(guān) 聯(lián) 矩 陣圖 的 矩 陣 表 示 關(guān) 聯(lián) 矩 陣 示 例右 圖 的 關(guān) 聯(lián) 矩 陣 是 右 圖 的 關(guān) 聯(lián) 矩 陣 是 1 34 521 3 42 11010000 10100100 01101010 00011001 0000011154321 11000 10110 01101 000114321 e1e2 e4e7e6 e5e8e3 e1e2 e3 e4e5 鄰 接 矩 陣 鄰 接 矩 陣 示 例右 圖 的 鄰 接 矩 陣 是 右 圖 的 鄰 接 矩 陣 是 1 34 521 3 42 01110 10101 11011 10101 0111054321 54321 0100 0000 1100 01104321 4321 主 要 結(jié) 論1: ( ) 2 2v VTh d v E m 2:Th 圖 中 奇 點(diǎn) 必 為 偶 數(shù) 個(gè) 。3: ( ) ( ) v V v VTh d v d v 圖 論 基 本 概 念 應(yīng) 用p 例 1： 證 明 在 9座 工 廠 之 間 ， 不 可 能 每 座 工 廠 只 與 其 他 3座工 廠 有 業(yè) 務(wù) 聯(lián) 系 ， 也 不 可 能 只 有 4座 工 廠 與 偶 數(shù) 個(gè) 工 廠 有業(yè) 務(wù) 聯(lián) 系 。將 9座 工 廠 看 做 9個(gè) 點(diǎn) ， 他 們 有 聯(lián) 系 用 邊 相 連 ， 若 每 座 工 廠只 與 其 他 3座 工 廠 有 業(yè) 務(wù) 聯(lián) 系 ， 則 每 個(gè) 點(diǎn) 的 次 都 為 3， 從 而總 次 為 27， 非 偶 數(shù) ， 與 總 次 為 邊 的 2倍 矛 盾 。 從 而 得 證 。若 只 有 4座 工 廠 與 偶 數(shù) 個(gè) 工 廠 有 業(yè) 務(wù) 聯(lián) 系 ， 則 其 余 5座 與 奇數(shù) 個(gè) 工 廠 有 業(yè) 務(wù) 聯(lián) 系 ， 從 而 總 次 為 4*偶 +5*奇 =奇 數(shù)非 偶 數(shù) ， 矛 盾 。 從 而 得 證 。 例 2： 6個(gè) 人 圍 成 圓 圈 就 座 ， 每 個(gè) 人 恰 好 只 與 相 鄰 者 不 認(rèn) 識(shí) ，是 否 可 以 重 新 就 座 ， 使 每 個(gè) 人 都 與 鄰 座 認(rèn) 識(shí) ？將 6個(gè) 人 看 做 6個(gè) 點(diǎn) ， 相 互 認(rèn) 識(shí) 用 邊 表 示1 62 3 4 5 要 求 重 排 之 后 每 個(gè) 人 與 鄰 座 認(rèn) 識(shí)只 需 找 到 一 個(gè) 序 列 ， 該 序 列 中 前后 兩 個(gè) 點(diǎn) 是 相 鄰 的 就 可 以 了 。 如1-3-5-2-6-4-11 4 3 5 2 6 例 3 甲 、 乙 、 丙 、 丁 、 戊 5個(gè) 運(yùn) 動(dòng) 員 報(bào) 名 參 加 A,B,C,D,E，F(xiàn)六 個(gè) 項(xiàng) 目 比 賽 ， 報(bào) 名 情 況 見 下 表 （ 打 *表 示 各 運(yùn) 動(dòng) 員 報(bào) 名參 加 的 比 賽 項(xiàng) 目 ） 。 問 如 何 安 排 項(xiàng) 目 ， 使 每 名 運(yùn) 動(dòng) 員 不 連 續(xù)參 加 兩 項(xiàng) 比 賽 ？將 6個(gè) 項(xiàng) 目 看 做 6個(gè) 點(diǎn) ， 同 一 個(gè) 人 參 加 的 項(xiàng) 目 之 間 有 邊要 求 安 排 項(xiàng) 目 ， 每 名 運(yùn) 動(dòng) 員 不 連續(xù) 參 加 兩 項(xiàng) 比 賽 ， 只 需 找 到 一 個(gè)遍 歷 點(diǎn) 的 序 列 ， 該 序 列 中 前 后 兩個(gè) 點(diǎn) 是 不 相 鄰 的 就 可 以 了 。 如 A-C-D-E-F-BA B C D E F甲 * *乙 * * *丙 * *丁 * *戊 * *AB C D EF 練 習(xí) 10個(gè) 研 究 生 參 加 6門 課 考 試 ， 每 個(gè) 研 究 生 考 試 課 程 見下 表 ， 要 求 上 下 午 各 排 一 門 課 ， 每 人 每 天 最 多 考 一 門 ， 且 A必 須 第 一 天 上 午 ， F必 須 最 后 考 ， B要 安 排 在 下 午 考 ， 試 給出 一 個(gè) 考 試 安 排 表 。A B C D E F1 * * *2 * *3 * *4 * * *5 * * *6 * *7 * * * 8 * *9 * * *10 * * * AECBDF 歐 拉 回 路n 連 通 圖 G中 若 存 在 一 條 道 路 ， 經(jīng) 每 邊 一 次 且 僅 一次 ， 則 該 道 路 為 歐 拉 道 路n 若 存 在 一 條 回 路 ， 經(jīng) 每 邊 一 次 且 僅 一 次 ， 該 回 路為 歐 拉 回 路 。n 有 歐 拉 回 路 的 圖 稱 為 歐 拉 圖 。 結(jié) 論 ：p Th1： 無 向 連 通 圖 G為 歐 拉 圖 充 要 條 件 是 G中 無 奇 點(diǎn) 。p Th2： 無 向 連 通 圖 G為 歐 拉 圖 充 要 條 件 是 G的 邊 集 可 分 為若 干 初 等 回 路 。p Th3： 無 相 連 通 圖 G為 歐 拉 道 路 充 要 條 件 是 G中 恰 有 2個(gè)奇 點(diǎn) 。p Th4： 連 通 有 向 圖 G為 歐 拉 圖 充 要 條 件 是 他 每 個(gè) 頂 點(diǎn) 的 出次 等 于 入 次 。p Th5： 連 通 有 向 圖 G為 歐 拉 道 路 充 要 條 件 是 這 個(gè) 圖 中 除 了兩 個(gè) 頂 點(diǎn) 之 外 ， 其 余 每 個(gè) 頂 點(diǎn) 出 次 等 于 入 次 ， 且 這 兩 頂 點(diǎn)中 ， 一 個(gè) 頂 點(diǎn) 入 次 比 出 次 多 1， 另 一 個(gè) 出 次 比 入 次 多 1. 一 個(gè) 散 步 者 能 否 從 某 地 出 發(fā) ， 走 遍 七 橋 且 每 座 橋 恰 好 經(jīng)過 一 次 ， 最 后 回 到 原 地 ？ 即 是 否 存 在 歐 拉 回 路 ？陸 地 A陸 地 B島 D 島 C AD B C每 點(diǎn) 都 是 奇 點(diǎn) ， 所 以 不 是 歐 拉 圖 ， 即 不 存 在 歐 拉 回 路 。如 果 存 在 歐 拉 回 路 ， 如 何 找 到 該 回 路 ？ 歐 拉 回 路 的 構(gòu) 造 方 法p 從 G中 任 意 點(diǎn) v1出 發(fā) 找 到 一 個(gè) 初 等 回 路 c1， 再 從圖 中 去 掉 c1， 在 剩 余 的 圖 中 再 找 初 等 回 路c2， ， 一 直 找 到 圖 中 所 有 的 邊 都 被 包 含 在 這些 初 等 回 路 中 為 止 ， 最 后 把 這 些 回 路 連 續(xù) 起 來 即得 該 圖 的 歐 拉 回 路 。 下 面 兩 個(gè) 圖 是 否 可 以 一 筆 畫 出 ？V3V1V2 V6V5 V4 12 3 45 67 89 10(2， e23,3,e34,4,e41,1,e12,2,e27,7,e75,5,e56,6,e67,7,e79,9,e910,10,e108,8,e89,9,e93,3,e310,10,e104,4,e48,8,e86,6,e61,1,e15,5) 第 二 節(jié) 最 小 樹 問 題1v 一 、 樹 的 定 義 與 樹 的 特 征定 義 連 通 且 不 含 圈 的 無 向 圖 稱 為 樹 常 用 T表 示 . 樹 中 的 邊 稱 為 樹 枝 . 樹 中 次 為 1的 頂 點(diǎn) 稱 為 樹 葉 ，次 大 于 1的 點(diǎn) 為 分 枝 點(diǎn) 。2v 3v 4v5v 定 理 設(shè) T是 具 有 n個(gè) 頂 點(diǎn) 的 圖 ， 則 下 述 命 題 等 價(jià) ：1) T是 樹 （ T無 圈 且 連 通 ） ；2) T無 圈 ， 且 有 n-1條 邊 ；3) T連 通 ， 且 有 n-1條 邊 ；4) T無 圈 ， 但 添 加 任 一 條 新 邊 恰 好 產(chǎn) 生 一 個(gè) 圈 ; 5) T連 通 ， 且 刪 去 一 條 邊 就 不 連 通 了6) T中 任 意 兩 頂 點(diǎn) 間 有 唯 一 一 條 路 . 二 、 圖 的 生 成 樹定 義 若 T是 包 含 圖 G的 全 部 頂 點(diǎn) 的 子 圖 ,它 又 是 樹 ,則 稱 T是 G的 生 成 樹 . 圖 G中 不 在 生 成 樹 的 邊 叫 做 弦 .定 理 圖 G=(V,E)有 生 成 樹 的 充 要 條 件 是 圖 G是 連 通 的 .找 圖 中 生 成 樹 的 方 法可 分 為 兩 種 ： 避 圈 法 和 破 圈 法 A 避 圈 法 : 深 探 法 和 廣 探 法 B 破 圈 法 A 避 圈 法 這 種 方 法 就 是 在 已 給 的 圖 G中 ， 每 步 選 出 一 條 邊 使它 與 已 選 邊 不 構(gòu) 成 圈 ， 直 到 選 夠 n-1條 邊 為 止 . 這種 方 法 可 稱 為 “ 避 圈 法 ” 或 “ 加 邊 法 ”在 避 圈 法 中 ， 按 照 邊 的 選 法 不 同 ， 找 圖 中 生 成 樹的 方 法 可 分 為 兩 種 ： 深 探 法 和 廣 探 法 . a) 深 探 法 若 這 樣 的 邊 的 另 一 端 均 已 有 標(biāo) 號(hào) ， 就 退 到 標(biāo) 號(hào) 為步 驟 如 下 ：i) 在 點(diǎn) 集 V中 任 取 一 點(diǎn) u,ii) 若 某 點(diǎn) v已 得 標(biāo) 號(hào) ， 檢端 是 否 均 已 標(biāo) 號(hào) . 若 有 邊 (v,w)之 w未 標(biāo) 號(hào) ,則 給w代 v， 重 復(fù) ii).i-1的 r點(diǎn) ,以 r代 v,重 復(fù) ii),直 到 全 部 點(diǎn) 得 到 標(biāo) 號(hào) 為 止 .給 以 標(biāo) 號(hào) 0.查 一 端 點(diǎn) 為 v的 各 邊 ， 另 一w以 標(biāo) 號(hào) i+1， 記 下 邊 (v,w).令例 用 深 探 法 求 出 下 圖 的 一 棵 生 成 樹 0 1 2345 6 789 10 111213 13a) 深 探 法0 1 2345 6 789 10 1112 例 用 深 探 法 求 出 下 圖 的 一 棵 生 成 樹 012345789 10 11 12 136 3b)廣 探 法步 驟 如 下 ：i) 在 點(diǎn) 集 V中 任 取 一 點(diǎn) u,ii) 令 所 有 標(biāo) 號(hào) i的 點(diǎn) 集 為是 否 均 已 標(biāo) 號(hào) . 對(duì) 所 有 未 標(biāo)號(hào) 之 點(diǎn) 均 標(biāo) 以 i+1,記 下 這 些 iii) 對(duì) 標(biāo) 號(hào) i+1的 點(diǎn) 重 復(fù) 步步 驟 ii)， 直 到 全 部 點(diǎn) 得 到給 u以 標(biāo) 號(hào) 0.Vi,檢 查 Vi,VVi中 的 邊 端 點(diǎn)邊 . 例 用 廣 探 法 求 出 下 圖 的 一 棵 生 成 樹 1 0 1221 3 212 2 34標(biāo) 號(hào) 為 止 . 3b)廣 探 法 例 用 廣 探 法 求 出 下 圖 的 一 棵 生 成 樹 1 0 1221 3 212 2 34顯 然 圖 的 生 成 樹 不 唯 一 . 0 43 21 1 1 12222 3 3 B 破 圈 法 相 對(duì) 于 避 圈 法 ， 還 有 一 種 求 生 成 樹 的 方 法 叫 做“ 破 圈 法 ” . 這 種 方 法 就 是 在 圖 G中 任 取 一 個(gè) 圈 ，任 意 舍 棄 一 條 邊 ， 將 這 個(gè) 圈 破 掉 ， 重 復(fù) 這 個(gè) 步 驟直 到 圖 G中 沒 有 圈 為 止 .例 用 破 圈 法 求 出下 圖 的 一 棵 生 成 樹 . B 破 圈 法例 用 破 圈 法 求 出 下 圖 的 另 一 棵 生 成 樹 .不 難 發(fā) 現(xiàn) ， 圖的 生 成 樹 不 是唯 一 的 . 三 、 最 小 生 成 樹 與 算 法 介 紹 最 小 樹 的 兩 種 算 法 ：Kruskal算 法 （ 或 避 圈 法 ） 和 破 圈 法 . A Kruskal算 法 （ 或 避 圈 法 ）步 驟 如 下 ： 1) 選 擇 邊 e1， 使 得 w(e1)盡 可 能 小 ；2) 若 已 選 定 邊 ， 則 從ieee ,., 21 ,., 21 ieeeE中 選 取 ， 使 得 :1iei) 為 無 圈 圖 ，,., 121 ieeeG ii) 是 滿 足 i)的 盡 可 能 小 的 權(quán) ，)( 1iew 3) 重 復(fù) 步 驟 2） ， 直 至 選 夠 n-1條 邊 .定 理 由 Kruskal算 法 構(gòu) 作 的 任 何 生 成 樹 * 1 2 1 , ,., nT G e e e 都 是 最 小 樹 . , 876432 eeeeee例 用 Kruskal算 法 求 下 圖 的 最 小 樹 .在 左 圖 中 權(quán) 值,., 821 eee最 小 的 邊 有 任 取 一 條 , 51 ee ,1e 在 中 選 取 權(quán) 值,., 832 eee ,5e最 小 的 邊 中 權(quán) 值 最 小 邊 有 , 從 中 選：73,ee;3e任 取 一 條 邊 , 87642 eeeee中 選 取 在 中 選 取 ,7e已 經(jīng) 選 夠 5-1條 邊 ， 從 而 最 小 樹構(gòu) 造 結(jié) 束 。 B破 圈 法算 法 2 步 驟 如 下 ： 1) 從 圖 G中 任 選 一 棵 樹 T1.2) 加 上 一 條 弦 e1， T1+e1中 立 即 生 成 一 個(gè) 圈 . 去 掉 此 圈 中 最 大 權(quán) 邊 ， 得 到 新樹 T2,以 T2代 T1,重 復(fù) 2)再檢 查 剩 余 的 弦 ， 直 到 全部 弦 檢 查 完 畢 為 止 .例 用 破 圈 法 求 下 圖 的 最 小 樹 .先 求 出 上 圖 的 一 棵 生 成 樹 . 加 以 弦 e 2,得 到 的 圈 v1v3v2v1,去 掉 最 大 的 權(quán) 邊 e2,得 到 一 棵 新樹 仍 是 原 來 的 樹 ； 2e 再 加 上 弦 e7， 得 到 圈 v4v5v2v4, 27e去 掉 最 大 的 權(quán) 邊 e6， 得 到 一 棵新 樹 ； 如 此 重 復(fù) 進(jìn) 行 ， 直 到 全部 的 弦 均 已 試 過 ,得 最 小 樹 . 例 ： 一 家 企 業(yè) 分 別 要 在 6間 辦 公 室 鋪 設(shè) 網(wǎng) 線 接 入 口 ，網(wǎng) 線 的 可 行 走 線 方 式 如 下 圖 所 示 ， 如 何 鋪 設(shè) 網(wǎng) 線才 能 使 網(wǎng) 線 總 長(zhǎng) 為 最 短 ？ 最 短 網(wǎng) 線 總 長(zhǎng) 度 為 最 小 樹 權(quán) 之 和 2+3+4+6+6=21 8 2 3 54 6 6 6 8v1 v 4v2v3 v5 v6 第 三 節(jié) 最 短 路 問 題 狄 克 斯 特 拉 (Dijkstra)算 法u 路 權(quán) ： 弧 (vi, vj)的 權(quán) 為 lij； 路 權(quán) 是 路 p中 各 條 弧 權(quán) 之 和u 最 短 路 ： 在 所 有 從 vs到 vt 的 路 p中 ， 求 一 條 路 權(quán) 最 短的 路u 算 法 說 明 ：n1959年 提 出 ， 目 前 公 認(rèn) 的 最 短 路 算 法 n 適 合 于 求 解 所 有 弧 權(quán) wij 0的 最 短 路 問 題 第 三 節(jié) 最 短 有 向 路 問 題u 基 本 思 路 :n 從 始 點(diǎn) vs 出 發(fā) ， 逐 步 探 尋 ， 給 每 個(gè) 點(diǎn) 標(biāo) 號(hào) ；n 標(biāo) 號(hào) 分 永 久 標(biāo) 號(hào) P(vk)和 臨 時(shí) 標(biāo) 號(hào) T(vk) 兩 種 ：p永 久 標(biāo) 號(hào) P(vk) 是 從 點(diǎn) vs vk 的 最 短 路 權(quán)p臨 時(shí) 標(biāo) 號(hào) T(vk) 是 從 點(diǎn) vs vk 最 短 路 權(quán) 的 上界n 算 法 的 每 一 步 從 臨 時(shí) 標(biāo) 號(hào) 集 中 選 最 小 者 變 為 永 久 標(biāo)號(hào) ； n 經(jīng) 過 逐 次 改 變 ， 就 可 以 得 到 從 點(diǎn) vs 到 各 點(diǎn) 的 最 短 路p 標(biāo) 號(hào) 形 式 ：n 單 標(biāo) 號(hào) 法 是 對(duì) 每 一 點(diǎn) 賦 予 一 個(gè) 路 權(quán) 標(biāo) 號(hào)n 雙 標(biāo) 號(hào) 法 是 對(duì) 每 一 點(diǎn) 賦 予 兩 個(gè) 標(biāo) 號(hào) ： 路 標(biāo) 、 路 權(quán) 。 狄 克 斯 特 拉 (Dijkstra)算 法 步 驟 1) ( ) 0, ( )2) :( , ) ,( ) min ( ), ( )3)( ) min ( )s s ii j i jj j j j i iji i iv P P v T T vv P v v v Ev T v TT v T v P v lT PP v T v P Pv v 給 以 標(biāo) 號(hào) ， 其 余 各 點(diǎn) 均 給 標(biāo) 號(hào) ，若 為 剛 得 到 的 標(biāo) 號(hào) 的 點(diǎn) ， 考 慮 這 樣 的 點(diǎn) 且為 標(biāo) 號(hào) 。 對(duì) 的 標(biāo) 號(hào) 進(jìn) 行 如 下 修 改 ：比 較 所 有 具 有 標(biāo) 號(hào) 的 點(diǎn) ， 把 最 小 者 改 為 標(biāo) 號(hào) ， 即 ：當(dāng) 存 在 兩 個(gè) 以 上 最 小 者 時(shí) ， 可 同 時(shí) 改 為 標(biāo) 號(hào) ， 若 全 部 點(diǎn) 均 為標(biāo) 號(hào) ， 則 停 止 。 否 則 ， 用 代 2i轉(zhuǎn) 回 ） 例 ： 從 發(fā) 電 廠 （ 記 為 節(jié) 點(diǎn) 1） 向 某 城 市 （ 記 為 節(jié) 點(diǎn) 6）輸 送 電 ， 必 須 通 過 中 轉(zhuǎn) 站 （ 記 為 節(jié) 點(diǎn) 2， 3， 4， 5）轉(zhuǎn) 送 。 圖 給 出 了 兩 節(jié) 點(diǎn) 間 的 距 離 。 電 力 公 司 希 望 選擇 合 適 的 中 轉(zhuǎn) 站 ， 使 從 電 廠 到 城 市 的 傳 輸 路 線 最 短 。即 從 節(jié) 點(diǎn) 1到 節(jié) 點(diǎn) 6的 最 短 路 徑 。 這 就 是 一 個(gè) 最 短 路問 題 。 單 標(biāo) 號(hào) 求 最 短 路1 32 54 643 323 22 第 0步 ： P(1)=0,T(i)=+ ； 第 1步 ： 與 1相 連 的 標(biāo) 號(hào) 為 2,3， 均 是 T標(biāo) 號(hào) ， 修 改 2,3的 標(biāo) 號(hào) ， T(2)=minT(2),P(1)+l12=4,T(3)=3；在 所 有 的 T標(biāo) 號(hào) 中 ， 3的 標(biāo) 號(hào) 最 小 ， 改 3的 標(biāo) 號(hào) 為 P(3)=3； 第 2步 ： 修 改 與 3相 連 的 T標(biāo) 號(hào) ； 在 所 有 剩 下 的 T標(biāo) 號(hào) 中 ， 2的 標(biāo) 號(hào) 最 小 ， 改 為 P(2)=4； 第 3步 ： 修 改 與 2相 連 的 T標(biāo) 號(hào) ； 在 所 有 剩 下 的 T標(biāo) 號(hào) 中 ， 5的 標(biāo) 號(hào) 最 小 ， 改 為 P(5)=6； 第 4步 ： 修 改 與 5相 連 的 T標(biāo) 號(hào) ； 在 所 有 剩 下 的 T標(biāo) 號(hào) 中 ， 4的 標(biāo) 號(hào) 最 小 ， 改 為 P(4)=7； 第 5步 ： 修 改 與 4相 連 的 T標(biāo) 號(hào) ； 只 剩 下 節(jié) 點(diǎn) 6是 T標(biāo) 號(hào) ， 修 改 6的 標(biāo) 號(hào) ， P(6)=8。 從 節(jié) 點(diǎn) 6開 始 回 退 ， 得 到 最 短 路 。P(1)=0 T(3)=+T(2)=+3 T(5)=+P 64 T(4)=+ T(6)=+P 7P 8P P P(6)=8 P(5)=6 P(3)=3 P(1)=0 例 ： 雙 標(biāo) 號(hào) 法 求 下 圖 網(wǎng) 絡(luò) 最 短 路3 9 47 3 2 6 14 12 87110sv 2v1v 5v4v6v3v tv 第 一 步 ： 3 9 47 32 6 14 12 87110( ,0)sv ( ,3)sv ( ,9)sv ( ,10)sv ( , )sv ( , )sv ( , )sv ( , )sv sv sv 2v1v 5v4v6v3v tv 第 二 步 ： 3 9 47 32 6 14 12 87110( ,0)sv ( ,9)sv ( ,10)sv ( , )sv ( , )sv sv 2v1v 5v4v6v3v tv ( ,3)sv 1( ,5)v 1( ,7)v 第 三 步 ： 3 9 47 32 6 14 12 87110( ,0)sv ( ,9)sv ( ,10)sv ( , )sv sv 2v1v 5v4v6v3v tv ( ,3)sv 5( ,6)v 5( ,13)v1( ,5)v 最 終 ： 依 此 類 推 ， 重 復(fù) 上 述 標(biāo) 號(hào) 過 程 。 得 最 短 路 。 3 9 47 32 6 14 12 87110( ,0) sv sv 2v1v 5v4v6v3v tv( ,3)sv 3( ,11)v 6( ,12)v4( ,9)v 5( ,6)v1( ,5)v4( ,7)v 練 習(xí) ： 求 下 圖 中 v1到 v8的 最 短 距 離v1 v2v3 v4v5 v6v7 v846 44 5 9 415 7 57 6 v8 （ v1， 4）（ v1， 6） （ v2， 8）（ v2， 9） （ v5， 13）（ v5， 14） （ v7， 15）（ v1， 0） v7v5v2v1