《图论初步》PPT课件

《《图论初步》PPT课件》由会员分享，可在线阅读，更多相关《《图论初步》PPT课件（92页珍藏版）》请在装配图网上搜索。

1、图 论 初 步 第 六 讲图 论 初 步 6.1 引 言 图 论 是 运 筹 学 的 一 个 经 典 和 重 要 的 分 支 ， 它 起 源于 欧 拉 （ Euler） 对 七 桥 问 题 的 抽 象 和 论 证 。 1936年 ，匈 牙 利 数 学 家 柯 尼 希 （ Knig） 出 版 了 图 论 的 第 一 部 专著 有 限 图 与 无 限 图 理 论 ， 竖 立 了 图 论 发 展 的 第 一座 里 程 碑 。 此 后 ， 图 论 进 入 发 展 与 突 破 的 快 车 道 ， 所研 究 的 问 题 涉 及 经 济 管 理 、 工 业 工 程 、 交 通 运 输 、 计算 机 科 学

2、与 信 息 技 术 、 通 讯 与 网 络 技 术 等 诸 多 领 域 。近 几 十 年 来 ， 由 于 计 算 机 技 术 和 科 学 的 飞 速 发 展 ， 大大 地 促 进 了 图 论 研 究 和 应 用 ， 图 论 的 理 论 和 方 法 已 经渗 透 到 物 理 、 化 学 、 通 讯 科 学 、 建 筑 学 、 生 物 遗 传 学 、心 理 学 、 经 济 学 、 社 会 学 等 学 科 中 。 图 论 中 所 谓 的 “ 图 ” 是 指 某 类 具 体 事 物 和这 些 事 物 之 间 的 联 系 。 如 果 我 们 用 点 表 示 这 些具 体 事 物 ， 用 连 接 两 点

3、的 线 段 （ 直 的 或 曲 的 ）表 示 两 个 事 物 的 特 定 的 联 系 ， 就 得 到 了 描 述 这个 “ 图 ” 的 几 何 形 象 。 图 论 为 任 何 一 个 包 含 了一 种 二 元 关 系 的 离 散 系 统 提 供 了 一 个 数 学 模 型 ，借 助 于 图 论 的 概 念 、 理 论 和 方 法 ， 可 以 对 该 模型 求 解 。 引 例 6.1.1 最 短 路 问 题 （ SPP shortest path problem） 一 名 货 柜 车 司 机 奉 命 在 最 短 的 时 间 内 将 一车 货 物 从 甲 地 运 往 乙 地 。 从 甲 地 到 乙

4、 地 的 公 路网 纵 横 交 错 ， 因 此 有 多 种 行 车 路 线 ， 这 名 司 机应 选 择 哪 条 线 路 呢 ？ 假 设 货 柜 车 的 运 行 速 度 是恒 定 的 ， 那 么 这 一 问 题 相 当 于 需 要 找 到 一 条 从甲 地 到 乙 地 的 最 短 路 。 引 例 6.1.2 中 国 邮 递 员 问 题 （ CPP chinese postman problem） 一 名 邮 递 员 负 责 投 递 某 个 街 区 的 邮 件 。 如何 为 他 （ 她 ） 设 计 一 条 最 短 的 投 递 路 线 （ 从 邮局 出 发 ， 经 过 投 递 区 内 每 条 街

5、道 至 少 一 次 ， 最后 返 回 邮 局 ） ？ 由 于 这 一 问 题 是 我 国 管 梅 谷 教授 1960年 首 先 提 出 的 ， 所 以 国 际 上 称 之 为 中 国邮 递 员 问 题 。 引 例 6.1.3 旅 行 商 问 题 （ TSP traveling salesman problem） 一 名 推 销 员 准 备 前 往 若 干 城 市 推 销 产 品 。如 何 为 他 （ 她 ） 设 计 一 条 最 短 的 旅 行 路 线 （ 从驻 地 出 发 ， 经 过 每 个 城 市 恰 好 一 次 ， 最 后 返 回驻 地 ） ？ 这 一 问 题 的 研 究 历 史 十 分

6、悠 久 ， 通 常称 之 为 旅 行 商 问 题 。 引 例 6.1.4 指 派 问 题 （ assignment problem） 一 家 公 司 经 理 准 备 安 排 名 员 工 去 完 成 项 任务 ， 每 人 一 项 。 由 于 各 员 工 的 特 点 不 同 ， 不 同的 员 工 去 完 成 同 一 项 任 务 时 所 获 得 的 回 报 是 不同 的 。 如 何 分 配 工 作 方 案 可 以 使 总 回 报 最 大 ？ 引 例 6.1.5 运 输 问 题 （ transportation problem） 某 种 原 材 料 有 个 产 地 ， 现 在 需 要 将 原 材 料从

7、 产 地 运 往 个 使 用 这 些 原 材 料 的 工 厂 。 假 定 个产 地 的 产 量 和 家 工 厂 的 需 要 量 已 知 ， 单 位 产 品从 任 一 产 地 到 任 一 工 厂 的 运 费 已 知 ， 那 么 如 何安 排 运 输 方 案 可 以 使 总 运 输 成 本 最 低 ？ 6.2 图 的 基 本 概 念 6.2.1 图 的 定 义 定 义 6.2.1 称 数 学 结 构 G = V(G), E(G), G 为 一 个 图 ， 其 中 V(G) = v1, v2, , vn 称 为 图 G的顶点集（ vertex set） 或 节 点 集 （ node set） ，V(

8、G) 中 的 每 一 个 元 素 vi（ i = 1, 2, , n） 称 为 该图 的 一 个顶点（ vertex） 或 节 点 （ node） ； E(G) = e1, e2, , em 称 为 图 G 的 边 集 （ edge set） ， E(G) 中 的 每 一 个 元 素 ek（ 即 V(G) 中 某 两个 元 素 vi, vj 的 无 序 对 ） 记 为 ek = (vi, vj) 或 ek = vivj = ek = vjvi（ k = 1, 2, , m） ， 被 称 为 该 图 的一 条 从 vi 到 vj 的 边 （ edge） ； G是 从 E(G) 到V(G)V(G)

