第 十 一 章 圖 與 網 絡 分 析Graph theory and network analysis 第 十 一 章 圖 與 網 絡 分 析11.1 引 言 引 言圖 論 是 專 門 研 究 圖 的 理 論 的 一 門 數 學 分 支 ，屬 于 離 散 數 學 范 疇 ， 與 運 籌 學 有 交 叉 ， 它 有200多 年 歷 史 ， 大 體 可 劃 分 為 三 個 階 段 。 引 言第 一 階 段 從 十 八 世 紀 中 葉 到 十 九 世 紀 中 葉 ， 處 于萌 芽 階 段 ， 多 數 問 題 由 游 戲 而 產 生 ， 最有 代 表 性 的 工 作 是 所 謂 的 Euler七 橋 問題 ， 即 一 筆 畫 問 題 。 引 言第 二 階 段 從 十 九 世 紀 中 葉 到 二 十 世 紀 中 葉 ， 這 時 ，圖 論 問 題 大 量 出 現 ， 如 Hamilton問 題 ，地 圖 染 色 的 四 色 問 題 以 及 可 平 面 性 問 題 等 ，這 時 ， 也 出 現 用 圖 解 決 實 際 問 題 ， 如Cayley把 樹 應 用 于 化 學 領 域 ， Kirchhoff用 樹 去 研 究 電 網 絡 等 . 引 言第 三 階 段 二 十 世 紀 中 葉 以 后 ， 由 生 產 管 理 、 軍 事 、交 通 、 運 輸 、 計 算 機 網 絡 等 方 面 提 出 實 際問 題 ， 以 及 大 型 計 算 機 使 大 規(guī) 模 問 題 的 求解 成 為 可 能 ， 特 別 是 以 Ford和 Fulkerson建 立 的 網 絡 流 理 論 ， 與 線 性 規(guī) 劃 、 動 態(tài) 規(guī)劃 等 優(yōu) 化 理 論 和 方 法 相 互 滲 透 ， 促 進 了 圖論 對 實 際 問 題 的 應 用 。 哥 尼 斯 堡 七 橋 問 題 哥 尼 斯 堡 七 橋 問 題 最 后 ， 數 學 家 Euler在 1736年 巧 妙 地 給 出 了這 個 問 題 的 答 案 ， 并 因 此 奠 定 了 圖 論 的 基 礎Euler把 A、 B、 C、 D四 塊 陸 地 分 別 收 縮 成 四 個頂 點 ， 把 橋 表 示 成 連 接 對 應 頂 點 之 間 的 邊 ， 問題 轉 化 為 從 任 意 一 點 出 發(fā) ， 能 不 能 經 過 各 邊 一次 且 僅 一 次 ， 最 后 返 回 該 點 。 這 就 是 著 名 的Euler問 題 。 哥 尼 斯 堡 七 橋 問 題 哥 尼 斯 堡 七 橋 問 題 圍 坐 問 題 有 7個 人 圍 桌 而 坐 ， 如 果 要 求 每 次 相 鄰 的人 都 與 以 前 完 全 不 同 ， 試 問 不 同 的 就 座 方案 共 有 多 少 種 ？用 頂 點 表 示 人 ， 用 邊 表 示 兩 者 相 鄰 ， 因為 最 初 任 何 兩 個 人 都 允 許 相 鄰 ， 所 以 任何 兩 點 都 可 以 有 邊 相 連 。 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 假 定 第 二 次 就 座 方 案 是（ 1， 3， 5， 7， 2， 4， 6， 1） ，那 么 第 三 次 就 座 方 案 就 不 允 許 這 些 頂 點 之間 繼 續(xù) 相 鄰 ， 只 能 從 圖 中 刪 去 這 些 邊 。圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 假 定 第 三 次 就 座 方 案 是（ 1， 4， 7， 3， 6， 2， 5， 1） ， 那 么 第 四次 就 座 方 案 就 不 允 許 這 些 頂 點 之 間 繼 續(xù) 相 鄰 ，只 能 從 圖 中 刪 去 這 些 邊 ， 只 留 下 7點 孤 立 點 ，所 以 該 問 題 只 有 三 個 就 座 方 案 。圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 圍 坐 問 題 假 定 第 三 次 就 座 方 案 是（ 1， 4， 7， 3， 6， 2， 5， 1） ，那 么 第 四 次 就 座 方 案 就 不 允 許 這 些頂 點 之 間 繼 續(xù) 相 鄰 ， 只 能 從 圖 中 刪去 這 些 邊 ， 只 留 下 7點 孤 立 點 ， 所 以該 問 題 只 有 三 個 就 座 方 案 。圍 坐 問 題 哈 密 頓 （ Hamilton） 回 路 是 十 九世 紀 英 國 數 學 家 哈 密 頓 提 出 ， 給 出 一個 正 12面 體 圖 形 ， 共 有 20個 頂 點 表 示20個 城 市 ， 要 求 從 某 個 城 市 出 發(fā) 沿 著棱 線 尋 找 一 條 經 過 每 個 城 市 一 次 而 且僅 一 次 ， 最 后 回 到 原 處 的 周 游 世 界 線路 （ 并 不 要 求 經 過 每 條 邊 ） 。哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 哈 密 頓 回 路 引 言 瑞 士 數 學 家 Euler 在 1736年 發(fā) 表 的 一 篇 題 為“ 依 據 幾 何 位 置 的 解 題 方 法 ” 的 論 文 ， 有 效 的 解決 了 哥 尼 斯 堡 七 橋 問 題 ， 是 有 記 載 的 第 一 篇 圖 論論 文 ， Euler被 認 為 是 圖 論 的 創(chuàng) 始 人 。 圖 論 的 第 一 本 專 著 是 匈 牙 利 的 O Konig寫 的 “ 有限 圖 與 無 限 圖 的 理 論 ” ， 發(fā) 表 于 1936。 從 1736到 1936， 前 后 200年 ， 總 的 來 講 這 一 時期 圖 論 發(fā) 展 緩 慢 。 直 到 20世 紀 中 葉 ， 電 子 計 算 機 的 發(fā) 展 和 零 散 數 學問 題 具 有 越 來 越 重 要 的 地 位 ， 使 得 圖 論 得 以 迅 速發(fā) 展 第 十 一 章 圖 與 網 絡 分 析11.1 引 言11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 圖 論 是 專 門 研 究 圖 的 理 論 的 一 門數 學 分 支 ， 主 要 研 究 點 和 線 之 間的 幾 何 關 系 11.2 圖 與 網 絡 的 基 本 概 念定 義 ：圖 是 由 點 集 V=（ vi ） 和 V 中 元 素 的 無 序 對 的 一 個 集合 E=（ ek ） 所 構 成 的 二 元 組 ， 記 為 G=（ V， E） ，其 中 ： V= （ v1， v2， . vm） 是 m個 頂 點 集 合 ； E= （ e1， e2， . en） 是 n條 邊 集 合 。 當 V， E為 有 限 集 合 時 ， G稱 為 有 限 圖 ， 否 則 稱 為無 限 圖 ， 本 章 只 討 論 有 限 圖 。 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念說 明 ：（ 1） V非 空 ， 即 沒 有 頂 點 的 圖 不 討 論 ；（ 2） E無 非 空 條 件 ， 即 允 許 沒 有 邊 ；（ 3） E是 一 個 不 與 V 中 頂 點 相 交 的 邊 集 合 ； （ 指 點 只 在 邊 的 端 點 處 相 交 ）（ 4） 任 一 條 邊 必 須 與 一 對 頂 點 關 聯 ， 反 之 不 然 。 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念定 義對 任 一 條 邊 （ vi， vj） 屬 于 E，如 果 邊 （ vi， vj） 的 端 點 無 序 ， 則 它 是 無 向 邊 ， 此時 圖 為 無 向 圖 。如 果 如 果 邊 （ vi， vj） 的 端 點 有 序 ， 則 它 表 示 以 vi為 始 點 ， v j為 終 點 的 有 向 邊 （ 或 稱 為 弧 ） ， 此 時圖 為 有 向 圖 。 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念定 義 （ 鏈 ）如 果 圖 中 的 某 些 點 、 邊 可 以 排 列 成 點 和 邊的 交 錯 序 列 ， 則 稱 此 為 一 條 鏈 。定 義 （ 圈 ）如 一 條 鏈 中 起 點 和 終 點 重 合 ， 則 稱 此 為 一條 圈 。 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念定 義 （ 鏈 ）如 果 圖 中 的 某 些 點 、 邊 可 以 排 列 成 點 和 邊的 交 錯 序 列 ， 則 稱 此 為 一 條 鏈 。定 義 （ 圈 ）如 一 條 鏈 中 起 點 和 終 點 重 合 ， 則 稱 此 為 一條 圈 。 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念定 義 （ 鏈 ）如 果 圖 中 的 某 些 點 、 邊 可 以 排 列 成 點 和 邊的 交 錯 序 列 ， 則 稱 此 為 一 條 鏈 。定 義 （ 圈 ）如 一 條 鏈 中 起 點 和 終 點 重 合 ， 則 稱 此 為 一條 圈 。 11.2 圖 與 網 絡 的 基 本 概 念 圖 的 矩 陣 表 示 一 個 圖 非 常 直 觀 ， 但 是 不 容 易 計 算 ，特 別 不 容 易 在 計 算 機 上 進 行 計 算 ， 一 個 有效 的 解 決 辦 法 是 將 圖 表 示 成 矩 陣 形 式 ， 通常 采 用 的 矩 陣 是 鄰 接 矩 陣 、 邊 長 鄰 接 矩 陣 、弧 長 矩 陣 和 關 聯 矩 陣 。 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念 11.2 圖 與 網 絡 的 基 本 概 念賦 權 圖 或 網 絡在 圖 的 各 邊 上 一 個 數 量 指 標 （ cij） ， 具 體 表示 這 條 邊 的 權 （ 距 離 ， 單 價 ， 通 過 能 力 等 ） 。無 向 網 絡 ； 有 向 網 絡 ； 混 合 網 絡 ；邊 權 網 絡 ； 點 權 網 絡 。 第 十 一 章 圖 與 網 絡 分 析11.1 引 言11.2 圖 與 網 絡 的 基 本 概 念11.3 最 短 路 問 題 11.3 最 短 路 問 題對 一 個 賦 權 的 有 向 圖 D ;指 定 的 兩 個 點 Vs 和 Vt ；找 到 一 條 從 Vs 到 Vt 的 路 ， 使 得 這 條 路 上 所 有弧 的 權 數 的 總 和 最 小 ；這 條 路 被 稱 之 為 從 Vs到 Vt的 最 短 路 。這 條 路 上 所 有 弧 的 權 數 總 和 被 稱 為 從 Vs到 Vt的距 離 。 11.3 最 短 路 問 題一 、 求 解 最 短 路 的 Dijkstra算 法 (迪 科 斯 徹 ， 雙 標 號 法 ） 對 圖 中 的 點 Vj 賦 予 兩 個 標 號 （ lj, kj） , 第 一 個 標 號 lj 表 示 從 起 點 Vs 到 Vj 的 最 短 路 的 長 度 ， 第 二 個 標 號 kj 表 示 在 Vs 到 Vj 的 最 短 路 上 Vj 前 面 一 個鄰 點 的 下 標 。例 如 ： V 6（ 8,4) 表 示 ， 從 起 點 V 到 V 的 最 短 路 的 長 度 為 在 這 條 最 短 路 上 V 的 前 一 個 鄰 點 為 V 。 11.3 最 短 路 問 題步 驟 ：1. 給 出 點 V1 以 標 號 (0， s)2. 找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J,以 及 弧 的 集 合 3. 如 果 上 述 弧 的 集 合 是 空 集 ， 則 計 算 結 束 。 如 果 Vt 已 標 號 （ lt,kt） ， 則 Vs 到 Vt 的 距 離 為 lt 。 如 果 V t 未 標 號 ， 則 可 以 斷 言 不 存 在 從 Vs到 Vt的 有 向 路 。 如 果 上 述 的 弧 的 集 合 不 是 空 集 ， 則 轉 下 一 步 。4. 對 上 述 弧 的 集 合 中 的 每 一 條 弧 ， 計 算 sij=li+cij 。 在 所 有 的 sij中 ， 找 到 其 值 為 最 小 的 弧 。 不 妨 設 此 弧 為（ Vc,Vd） ， 則 給 此 弧 的 終 點 以 雙 標 號 （ scd,c） ,返 回 步 驟 2。( , ) | , i j i jv v v I v J 11.3 最 短 路 問 題例 求 下 圖 中 v1 到 v6 的 最 短 路 v23 5 2 7 53 1512v1 v6v 5v3 v4 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4 .給 出 點 V1 以 標 號 (0， s) (0， s) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s) .找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J， 以 及 弧 的 集 合( , ) | , i j i jv v v I v J 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s) .找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1J V2, V3, V4, V5, V6 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s) .找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1J V2, V3, V4, V5, V6 弧 的 集 合 (V1 , V2), (V1 , V3), (V1 , V4)( , ) | , i j i jv v v I v J 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)2.對 每 一 條 弧 ， 計 算 sij=li+cij 。 找 到 其 值 為 最 小 的 弧 , 給 此 弧 的 終 點 以 雙 標 號 s12=l1+c12 =0 + 3 =3 s13=l1+c13 =0 + 2 =2 s14=l1+c14 =0 + 5 =5 MIN (s12 , s13 , s14) = s13 =2 (2， 1) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)3.找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V3 J V2, V4, V5, V6 (2， 1) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)3.找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V3 J V2, V4, V5, V6 弧 的 集 合 (V1 , V2), (V1 , V4), (V3 , V4)( , ) | , i j i jv v v I v J (2， 1) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)3.對 每 一 條 弧 ， 計 算 sij=li+cij 。 找 到 其 值 為 最 小 的 弧 , 給 此 弧 的 終 點 以 雙 標 號 s12=l1+c12 =0 + 3 =3 s14=l1+c14 =0 + 5 =5 s34=l3+c34 =2 + 1 =3 MIN (s12 , s14 , s34) = s12 = s34 = 3 (2， 1)(3， 1) (3， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)4.找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V2, V3, V4 J V5, V6 (2， 1)(3， 1) (3， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)4.找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V2, V3, V4 J V5, V6弧 的 集 合 (V2 , V6), (V4 , V6)( , ) | , i j i jv v v I v J (2， 1)(3， 1) (3， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)4.對 每 一 條 弧 ， 計 算 sij=li+cij 。 找 到 其 值 為 最 小 的 弧 , 給 此 弧 的 終 點 以 雙 標 號 s26=l2+c26 =3 + 7 =10 s46=l4+c46 =3 + 5 =8MIN (s26 , s46) = s46 = 8 (2， 1)(3， 1) (3， 3) (8， 4) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s)5.找 出 已 標 號 點 的 集 合 I， 沒 標 號 的 點 的 集 合 J, 以 及 弧 的 集 合( , ) | , i j i jv v v I v J I V1 , V2, V3, V4 , V6 J V6 (2， 1)(3， 1) (3， 3)上 述 弧 的 集 合 是 空 集 ， 計 算 結 束 。 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 v23 5 2 7 53 1512v1 v6v 5v3 v4(0， s) (2， 1)(3， 1)(3， 3) (8， 4)由 于 V 已 標 號 （ , ）則 V 到 V 的 距 離 為 。最 短 路 徑 為 (由 倒 推 得 到 )V V V V 11.3 最 短 路 問 題 例 電 信 公 司 準 備 在 甲 、 乙 兩 地 沿 路 架 設 一 條光 纜 線 ， 問 如 何 架 設 使 其 光 纜 線 路 最 短 ？ 下 圖 給 出 了 甲 乙 兩 地 間 的 交 通 圖 。 權 數 表 示 兩 地 間 公 路 的 長 度 （ 單 位 ： 公 里 ） 。 V 1 （ 甲 地 ） 15 17 62444 310 6 5V2 V7 （ 乙 地 ）V3 V4 V5 V6 11.3 最 短 路 問 題 這 是 一 個 求 無 向 圖 的 最 短 路 的 問 題 。 可 以 把 無 向 圖 的 每 一 邊 （ vi,vj） 都 用 方 向 相 反 的 兩 條弧 （ vi,vj） 和 （ vj,vi） 代 替 ， 就 化 為 有 向 圖 ， 也 可 直 接 在 無 向 圖 中 用 Dijkstra算 法 來 求 解 。 只 要 在 算 法 中 把 從 已 標 號 的 點 到 未 標 號 點 弧 的 集 合 改成 已 標 號 點 到 未 標 號 點 邊 的 集 合 即 可 。 11.3 最 短 路 問 題例 求 下 圖 中 v1 到 v 的 最 短 路 V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 .給 出 點 V1 以 標 號 (0， s)(0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7 11.3 最 短 路 問 題解 采 用 Dijkstra算 法2. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V1 , V2), (V1 , V3) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7 11.3 最 短 路 問 題解 采 用 Dijkstra算 法s 12=l1+c12 =0 + 15 =15s13=l1+c13 =0 + 10 =10MIN (s12 , s13) = s13 =102. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V1 , V2), (V1 , V3) (0， s) V1 15 17 6244310 6 5V2V3 V4 V5 V6V7(10， 1) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法3. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V1 , V2), (V3 , V2) , (V3 , V5) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法3. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V1 , V2), (V3 , V2) , (V3 , V5) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1) s12=l1+c12 =0 + 15 =15 s32=l3+c32 =10 + 3 =13 s35=l3+c35 =10 + 4 =14MIN (s12 , s32 , s35) = s32 =13 (13， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法4. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V3 , V5) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法 s 24=l2+c24 =13 + 6 =19 s27=l2+c27 =13 + 17 =30 s35=l3+c35 =10 + 4 =14MIN (s24 , s27 , s35) = s35 =144. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V3 , V5) (0， s) V1 15 17 6244310 6 5V2V3 V4 V5 V6V7(10， 1)(13， 3) (14， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法5. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V5 , V4) , (V5 , V6) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法5. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V5 , V4) , (V5 , V6) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3) s24=l2+c24 =13 + 6 =19 s27=l2+c27 =13 + 17 =30 s54=l5+c54 =14 + 4 =18 s56=l5+c56 =14 + 2 =16MIN (s24 , s27 , s54 , s56) = s56 =16 (16， 5) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法6. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V5 , V4) , (V6 , V7) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3)(16， 5) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法6. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V2 , V4), (V2 , V7) , (V5 , V4) , (V6 , V7) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3)(16， 5) s24=l2+c24 =13 + 6 =19 s27=l2+c27 =13 + 17 =30 s54=l5+c54 =14 + 4 =18 s67=l6+c67 =16 + 6 =22MIN (s24 , s27 , s54 , s67) = s54 =18 (18， 5) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法7. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V2 , V7), (V4 , V7) , (V6 , V7) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 5)(16， 5)(18， 5) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法7. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合 (V2 , V7), (V4 , V7) , (V6 , V7) (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 5)(16， 5)(18， 5) s27=l2+c27 =13 + 17 =30 s47=l4+c47 =18 + 5 =23 s67=l6+c67 =16 + 6 =22MIN (s27 , s47 , s67) = s67 =22 (22， 6) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法8. 已 標 號 點 至 沒 標 號 的點 的 邊 的 集 合為 空 ， 計 算 結 束 (0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 5)(16， 5)(18， 5) (22， 6) 11.3 最 短 路 問 題解 采 用 Dijkstra算 法(0， s) V1 15 17 6244310 6 5V2V 3 V4 V5 V6V7(10， 1)(13， 3) (14， 3)(16， 5)(18， 5) (22， 6)由 于 V 7 已 標 號 （ 22,6）則 V 到 V 的 距 離 為 22。最 短 路 徑 為 V V3 V5 V6 V7 11.3 最 短 路 問 題習 題 采 用 Dijkstra算 法 求 V 到 V8 的 最 短 路4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5)(14， 5) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5)(14， 5) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5)(14， 5) (15， 7) 11.3 最 短 路 問 題4 95 41676 544 7 5 V1 V8 V2 V4 V6 V 3 V5 V7(0， s) (4， 1)(6， 1) (8， 2)(9， 2) (13， 5)(14， 5) (15， 7) 由 于 V8 已 標 號 （ 15,7）則 V 到 V8的 距 離 為 15。最 短 路 徑 為 V V2 V5 V7 V8 11.3 最 短 路 問 題6 V1 V8 V2 V 5 V7(0， s) (4， 1) (8， 2) (14， 5) (15， 7) 由 于 V8 已 標 號 （ 15,7）則 V 到 V8的 距 離 為 15。最 短 路 徑 為 V V2 V5 V7 V8 11.3 最 短 路 問 題例 某 公 司 使 用 一 臺 設 備 ， 在 每 年 年 初 ， 公 司 就 要決 定 是 購 買 新 的 設 備 還 是 繼 續(xù) 使 用 舊 設 備 。 如 果 購 置 新 設 備 ， 就 要 支 付 一 定 的 購 置 費 ， 當然 新 設 備 的 維 修 費 用 就 低 。 如 果 繼 續(xù) 使 用 舊 設 備 ， 可 以 省 去 購 置 費 ， 但 維修 費 用 就 高 了 。 請 設 計 一 個 五 年 之 內 的 更 新 設 備 的 計 劃 ， 使 得五 年 內 購 置 費 用 和 維 修 費 用 總 的 支 付 費 用 最 小 。 11.3 最 短 路 問 題設 備 每 年 年 初 的 價 格 表設 備 維 修 費 如 下 表年 份 1 2 3 4 5年 初 價 格 11 11 12 12 13使 用 年 數 0-1 1-2 2-3 3-4 4-5每 年 維 修費 用 5 6 8 11 18 年 份 1 2 3 4 5年 初 價 格 11 11 12 12 13使 用 年 數 0-1 1-2 2-3 3-4 4-5每 年 維 修費 用 5 6 8 11 181 2 3 4 5 6第 1年 購 入 新 設 備 16 22 30 41 59第 2年 購 入 新 設 備 16 22 30 41第 3年 購 入 新 設 備 17 23 31 第 4年 購 入 新 設 備 17 23第 5年 購 入 新 設 備 18第 6年 購 入 新 設 備 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v6（ v1,v4） 表 示 ， 第 1年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 4年 年 初 。（ v4,v5） 表 示 ， 第 4年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 5年 年 初（ v5,v6） 表 示 ， 第 5年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 6年 年 初30 17 18 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1)(22， 1) (30， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) (53， 3)(53， 4) 11.3 最 短 路 問 題例 3的 解 ： 用 vi表 示 “ 第 i年 年 初 購 進 一 臺 新 設 備 ” , 弧 （ vi,vj） 表 示 第 i年 年 初 購 進 的 設 備 一 直 使 用 到 第 j年 年 初 。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) (53， 3)(53， 4) 11.3 最 短 路 問 題其 最 短 路 有 兩 條 : V V3 V6 ; V V4 V6 .即 第 1年 年 初 購 進 新 設 備 使 用 到 第 3年 年 初 ， 第 3年 年 初 購 進 新 設 備 使用 到 第 5年 年 底 ； 或 第 1年 年 初 購 進 新 設 備 使 用 到 第 4年 年 初 ， 第 4年 年 初 購 進 新 設 備 使 用 到 第 5年 年 底 。 費 用 均 為 53。v 1 v2 v3 v4 v5 v616 22 30 41 5916 22 30 41 3123 17 1817 23(0， s) (16， 1) (22， 1)(30， 1) (41， 1) (53， 3)(53， 4) 11.3 最 短 路 問 題其 最 短 路 有 兩 條 : V V3 V6 ; V V4 V6 .即 第 1年 年 初 購 進 新 設 備 使 用 到 第 3年 年 初 ， 第 3年 年 初 購 進 新 設 備 使用 到 第 5年 年 底 ； 或 第 1年 年 初 購 進 新 設 備 使 用 到 第 4年 年 初 ， 第 4年 年 初 購 進 新 設 備 使 用 到 第 5年 年 底 。 費 用 均 為 53。v 1 v2 v3 v4 v5 v631 1822 (53， 3)(22， 1) 11.3 最 短 路 問 題其 最 短 路 有 兩 條 : V V3 V6 ; V V4 V6 .即 第 1年 年 初 購 進 新 設 備 使 用 到 第 3年 年 初 ， 第 3年 年 初 購 進 新 設 備 使用 到 第 5年 年 底 ； 或 第 1年 年 初 購 進 新 設 備 使 用 到 第 4年 年 初 ， 第 4年 年 初 購 進 新 設 備 使 用 到 第 5年 年 底 。 費 用 均 為 53。v 1 v2 v3 v4 v5 v630 23 (53， 4)(30， 1) 11.3 最 短 路 問 題第 1年 第 2年 第 3年 第 4年 第 5年購 買 費 11 12 13 14 14機 器 役 齡 0 1 1 2 2 3 3 4 4 5維 修 費 5 6 8 11 18 殘 值 4 3 2 1 0習 題 ： 工 廠 使 用 一 臺 設 備 ， 每 年 年 初 作 出 決 定 ， 如 果繼 續(xù) 使 用 舊 的 ， 要 支 付 維 修 費 ， 如 果 購 買 新 的 支 付 購買 費 。 試 制 定 五 年 更 新 計 劃 11.3 最 短 路 問 題1 2 3 4 5 6第 1年 購 入 新 設 備 12 19 28 40 59第 2年 購 入 新 設 備 13 20 29 41第 3年 購 入 新 設 備 14 21 30第 4年 購 入 新 設 備 15 22 第 5年 購 入 新 設 備 15第 6年 購 入 新 設 備 第 1年 第 2年 第 3年 第 4年 第 5年購 買 費 11 12 13 14 14機 器 役 齡 0 1 1 2 2 3 3 4 4 5維 修 費 5 6 8 11 18殘 值 4 3 2 1 0 v1 v2 v3 v4 v5 v61219 28 40 59表 示 ， 第 1年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 2-6年 年 初 的 費 用 。 v1 v2 v3 v4 v5 v61219 28 40 5920 29 41表 示 ， 第 2年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 3-6年 年 初 的 費 用 。13 v1 v2 v3 v4 v5 v61219 28 40 5920 29 41表 示 ， 第 3年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 4-6年 年 初 的 費 用 。14 21 3013 v1 v2 v3 v4 v5 v61219 28 40 592013 29 41表 示 ， 第 4年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 5-6年 年 初 的 費 用 。14 21 3015 22 v1 v2 v3 v4 v5 v61219 28 40 592013 29 41表 示 ， 第 5年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 6年 年 初 的 費 用 。14 21 3015 2215 v1 v2 v3 v4 v5 v61219 28 40 592013 29 4114 21 3015 2215(0， s) v1 v2 v3 v4 v5 v61219 28 40 592013 29 4114 21 3015 2215(0， s) (12， 2) v1 v2 v3 v4 v5 v61219 28 40 592013 29 4114 21 3015 2215(0， s) (12， 2) (19， 3) v1 v2 v3 v4 v5 v61219 28 40 592013 29 4114 21 3015 2215(0， s) (12， 2) (19， 3) (49， 3) v1 v2 v3 v4 v5 v61219 28 40 592013 29 41表 示 ， 第 2年 年 初 購 進 一 臺 新 設 備 ， 使 用 到 第 3-6年 年 初 的 費 用 。14 21 3015 2215 第 十 一 章 圖 與 網 絡 分 析11.1 引 言11.2 圖 與 網 絡 的 基 本 概 念11.3 最 短 路 問 題11.4 最 小 生 成 樹 問 題 11.4 最 小 生 成 樹 問 題 樹 是 圖 論 中 的 重 要 概 念 ， 所 謂 樹 就 是 一 個 無 圈 的 連 通 圖 。v1v2 v3 v 4v5v6 v7v8 v9 v1v2 v3 v5v8v7v6v4 v1v2v3 v4v5v7 v6 v8 v9(a) (b) (c) 11.4 最 小 生 成 樹 問 題 樹 是 圖 論 中 的 重 要 概 念 ， 所 謂 樹 就 是 一 個 無 圈 的 連 通 圖 。v1v2 v3 v 4v5v6 v7v8 v9 v1v2 v3 v5v8v7v6v4 v1v2v3 v4v5v7 v6 v8 v9(a) (b) (c)無圈 連通 11.4 最 小 生 成 樹 問 題 無 向 圖 G=(V,E)， 保 留 G的 所 有 點 ， 而 刪 掉 部 分 G的 邊 或 者 保 留 部 分 G的 邊 ， 所 獲 得 的 圖 G， 稱 之 為 G的 生 成 子 圖 ; 11.4 最 小 生 成 樹 問 題 無 向 圖 G=(V,E)， 保 留 G的 所 有 點 ， 而 刪 掉 部 分 G的 邊 或 者 保 留 部 分 G的 邊 ， 所 獲 得 的 圖