9、 的 一 个 映 射 ， 它 指 定 E(G) 中 的 每 条边 与 V(G) 中 的 点 组 成 的 无 序 点 对 相 对 应 。 若 用 小 圆 点 表 示 点 集 V(G) 中 的 点 ， 连 线 表示 边 集 E(G) 中 的 边 ， 则 可 用 图 形 将 图 表 示 出 来 ，称 之 为 图 的 图 形 。 我 们 常 用 图 的 图 形 代 表 图 本身 。 例 6.2.1 设 V = v1, v2, v3, v4， E = e1, e2, e3, e4, e5， ： EVV 定 义 为(e1) = v1v2， (e2) = v2v3，(e3) = v2v3， (e4) = v

10、3v4， (e5) = v4v4，则 G = V, E 是 一 个 图 ， 其 图 形 如 图 所 示 。 图 6.2.1 例 6.2.2 设 V = v1, v2, v3, v4， E = v1v2, v1v2, v2v3， 则 G = V, E 是 一 个 图 ， 其 图 形 如图 所 示 。 图 6.2.2 定 义 6.2.2 设 e = uv 为 图 G 的 一 条 边 ， 我 们称 u， v 是 e 的端点， u 与 v 相邻， 边 e 与 点 u（ 或 v） 相关联； 称 u 是 e 的 起 点 ， v 是 e 的 终点 。 若 两 条 边 e1 与 e2 有 共 同 的 端 点

11、， 则 称 边 e1与 e2 相 邻 ； 称 有 相 同 起 点 和 终 点 的 两 条 边 为重边； 称 两 端 点 均 相 同 的 边 为环； 称 不 与 任 何 边相 关 联 的 点 为孤立点。 无 环 且 无 重 边 的 图 称 之 为简单图。 例 6.2.1 和 例 6.2.2 都 不 是 简 单 图 ， 因 为 例6.2.1 中 既 含 重 边 （ e2 与 e3） 又 含 环 （ e5） ， 而例 6.2.2 中 含 重 边 （ v1v2） 。 下 图 中 给 出 的 则 是简 单 图 。 图 6.2.3 任 意 两 点 均 相 邻 的 简 单 图 称 之 为完全图。 n 个 点

12、 的 完 全 图 记 为 Kn， 图 6.2.4 中 给 出 的分 别 是 K2， K3， K4。 图 6.2.4 如 果 图 G 的 各 条 边 都 被 赋 予 了 方 向 ， 则 称 图 G 为有向图。 如 果 图 G 的 每 条 边 e 都 附 有 一 个 实 数 w(e)，则 称 图 G 为赋权图， 实 数 w(e) 称 为 边 e 的 权 （ 值 ） 。 图 6.2.5 和 图 6.2.6 分 别 给 出 了 有 向 图 和 赋 权 图 的例 子 ； 而 图 6.2.7 则 给 出 了 有 向 赋 权 图 的 例 子 。 图 6.2.5 图 6.2.6 图 6.2.7 设 v 为 图

13、 G 的 点 ， G 中 与 v 相 关 联 的 边 的条 数 （ 环 计 算 两 次 ） 称 为 点 v 的 度 ， 记 为 dG(v)，简 记 为 d(v)。 例 如 ， 在 图 6.2.1 中 ， d(v1) = 1， d(v2) = d(v3) = d(v4) = 3； 在 图 6.2.2 中 ， d(v1) = 2， d(v2) = 3，d(v3) = 1， d(v4) = 0。 如 果 简 单 图 G 的 每 个 顶 点 都 有 相 同 的 度 数d， 则 称 G 为 d 次 正 则 图 。 完 全 图 Kn 一 定 是 n 次 正 则 图 ， 如 图 6.2.4。 定 理 6.2

14、.1 设 G 是 具 有 n 个 顶 点 m 条 边 的图 ， 则 顶 点 度 数 的 总 和 等 于 边 数 的 2 倍 ， 即 定 理 6.2.2 完 全 图 Kn 的 边 数 为m = n(n1)/2。mvdni i 2)(1 6.2.2 图 的 矩 阵 表 示 一 个 图 除 了 可 以 用 图 形 表 示 之 外 ， 还 可 用 矩 阵 来表 示 。 用 矩 阵 表 示 图 有 利 于 计 算 机 处 理 。 设 图 G = V, E， V = v1, v2, , vn， E = e1, e2, , em。 无 向 图 的关联矩阵 M(G) = (mij) 是 一 个 nm矩 阵 ，

15、其 中 不 相 关 联与若， 相 关 联与若， 0 1 ji jiij ev evm 有 向 图 的关联矩阵 M(G) = (mij) 是 一 个 nm矩 阵 ，其 中 不 相 关 联与若， 的 终 点是若， 的 起 点是若， 0 1 1 ji ji jiij ev ev evm 无 向 图 的邻接矩阵 A(G) = (aij) 是 一 个 n 阶方 阵 ， 其 中 aij 为 连 接 点 vi 与 点 vj 之 间 边 的 数 目 ；有 向 图 的邻接矩阵 A(G) = (aij) 是 一 个 n 阶 方 阵 ，其 中 aij 为 从 点 vi 与 出 发 到 点 vj 终 止 的 边 的

16、数 目 ；简单赋权有向图的邻接矩阵 A(G) = (aij) 是 一 个 n 阶 方 阵 ， 其 中 Evv ji wEvvwa ji jiij 0 若， 若， 是 它 的 权 值且若， 无 向 赋 权 图 的边权矩阵 W(G) = (wij) 是 一 个3m 方 阵 ， 其 中 w1j 为 第 j 条 边 的 起 点 的 标 号 ，w2j 为 第 j 条 边 的 终 点 的 标 号 ， w3j 为 第 j 条 边 的权 值 。 下 面 的 矩 阵 是 图 6.2.6 的 边 权 矩 阵 ： 310976518 55453542 43322111W 6.2.3 子 图 定 义 设 G = V(

17、G), E(G), G 与 H = V(H), E(H), H 为 两 个 图 。 若 V(H) V(G)， E(H) E(G)， 且 H 是 G 在 E(H) 上 的 限 制 ， 则 称 H 是 G 的子图。 若 H 是 G 的 子 图 ， 且 V(H) = V(G)， 则 称 H 是 G 的生成子图。 图 6.2.8 中 ， H1 与 H2 均 为 G 的 子 图 ， 其 中 H2 是 G 的 生 成 子 图 。 图 6.2.8 6.3 最 短 路 问 题 及 其 算 法 6.3.1 相 关 的 概 念 定 义 6.3.1 设 图 G 不 是 赋 权 图 。 由 图 G 中点 与 边 交

18、替 组 成 的 序 列 = v1e1v2e2 vkekvk+1，若 满 足 ei 的 端 点 为 vi 与 vi 1， i = 1, 2, , k， 则称 为 一 条 从 起 点 v1 到 终 点 vk+1 的 长 为 k 的通路。 边 不 重 复 的 通 路 称 为简单通路； 除 起 点 与终 点 可 以 相 同 外 ， 任 意 两 点 都 不 同 的 通 路 ， 称为基本通路， 基 本 通 路 简 称 为路。 显 然 ， 基 本通 路 必 为 简 单 通 路 。 称 起 点 与 终 点 相 同 的 通 路 为回路； 边 不 重复 的 回 路 称 为简单回路； 起 点 与 终 点 相 同 的

19、 长为 正 的 基 本 通 路 称 为基本回路， 也 称 为圈。 如 不 引 起 混 淆 （ 如 在 简 单 图 中 ） ， 通 路 与回 路 均 可 用 点 序 列 来 表 达 。 例 6.3.1 在 图 6.3.1 中 ， 取1 = v1v2v3， 2 = v1v2v3v4v2， 3 = v1v2v3v2v3v4，则 1， 2， 3 分 别 是 长 为 2， 4， 5 的 通 路 。 其 中 1 与 2 为 简 单 通 路 ， 1 为 基 本 通 路 。 又 取 C1 = v1v2v3v4v2v5v1， C2 = v1v2v5v1，则 C1 是 长 为 6 的 简 单 回 路 ， C2 是

20、 长 为 3 的 圈 。 图 6.3.1 定 义 6.3.2 任 意 两 点 之 间 均 存 在 通 路 的 图 称为连通图， 否 则 称 为 非 连 通 图 。 非 连 通 图 中 的连 通 子 图 ， 称 为连通分支。 图 6.3.1 所 示 的 图 为 连 通 图 ， 而 图 6.3.2 所示 的 图 为 非 连 通 图 ， 它 含 有 两 个 连 通 分 支 。 图 6.3.1 图 6.3.2 定 义 6.3.3 设 图 G 是 赋 权 图 ， 为 G 中 的一 条 路 ， 则 称 的 各 边 权 之 和 为 路 的长度。对 于 G 的 两 个 顶 点 u 和 v， 从 u 到 v 的

21、 路 一 般不 只 一 条 ， 其 中 最 短 的 一 条 称 为 从 u 到 v 的最短路； 最 短 路 的 长 称 为 从 u 到 v 的距离， 记 为d(u, v)。 6.3.2 固 定 起 点 到 其 余 各 点 的 最 短 路 算 法 寻 求 从 一 固 定 起 点 u0 到 其 余 各 点 的 最 短 路 的最 有 效 算 法 之 一 是 Dijkstra（ 迪 克 斯 特 拉 ） 算 法 ，1959 年 由 Dijkstra 提 出 。 这 个 算 法 是 一 种 迭 代 算 法 ，它 依 据 的 是 一 个 重 要 而 明 显 的 性 质 ：最短路是一条路，最短路上的任一子段也

22、是最短路。 Dijkstra 算 法 的 基 本 思 想 是 ： 按 距 u0 从 近 到 远为 顺 序 ， 依 次 求 得 u0 到 图 G 的 各 顶 点 的 最 短 路 和距 离 ， 直 至 顶 点 v0（ 或 直 至 图 G 的 所 有 顶 点 ） 。 Dijkstra 算法问 题 ： 设 简 单 赋 权 图 G = V, E 有 n 个 顶 点 ，求 G 中 u0 点 到 其 它 各 点 的 距 离 及 最 短 路 。为 避 免 重 复 并 保 留 每 一 步 的 计 算 信 息 ， 对 vV，定 义 两 个 标 号 ： l(v)顶 点 v 的 标 号 ， 表 示 从 顶 点 u0

23、到 v 的 一 条 路 的 权 值 ； z(v)顶 点 v 的 父 节 点 标 号 ， 用 以 确 定 最 短 路 的 路 线 。 第 一 步 赋 初 值 ： 令 l(u0) = 0， 对 所 有 vV u0，令 l(v) = ， z(v) = u0； S0 = u0， i = 0。第 二 步 若 i = n 1， 停 止 ； 否 则 令 = V Si，进 行 下 一 步 。第 三 步 更 新 标 号 ： 对 每 个 v ， 令如 果 l(v) l(ui) + w(uiv)， 则 z(v) = ui， 否 则 z(v) 不 变 。 iSiS ),()( ),(min)( vuwulvlvl i

24、iSu ii 第 四 步 计 算 ， 并 用 ui 1 记 达 到 最 小值 的 顶 点 ， 置 Si 1 = Siui 1， i = i 1， 转 第二 步 。 算 法 终 止 后 ， u0 到 v 的 距 离 由 l(v) 的 终 值给 出 ， 从 v 的 父 节 点 标 号 z(v) 追 溯 到 u0， 就 得到 u0 到 v 的 最 短 路 的 路 线 。 )(min vliSv 例 6.3.2 求 图 6.3.3 所 示 的 图 G 中 v1 到 其余 各 顶 点 的 最 短 路 及 其 距 离 。图 6.3.3 解 ： (1) 初 始 标 号 。 i = 0。 S0 = v1， v

25、1 = u0， 参 见 图 6.3.4(a)。图 6.3.4(a) (2) 用 u0 = v1 对 各 顶 点 的 标 号 进 行 更 新 。 i = 1。 = v2, v3, v4, v5, v6， v ， 由 算 法 有 ： l(v2) = min, 0+7 = 7， l(v3) = min, 0+4 = 4， l(v4) = min, 0+ = ， l(v5) = min, 0+ = ， l(v6) = min, 0+2 = 2。 由 于 v2， v3， v6 的 标 号 被 v1 更 新 ， 故 这 三 个 顶 点的 父 节 点 为 v1， 即 z(v2) = z(v3) = z(v6

26、) = v1， 参 见 图 6.3.4(b)， 数 字 边 方 框 中 的 符 号 表 示 父 节 点 。 又 由 于 = l(v 6) = 2， 故 u1 = v6， S1 = v1, v6。参 见 图 6.3.4(c)。 )(min0 vlSv0S 0S 图 6.3.4(b) 图 6.3.4(c) (3) 用 u1 = v6 对 各 顶 点 的 标 号 进 行 更 新 。 i = 2。 = v2, v3, v4, v5， v ， 由 算 法 有 ： l(v2) = min7, 2+ = 7， l(v3) = min4, 2+1 = 3， l(v4) = min, 2+5 = 7， l(v5

27、) = min, 2+5 = 7。 在 此 次 迭 代 中 ， v2 的 标 号 不 变 ， v3， v4， v5 的 标 号被 v6 更 新 ， 故 v2 的 父 节 点 不 变 ， v3， v4， v5 的 父 节 点为 v6， 即 z(v2) = v1， z(v3) = z(v4) = z(v5) = v6。 参 见 图6.3.4(d)。 又 由 于 = l(v 3) = 3， 故 u2 = v3， S2 = v1, v6, v3。 参 见 图 6.3.4(e)。 )(min1 vlSv1S 1S 图 6.3.4(d) 图 6.3.4(e) (4) 用 u2 = v3 对 各 顶 点 的

28、 标 号 进 行 更 新 。 i = 3。 = v2, v4, v5， v ， 由 算 法 有 ： l(v2) = min7, 3+3 = 6， l(v4) = min7, 3+1 = 4， l(v5) = min7, 3+ = 7。 在 此 次 迭 代 中 ， v5 的 标 号 不 变 ， v2 和 v4 的 标号 被 v3 更 新 ， 故 v5 的 父 节 点 不 变 ， v2 和 v4 的 父 节点 为 v3， 即 z(v5) = v6， z(v2) = z(v4) = v3。 参 见 图6.3.4(f)。 又 由 于 = l(v4) = 4， 故 u3 = v4， S3 = v1, v

29、 6, v3, v4。 参 见 图 6.3.4(g)。 )(min2 vlSv2S 2S 图 6.3.4(f) 图 6.3.4(g) (5) 用 u3 = v4 对 各 顶 点 的 标 号 进 行 更 新 。 i = 4。 = v2, v5， v ， 由 算 法 有 ： l(v2) = min6, 4+ = 6， l(v5) = min7, 4+2 = 6。 在 此 次 迭 代 中 ， v2 的 标 号 不 变 ， v5 标 号 被v4 更 新 ， 故 v2 的 父 节 点 不 变 ， v5 的 父 节 点 为 v4，即 z(v2) = v3， z(v5) = v4。 参 见 图 6.3.4(

30、h)。 又 由 于 = l(v5) = 6， 故 u4 = v5， S4 = v1, v6, v3, v4, v5。 参 见 图 6.3.4(i)。 )(min 3 vlSv 3S 3S 图 6.3.4(h) 图 6.3.4(i) (6) 用 u4 = v5 对 各 顶 点 的 标 号 进 行 更 新 。 i = 5。 = v2， v = v2， 由 算 法 有 ： l(v2) = min6, 6+ = 6。 在 此 次 迭 代 中 ， v2 的 标 号 不 变 ， 故 v2 的 父节 点 不 变 ， 即 z(v2) = v3。 参 见 图 6.3.4(i)。 又 由 于 = l(v2) =

31、6， 故 u5 = v2， S5 = v1, v6, v3, v4, v5, v2。 参 见 图 6.3.4(j)。)(min 4 vlSv 4S 4S 图 6.3.4(h) 图 6.3.4(i)(7) 由 于 i = 5 = n 1， 停 止 。 注： 迭 代 的 终 止 条 件 也 可 使 用 Sn1 = v1, , vn， 或 者 = 。 若 寻 找 v1 到 某 点 v 的 最 短 路 的 路 由 ， 则 由 v 开 始追 溯 父 节 点 直 至 v1。 例 如 ， 寻 找 v1 到 v5 的 最 短 路 的 路 由 ， 根 据 图 6.3.4(j)，从 v5 开 始 追 溯 父 节

32、点 ： v5 的 父 节 点 为 v4， v4的 父 节 点 为 v3，v3 的 父 节 点 为 v6， v6 的 父 节 点 为 v1。 于 是 v1 到 v5 的 最 短路 为 ： v1v6v3v4v5。 再 如 ， v1 到 v2 的 最 短 路 为 ： v1v6v3v2。 若 求 v1 到 某 点 v 的 距 离 ， 则 直 接 由 l(v) 的 终 值 确 定 。 例 如 ， 根 据 图 6.3.4(j)， 由 于 l(v 5) = 6， 故 v1 到 v5的 距离 为 6。 再 如 ， 由 于 l(v2) = 6， 故 v1 到 v2 的 距 离 也 为 6。1nS 6.3.3 每

33、 对 顶 点 间 的 最 短 路 算 法 寻 求 赋 权 图 中 各 对 顶 点 之 间 最 短 路 ， 显 然可 以 调 用 Dijkstra 算 法 。 具 体 方 法 是 ： 每 次 以不 同 的 顶 点 作 为 起 点 ， 用 Dijkstra 算 法 求 出 从该 起 点 到 其 余 顶 点 的 最 短 路 径 ， 反 复 执 行 次 这样 的 操 作 ， 就 可 得 到 每 对 顶 点 之 间 的 最 短 路 。但 这 样 做 需 要 大 量 重 复 计 算 ， 效 率 不 高 。 R. W. Floyd（ 弗 洛 伊 德 ） 另 辟 蹊 径 ， 提 出 了 比 这 更 好的 算

34、法 ， 操 作 方 式 与 Dijkstra 算 法 截 然 不 同 。 Floyd 算 法 的 基 本 思 想 是 ： 从 图 的 带 权 邻 接矩 阵 A = a(i, j)nn 开 始 ， 在 A 中 用 插 入 顶 点 的方 法 依 次 构 造 出 n 个 矩 阵 D(1)、 D(2)、 、 D(n)，使 最 后 得 到 的 矩 阵 D(n) 成 为图的距离矩阵， 即矩阵 D(n) 的 i 行 j 列元素便是 i 号顶点到 j 号顶点的距离。 构 造 D(i) 的 同 时 ， 也 引 入 一 个 路 由矩 阵 P(i) 来 记 录 两 点 间 的 最 短 路 径 。 构 造 矩 阵 D

35、(k)， k = 1, 2, , n， 采 用 如 下 的递 推 公 式 ： D(0) = dij(0)nn = A： 是 带 权 邻 接 矩 阵 ， dij(0) 表 示 从 vi 到 vj 的 、 中 间 不 插 入 任 何 点 的 路 径 ，即 边 vivj 的 权 值 ； D(1) = dij(1)nn， 其 中 dij(1) = mindij(0)， di1(0) d1j(0)： dij(1) 表 示 从 vi 到 vj 的 、 中 间 最 多 只 允许 v1 作 为 插 入 点 的 路 径 中 最 短 路 的 长 度 ； D(2) = dij(2)nn， 其 中 dij(2) =

36、mindij(1)， di2(1) d2j(1)： dij(2) 表 示 从 vi 到 vj 的 、 中 间 最 多 只 允许 v1 和 v2 作 为 插 入 点 的 路 径 中 最 短 路 的 长 度 ； D(n) = dij(n)nn， 其 中 dij(n) = mindij(n1)， di, n1(n1) dn1, j(n1)： dij(n) 表 示 从 vi 到 vj 的 、 中间 最 多 只 允 许 v1, v2, , vn1 作 为 插 入 点 的 路 径中 最 短 路 的 长 度 ， 即 vi 和 vj 之 间 的 距 离 。 建 立 路 由 矩 阵 P(k)， k = 1, 2

37、, , n， 采 用 如 下 的 递推 公 式 ： P(0) = pij(0)nn： pij(0) 表 示 从 vi 到 vj 的 最 短 路 要 经过 点 vj， 即 pij(0) = j； 每 求 得 一 个 D(k) 时 ， 按 下 列 方 式 产 生 相 应 的 新 的 P(k) = pij(k)nn， 其 中即 当 vk 被 插 入 到 vi 与 vj 之 间 的 最 短 路 时 ， 被 记 录 在 P (k) 中 。 依 次 求 D(n) 时 求 得 P(n)， 可 由 P(k) 来 查 找 任 何两 点 之 间 最 短 路 的 路 由 。 否 则若, , )1( )1()1()1

38、()( kij kkjkikkijkij p dddkp Floyd 算法 问 题 ： 设 简 单 赋 权 图 G = V, E 有 n 个 顶 点 ，求 G 中 任 意 两 点 vi 和 vj 之 间 的 距 离 及 最 短 路 。 输 入 带 权 邻 接 矩 阵 A = a(i, j)nn。 第 一 步 赋 初 值 ： 对 所 有 I 和 j， d(i, j) = a(i, j)；当 a(i, j) = 时 ， path(i, j) = 0， 否 则 path(i, j) = j， k = 1。 第 二 步 更 新 d(i, j)， path(i, j)： 对 所 有 i 和 j，若 d(

39、i, k) d(k, j) d(i, j)， 则 转 第 三 步 ； 否 则 d(i, j) = d(i, k) d(k, j)， path(i, j) = path(i, k)， k = k 1， 继续 执 行 第 三 步 。 第 三 步 重 复 第 二 步 直 到 k = n 1。 在 此 ： d(i, j)： dij(k)。 path(i, j)： pij(k)； 对 应 于 dij(k) 的 路 径 上 I 的 后 继 点 ， 最终 的 取 值 为 i 到 j 的 最 短 路 径 上 i 的 后 继 点 。 例 如 ， 若则 顶 点 1 到 顶 点 3 的 最 短 路 径 为 1253

40、。 这 是 因 为 ：path(1, 3) = 2， 意 味 着 顶 点 1 的 后 继 点 为 2； 又 path(2, 3) = 5，意 味 着 顶 点 2 的 后 继 点 为 5； 同 理 ， 因 path(5, 3) = 3， 从 而 顶 点 5 的 后 继 点 为 3。 故 1253 便 是 顶 点 1 到 顶 点 3 的 最 短 路径 。 53311 54555 44324 55525 22221path 6.3.4 最 短 路 算 法 的 Matlab 实 现 根 据 Dijkstra 算 法 和 Floyd 算 法 的 步 骤 ， 可以 编 写 相 应 的 Matlab 程 序

41、 。 6.4 树 及 其 算 法 6.4.1 相 关 的 概 念 树 （ tree） 在 图 论 中 是 相 当 重 要 的 一 类 图 ，它 非 常 类 似 于 自 然 界 中 的 树 。 树 的 性 质 非 常 好 ，应 用 相 当 广 泛 。 定 义 6.4.1 无 圈 的 连 通 图 称 为树。 例 如 ， 图 6.4.1 给 出 的 G1 和 G2 是 树 ， 但 G3 和 G4 则 不 是 树 。 G1 G2 G3（ 有 圈 ） G4（ 不 连 通 ） 图 6.4.1 定 理 6.4.1 设 G 是 具 有 n 个 点 m 条 边 的 图 ，则 以 下 关 于 树 的 命 题 等

42、价 。 (1) G 是 树 ； (2) G 中 任 两 个 不 同 点 之 间 存 在 唯 一 的 路 ； (3) G 连 通 ， 删 去 任 一 条 边 均 不 连 通 ； (4) G 连 通 ， 且 n = m + 1； (5) G 无 圈 ， 且 n = m + 1； (6) G 无 圈 ， 添 加 任 一 条 边 可 得 唯 一 的 圈 。 定 义 6.4.2 若 图 G 的 生 成 子 图 H 是 树 ， 则称 H 为 G 的生成树或支撑树。 一 般 来 讲 ， 一 个 图 的 生 成 树 不 唯 一 。 例 如 ， 在图 6.4.2 中 ， (a)、 (b)、 (c) 均 是 (d

43、) 的 生 成 树 。 (c) (d) 图 6.4.2(a) (b) 定 理 6.4.2 连 通 图 的 生 成 树 一 定 存 在 。 证 明 给 定 连 通 图 G， 若 G 无 圈 ， 则 G 本 身 就是 自 己 的 生 成 树 。 若 G 有 圈 ， 则 任 取 G 中 一 个 圈C， 记 删 去 C 中 一 条 边 后 所 得 之 图 为 G。 显 然 G 中 圈 C 已 经 不 存 在 ， 但 G 仍 然 连 通 。 若 G 中 还有 圈 ， 再 重 复 以 上 过 程 ， 直 到 得 到 一 个 无 圈 的 连 通图 H。 易 知 H 是 G 的 生 成 树 。 证 毕 。 定

44、 理 6.4.2 的 证 明 方 法 也 是 求 生 成 树 的 一 种 方法 ， 称 为 “ 破 圈 法 ” 。 定 义 6.4.3 在 赋 权 图 G 中 ， 边 权 之 和 最 小 （ 大 ）的 生 成 树 称 为 G 的最小（大）生成树。 6.4.2 最 小 生 成 树 算 法 一 个 简 单 连 通 图 只 要 不 是 树 ， 其 生 成 树 就不 唯 一 ， 而 且 非 常 多 。 一 般 地 ， n 个 顶 点 地 完全 图 ， 其 不 同 地 生 成 树 个 数 为 nn2。 因 而 ， 寻求 一 个 给 定 赋 权 图 的 最 小 生 成 树 ， 一 般 是 不 能用 穷 举

45、 法 的 。 例 如 ， 30 个 顶 点 的 完 全 图 有 3028个 生 成 树 ， 3028 有 42 位 ， 即 使 用 最 现 代 的 计 算机 ， 在 我 们 的 有 生 之 年 也 是 无 法 穷 举 的 。 所 以 ，穷 举 法 求 最 小 生 成 树 是 无 效 的 算 法 ， 必 须 寻 求有 效 的 算 法 。 在 求 最 小 生 成 树 的 有 效 算 法 中 ， 最 著 名 的 两 个 是 Kruskal（ 克 罗 斯 克 尔 ） 算 法 和 Prim（ 普 瑞 姆 ） 算 法 ， 其迭 代 过 程 都 是 基 于 贪 婪 法 来 设 计 的 。 1 求 最 小 生

46、 成 树 的 Kruskal 算 法 K ruskal 算法的直观描述 假 设 T0 是 赋 权 图 G 的 最 小 生 成 树 ， T0 中 的 边 和 顶点 均 涂 成 红 色 ， 初 始 时 G 中 的 边 均 为 白 色 。 将 所 有 顶 点 涂 成 红 色 ； 在 白 色 边 中 挑 选 一 条 权 值 最 小 的 边 ， 使 其 与 红 色边不形成圈， 将 该 白 色 边 涂 红 ； 重 复 直 到 有 n1 条 红 色 边 ， 这 n1 条 红 色 边 便构 成 最 小 生 成 树 T 0 的 边 集 合 。 例 如 ， 对 于 图 6.4.3(a) 给 出 的 赋 权 图 ，

47、 按 照 上 述的 步 骤 ， 容 易 求 出 其 最 小 生 成 树 。 其 中 (b)、 (c) 分 别是 第 一 步 和 第 二 步 ， (d) 是 最 后 结 果 。(a) (b) (c) (d)图 6.4.3 K ruskal 算法的基本思想 设 T0 和 C(T0) 分 别 为 图 G 的 最 小 生 成 树 的 边 集 及其 权 值 ， 初 始 状 态 均 为 空 ， 算 法 结 束 时 T0 包 含 最 小 生成 树 的 所 有 边 ， C(T0) 表 示 最 小 生 成 树 的 权 值 。 令 VS是 一 个 不 相 交 的 节 点 的 集 合 ， 初 始 状 态 时 VS

48、= v1, v2, , vn。 算 法 的 主 要 步 骤 是 每 次 从 边 集 E 中 选出 一 条 未 处 理 的 有 最 小 权 值 的 边 (u, v) 进 行 分 析 ， 如果 u 和 v 同 属 于 VS 的 一 个 元 素 集 ， 则 将 边 (u, v) 删 除 ，如 果 u 和 v 分 属 于 VS 的 两 个 元 素 集 ， 则 将 边 (u, v) 加入 到 T0 中 ， 并 将 这 两 个 元 素 集 合 并 为 一 个 元 素 集 ， 然后 再 从 E 中 另 选 权 值 最 小 的 边 进 行 处 理 ， 直 至 找 到 一棵 最 小 生 成 树 为 止 。 K

49、ruskal 算法的步骤 第 一 步 T0， C(T0)0， VS， 将 E 中 的 边按 权 值 从 小 到 大 排 成 序 列 Q。 第 二 步 对 所 有 vV， VSv， 即 VS = v1, v2, , vn。 第 三 步 如 果 |VS| = 1， 输 出 T0 和 C(T0)， 停 止 。否 则 进 行 下 一 步 。 第 四 步 从 Q 中 取 出 权 值 最 小 的 边 (u, v)， 并 从 Q中 删 除 (u, v)。 第 五 步 如 果 u， v 在 VS 的 元 素 集 V1、 V2 中 且 V1 = V 2， 则 转 第 四 步 。 否 则 进 行 下 一 步 。

50、第 六 步 T0T0(u, v)， VV1V2， C(T0)C(T0) + w(u, v)， 转 第 三 步 。 例 6.4.1 用 Kruskal 算 法 求 图 6.4.3(a) 给 出的 赋 权 图 的 最 小 生 成 树 。 解 ： 将 图 的 边 按 照 权 值 从 小 到 大 进 行 排 列 ：边 (a, b) (c, e) (a, e) (b, c) (d, g) (a, c)权 4 5 7 9 12 15边 (d, f) (f, g) (c, d) (a, g) (e, g) (d, e)权 16 20 25 28 30 32 操 作 Kruskal 算 法 ， 迭 代 9 步

51、 完 成 最 小 生 成 树 的寻 找 。 操 作 过 程 的 各 个 步 骤 列 于 下 表 。 步骤 选 出 边 e w(e) 操 作 VS T0 C(T0)1 (a, b) 4 加 到 T0中 a, b, c, d, e, f, g (a, b) 42 (c, e) 5 加 到 T0中 a, b, c, e, d, f, g (a, b), (c, e) 93 (a, e) 7 加 到 T 0中 a, b, c, e, d, f, g (a, b), (c, e), (a, e) 164 (b, c) 9 删 除 a, b, c, e, d, f, g (a, b), (c, e), (

52、a, e) 165 (d, g) 12 加 到 T0中 a, b, c, e, d, g, f (a, b), (c, e), (a, e), (d, g) 286 (a, c) 15 删 除 a, b, c, e, d, g, f (a, b), (c, e), (a, e), (d, g) 287 (d, f) 16 加 到 T0中 a, b, c, e, d, g, f (a, b), (c, e), (a, e), (d, g), (d, f) 448 (f, g) 20 删 除 a, b, c, e, d, g, f (a, b), (c, e), (a, e), (d, g), (

53、d, f), (c, d) 449 (c, d) 25 加 到 T 0中 a, b, c, e, d, g, f (a, b), (c, e), (a, e), (d, g), (d, f), (c, d) 69 结 果 显 示 于 图 6.4.4 图 6.4.4 2 求 最 小 生 成 树 的 Prim 算 法 Prim 算法的直观描述 假 设 T0 是 赋 权 图 G 的 最 小 生 成 树 。 任 选 一个 顶 点 将 其 涂 红 ， 其 余 顶 点 为 白 点 ； 在 一 个 端点 为 红 色 ， 另 一 个 端 点 为 白 色 的 边 中 ， 找 一 条权 最 小 的 边 涂 红 ，

54、 把 该 边 的 白 端 点 也 涂 成 红 色 ；如 此 ， 每 次 将 一 条 边 和 一 个 顶 点 涂 成 红 色 ， 直到 所 有 顶 点 都 成 红 色 为 止 。 最 终 的 红 色 边 便 构成 最 小 生 成 树 T0 的 边 集 合 。 例 如 ， 对 于 图 6.4.3(a) 给 出 的 赋 权 图 ， 按 照 上 面的 描 述 ， 容 易 求 出 其 最 小 生 成 树 。 其 中 图 6.4.5(a)、 (b) 分 别 是 第 一 步 和 第 二 步 ， (c) 是 最 后 结 果 。 (a) (b) (c) 图 6.4.5 Prim 算法的基本思想 设 T0 和 C

55、(T0) 分 别 为 图 G 的 最 小 生 成 树 的边 集 及 其 权 值 ， 初 始 状 态 均 为 空 ， 算 法 结 束 时T0 包 含 最 小 生 成 树 的 所 有 边 ， C(T0) 表 示 最 小 生成 树 的 权 值 。 先 指 定 一 个 顶 点 为 初 始 访 问 点 ，记 做 v0， 将 v0 加 到 “ 通 过 点 ” 的 集 合 V 中 ， 然后 找 出 跨 接 在 “ 通 过 点 ” 集 合 V 与 “ 未 通 过 点 ”集 合 VV 之 间 权 最 小 的 边 e 作 为 “ 通 过 边 ” 加入 T0 中 ， 并 将 e 在 VV 中 的 端 点 转 到 V

56、 中 。重 复 上 述 过 程 直 至 V = V 为 止 。 K ruskal 算法的步骤 第 一 步 T0， C(T0)0， V v0。 第 二 步 对 每 一 个 点 vV V ， L(v)c(v, v0)（ 如 果 (v, v0)E， 则 c(v, v0) = ） 。 第 三 步 如 果 V = V， 输 出 T0， C(T0)， 停 止 。 否 则 进 行下 一 步 。 第 四 步 在 V V 中 找 一 点 u， 使L(u) = minL(v) | vV V ，并 将 V 中 与 u 邻 接 的 点 记 为 w， e = (w, u)。 第 五 步 T0T0e， C(T0)C(T0

57、)+C(e)， V V u。 第 六 步 对 所 有 vVV ， 如 c(v, u) L(v)， 则 L(v) c(v, u)， 否 则 L(v) 不 变 。 第 七 步 转 第 三 步 。 例 6.4.2 用 Prim 算 法 求 图 6.4.3(a) 给 出 的 赋 权 图的 最 小 生 成 树 。 解 ： 为 简 便 起 见 ， 将 操 作 Prim 算 法 的 步 骤 列 于 下表 ， 结 果 参 加 图 6.4.4。步 骤 u L(b) L(c) L(d) L(e) L(f) L(g) e V T0 C(T0)1 a 4 15 7 28 a 02 b 9 7 28 (a,b) a,

58、b (a, b) 43 e 5 32 28 (a,e) a, b, e (a, b), (a, e) 11 4 c 25 28 (c,e) a, b, e, c (a, b), (a, e), (c, e) 165 d 16 12 (c,d) a, b, e, c, d (a, b), (a, e), (c, e), (c, d) 416 g 16 (d,g) a, b, e, c, d, g (a, b), (a, e), (c, e), (c, d), (d, g) 537 f (d, f) a, b, e, c, d, g, f (a, b), (a, e), (c, e), (c, d

59、), (d, g), (d, f) 69 6.4.3 最 小 生 成 树 算 法 的 Matlab 实 现 根 据 Kruskal 算 法 和 Prim 算 法 的 步 骤 ， 许多 人 都 编 写 了 相 应 的 Matlab 程 序 。 在 此 选 用 5中 给 出 的 Matlab 程 序 。 6.4.4 关 于 最 小 生 成 树 算 法 的 注 释 最 小 生 成 树 的 Kruskal 算 法 是 1956 年 由Kruskal 提 出 的 。 随 后 在 1957 年 ， 领 导 贝 尔 实验 室 数 学 研 究 室 的 Prim 得 到 了 他 的 算 法 。 Kruskal

60、算 法 的 时 间 复 杂 性 以 O(mlog2m) 为 界 ， 当边 数 较 多 或 是 一 个 完 全 图 时 ， m (n 1)2， 则 时 间 复 杂性 近 似 于 O(n2log2n)。 而 Prim 算 法 的 时 间 复 杂 性 为O(n2)， 所 以 ， 如 果 图 的 连 通 度 较 高 （ 最 高 为 完 全 图 ） ，以 Prim 算 法 较 好 ， 如 果 图 的 连 通 度 较 低 ， 特 别 当 m O(n) 时 ， 则 Kruskal 算 法 更 合 适 。 在 实 际 应 用 中 ， 还 会 遇 到 求 一 个 赋 权 图 的 最 大 生成 树 的 问 题 。

61、 比 如 ， 某 图 的 边 权 代 表 的 是 利 润 或 效 益 ，则 最 终 的 问 题 很 可 能 就 是 求 其 最 大 生 成 树 。 事 实 上 ，从 上 面 两 个 算 法 可 以 看 出 ， 只 要 边 权 的 选 择 改 为 从 大到 小 ， 求 最 小 生 成 树 的 算 就 可 以 用 来 求 最 大 生 成 树 了 。 6.5 范 例 图 论 是 离 散 数 学 的 重 要 分 支 ， 它 能 够 为 自然 科 学 、 工 程 技 术 、 经 济 管 理 、 社 会 现 象 等 诸多 问 题 提 供 得 力 的 数 学 模 型 。 因 而 ， 许 多 实 际问 题 都

62、 可 以 转 化 为 图 论 的 问 题 加 以 解 决 。 在 此 ，仅 举 几 个 可 以 利 用 图 论 方 法 解 决 的 问 题 ， 予 以示 范 。 设备更新问题。 某 工 厂 的 某 台 机 器 可 连 续 工 作 4年 ，决 策 者 每 年 年 初 都 要 决 定 机 器 是 否 需 要 更 新 。 若 购 置 新 的 ，就 要 支 付 一 定 的 购 置 费 用 ； 若 继 续 使 用 ， 则 要 支 付 一 定 的维 修 与 运 行 费 用 ， 而 且 随 着 机 器 使 用 年 限 的 增 加 费 用 逐 年增 多 。 计 划 期 （ 4 年 ） 中 每 年 年 初 的

63、购 置 价 格 及 各 个 年 限内 维 修 与 运 行 费 用 由 下 表 给 出 ， 试 制 订 今 后 4 年 的 机 器 更新 计 划 ， 使 总 的 支 付 费 用 最 少 。 第 i年 初 1 2 3 4购 置 费 （ 万 元 ） 2.5 2.6 2.8 3.1使 用 年 限 1 2 3 4 每 年 的 维 修 与 运 行 费 （ 万 元 ） 1 1.5 2 4 又 如 果 已 知 不 同 役 龄 机 器 年 末 的 处 理 价 格如 下 表 所 示 ， 那 末 在 这 计 划 期 内 机 器 的 最 优 更新 计 划 又 会 怎 样 ？年 度 第 1年 末 第 2年 末 第 3年

64、 末 第 4年 末机 器 处 理 价 （ 万 元 ） 2.0 1.6 1.3 1.1 解 ： 关 于 第 一 问 ， 把 该 问 题 看 成 一 个 最 短 路 问 题 。设 v1 和 v5 分 别 表 示 计 划 期 的 始 点 和 终 点 （ x5 可 理 解 为第 4年 年 末 ） 。 图 中 各 边 (vi , vj) 表 示 在 第 i 年 初 购 进 的机 器 使 用 到 第 j 年 初 （ 即 第 j 1 年 底 ） ， 边 旁 的 数 字由 表 中 的 数 据 得 到 。 关 于 第 二 问 ， 类 似 于 第 一 问 ， 可 转 化 为 求 下图 中 从 v1 到 v5 的

65、最 短 路 问 题 。 按 照 最 短 路 算 法 可 得 最 短 路 v1, v2, v3, v5， 即 计 划期 内 机 器 更 新 最 优 计 划 为 第 1 年 、 第 3 年 初 各 购 进一 台 新 机 器 ， 4 年 总 的 支 付 费 用 为 6.8万 元 。 选址问题。 选 址 问 题 是 指 为 一 个 或 几 个 服务 设 施 在 一 定 区 域 内 选 定 它 的 位 置 ， 使 某 一 指标 达 到 最 优 值 。 选 址 问 题 的 数 学 模 型 依 赖 于 设施 可 能 的 区 域 和 评 判 位 置 优 劣 的 标 准 ， 有 许 多不 同 类 型 的 选 址

66、 问 题 。 比 较 简 单 的 两 类 选 址 问题 是 中 心 问 题 和 重 心 问 题 。 中 心 问 题 ： 有 些 公 共 服 务 设 施 （ 例 如 一 些 紧急 服 务 型 设 施 如 急 救 中 心 、 消 防 战 等 ） 的 选 址 ， 要求 网 络 中 最 远 的 被 服 务 点 距 离 服 务 设 施 的 距 离 尽 可能 小 。 例 如 ： 某 城 市 要 建 立 一 个 消 防 站 ， 为 该 市 所属 的 七 个 区 服 务 ， 如 下 图 所 示 。 问 应 设 在 那 个 区 ，才 能 使 它 至 最 远 区 的 路 径 最 短 。 解 ： (1) 用 Floyd 算 法 求 出 距 离 矩 阵 D = (dij)vv： 05.15.55.8647 5.10475.45.25.5 5.5403247 5.87305710 65.425025 45.247203 75.5710530D (2) 计 算 在 各 点 vi 设 立 服 务 设 施 的 最 大 服 务距 离 S(vi) ， i = 1, 2, , v有 ： S(v1) = 10， S(v2)