管理系统工程图与网络课件

管 理 系 统 工 程 图 与 网 络 1 第 十 八 章 图 与 网 络1.哥 尼 斯 堡 七 桥 问 题 德 国 古 城 哥 尼 斯 堡 普 雷 格 尔河 七桥 问 题 ： 从 任 一 桥 头 出 发 ， 依 次 走 过 每 一 座桥 ， 每 座 桥 只 走 一 次 ， 最 后 回 到 出 发 点 。 一 笔 画 问 题 管 理 系 统 工 程 图 与 网 络 2 2. 中 国 邮 递 员 问 题 邮 递 员 送 信 送 报 要 走 完 全 部 所 负 责 的街 道 ， 最 后 回 到 邮 局 ， 如 何 走 路 程 最 短 ？ 管 理 系 统 工 程 图 与 网 络 3 3.铁 路 交 通 图 管 理 系 统 工 程 图 与 网 络 4 管 理 系 统 工 程 图 与 网 络 5 第 一 节 图 的 基 本 概 念一 、 图 的 概 念定 义 图 是 由 点 与 边 组 成 的 集 合 ， 记 为G=(V， E)， 其 中 V表 示 图 G中 点 的 集 合 ， 是一 个 非 空 集 合 ， 记 为 V（ G） ， 这 些 点 称 为顶 点 ， E表 示 图 G中 边 的 集 合 ， 记 为 E（ G） 。例 18 1 图 18 4中 的 图 可 表 示 为G=（ V， E） ， 其 中 987654321 654321 e,e,e,e,e,e,e,e,eE v,v,v,v,v,vV 管 理 系 统 工 程 图 与 网 络 6 定 义 设 G=（ V， E）（ 1） 图 G中 含 顶 点 的 个 数 ， 记 为 p（ G） ， 称 为 图 G的 阶 ； 图 G中 含 边 的 条 数 ， 记 为 q（ G） ， 称 为 图 的 边 数 。（ 2） 若 e=u， v E， 则 称 u， v是 边 e的 端 点 ， 称 e为 u， v的 关 联 边 。（ 3） 若 u和 v是 同 一 条 边 相 关 联 ， 则 称 u和 v 是 相 邻 的 ， 若 边 ei、 ej有 公 共 的 端 点 ， 称 边 ei和 ej是 相 邻 的 。 管 理 系 统 工 程 图 与 网 络 7 （ 4） 若 e的 两 个 端 点 重 合 ， 则 称 e为 环 。（ 5） 若 两 点 之 间 多 于 一 条 边 ， 称 之 为 多 重 边 。（ 6） 含 多 重 边 的 图 ， 称 为 多 重 图 ， 无 环 也 无 多 重 边 的 图 ， 称 为 简 单 图 。（ 7） 以 顶 点 v为 端 点 的 边 的 条 数 ， 称 为 点 v的 次 （ 或 称 度 ） ， 记 为 d（ v） 。（ 8） 若 d（ v） =1， 则 称 v为 悬 挂 点 ， 与 悬 挂 点 相 关 联 的 边 称 为 悬 挂 边 。（ 9） 若 d（ v） =0， 则 称 v为 孤 立 点 。（ 10） 若 d（ v） =奇 数 ， 则 称 v为 奇 点 ， 若 d（ v） =偶 数 ， 则 称 v为 偶 点 。 管 理 系 统 工 程 图 与 网 络 8 定 理 1 在 图 G中 ， 所 有 顶 点 次 的 和 ， 等 于 边 数的 两 倍 。 即这 是 显 然 的 ， 因 为 在 计 算 各 点 的 次 时 ， 每 条 边都 用 过 两 次 ， 所 以 ， 所 有 顶 点 次 的 和 等 于 边 数的 两 倍 。定 理 2 在 任 一 图 中 ， 奇 点 的 个 数 必 为 偶 数 。 Vv q2)v(d 管 理 系 统 工 程 图 与 网 络 9 二 、 图 的 同 构定 义 设 是 两 个 图 ， 如 果 顶 点 集 合 V1与 V2之 间以 及 边 的 集 合 E1与 E2之 间 都 建 立 了 一 一 对 应 关系 ， 并 且 图 形 的 两 顶 点 之 间 的 边 对 应 于 另 一 图形 对 应 顶 点 的 边 ， 则 称 图 G1与 图 G2是 同 构 的 。 同 构 的 图 被 认 为 是 相 同 的 。 管 理 系 统 工 程 图 与 网 络 10 管 理 系 统 工 程 图 与 网 络 11 三 、 子 图定 义 设 ，如 果 ， 则 称 G1是 G2的 子 图 。应 当 指 出 ， 从 图 G2的 顶 点 集 合 V2中 任 选 一 些 顶 点 ，从 图 G2的 边 集 合 E2中 任 选 一 些 边 ， 不 一 定 就 能 组 成G2的 子 图 G1而 只 有 当 所 有 被 选 入 G1的 边 的 端 点 也 都被 选 入 G1时 ， G1才 是 G2的 子 图 。 并 且 ：（ 1） 若 ,则 称 G1是 G2的 一 个 部 分 图 ，例 如 图 18 6（ b） 就 是 图 18 6（ a） 的 一 个 部 分 图 。（ 2） 若 ， 则 称 G1是 G2的 真 子 图 。 例如 图 18 6（ c） 就 是 图 18 6（ a） 的 一 个 真 子 图 。 2121 EEVV ， ）， 222111 EV(G)EV(G 2121 EEVV ， 2121 EEVV ， 管 理 系 统 工 程 图 与 网 络 12 管 理 系 统 工 程 图 与 网 络 13 第 二 节 连 通 图定 义 设 是 一 个 图 ， Q为 G中 一 个 由 部 分 顶点 和 边 交 错 组 成 的 非 空 有 限 序 列其 中 则 称 Q为 从 到 的 一 条 链 ， 如 果 Q中 ， 而 且 与重 合 ， 则 称 Q为 圈 （ 或 称 闭 链 ） 。 如 果 链（ 圈 ） Q中 含 的 边 均 不 相 同 ， 则 称 Q为 简 单链 （ 圈 ） 。 如 果 链 （ 圈 ） Q中 含 的 边 与 顶 点均 不 相 同 ， 则 称 Q为 初 等 链 （ 圈 ） 。 kk iiiiii veevevQ ， 12211 ），（， 1k321rvve 1rrr iii 管 理 系 统 工 程 图 与 网 络 14 定 义 如 果 在 图 中 的 任 何 两 个 顶 点 之 间 都 至 少有 一 条 连 接 这 两 个 顶 点 的 链 ， 则 称 图 G为 连 通图 ， 否 则 ， 称 G为 非 连 通 图 。 管 理 系 统 工 程 图 与 网 络 15 管 理 系 统 工 程 图 与 网 络 16 一 笔 画 问 题欧 拉 链 ： 给 定 一 个 连 通 图 G,若 存 在 一 条 链 ， 过 每 边一 次 且 仅 一 次 ， 则 称 这 条 链 为 欧 拉 链 。欧 拉 圈 ： 若 存 在 一 个 简 单 圈 ， 过 每 边 一 次 ， 则 称 这个 圈 为 欧 拉 圈 。欧 拉 图 ： 有 欧 拉 圈 的 图 称 为 欧 拉 图 。 能 一 笔 画 的 图 一 定 是 欧 拉 圈 或 含 有 欧 拉 链 。定 理 ： 连 通 的 多 重 图 G是 欧 拉 图 的 充 要 条 件 是 G中 无奇 点 。推 论 ： 连 通 的 多 重 图 G有 欧 拉 链 的 充 要 条 件 是 G中 恰有 两 个 奇 点 。 管 理 系 统 工 程 图 与 网 络 17 管 理 系 统 工 程 图 与 网 络 18 第 三 节 树一 、 树 的 概 念 及 性 质 管 理 系 统 工 程 图 与 网 络 19 定 义 如 果 图 G是 一 个 无 圈 的 连 通 图 ， 则 称 G为树 。关 于 树 T， 具 有 下 列 性 质 ：1 在 树 T中 ， 任 意 两 个 顶 点 之 间 必 有 一 条 且 仅有 一 条 链 。2 在 树 T中 去 掉 任 意 一 条 边 ， 则 T成 为 非 连 通 图 。3 在 树 T中 不 相 邻 的 两 个 顶 点 之 间 添 上 一 条 边 ，恰 好 构 成 一 个 圈 。4 树 的 边 数 恰 等 于 树 的 顶 点 数 减 1。 管 理 系 统 工 程 图 与 网 络 20 二 、 图 的 部 分 树定 义 如 果 图 的 部 分 图 是 树 ， 其 中 ， 则 称 T为 G的 一 个 部 分 树 （ 或 生 成 树 ） 。 T中 的 边 称 为 树 枝 。 由 这 个 定 义 ， 显 然 可 以 得 到 ： 若 图 G有 部 分树 ， 则 G必 定 是 连 通 图 。 反 之 ， 若 图 G是 连 通 图 ，则 G必 有 部 分 树 。 管 理 系 统 工 程 图 与 网 络 21 管 理 系 统 工 程 图 与 网 络 22 用 丢 边 破 圈 法 ， 可 找 出 连 通 图 G的 部 分 树 。 所 谓 丢 边 破 圈 法 ， 就 是 取 图 G中 任 意 一 个圈 ， 丢 去 圈 上 任 意 一 边 ， 然 后 重 复 这 一 步 骤 ，直 到 图 中 无 圈 为 止 ， 则 剩 下 的 图 为 无 圈 的 连 通图 ， 就 是 G的 一 棵 部 分 树 。 也 可 以 用 避 圈 法 找 G的 部 分 树 。 所 谓 避 圈 法 ， 就 是 在 连 通 图 G中 任 意 取 一边 e1， 找 一 条 不 与 e1构 成 圈 的 边 e2， 然 后 再 找一 条 不 与 e1， e2构 成 圈 的 e3， 这 样 继 续 下 去 ，直 到 这 一 过 程 不 能 进 行 时 为 止 ， 这 样 得 到 的 图 ，就 是 连 通 图 G的 一 棵 部 分 树 。 管 理 系 统 工 程 图 与 网 络 23 管 理 系 统 工 程 图 与 网 络 24 三 、 最 小 部 分 树定 义 若 图 G的 每 一 条 边 （ vi， vj) 都 相 应 地 有 一 个 数wij， 则 称 这 样 的 图 G为 赋 权 图 ， wij称 为 边 （ vi， vj) 上的 权 。 一 个 连 通 图 的 部 分 树 是 不 唯 一 的 ， 其 中 使各 边 权 的 总 和 最 小 的 那 棵 部 分 树 ， 称 为 最 小 部分 树 。 )EV(T ， )EV(G ，设 有 一 个 赋 权 的 连 通 图 ， 求 G的 一 棵 部 分 树 ， 使取 得 最 小 值 。 Tvv ijji w)T(w ， 管 理 系 统 工 程 图 与 网 络 25 求 最 小 部 分 树 的 两 种 方 法 算 法 （ Kruskal算 法 ） ： 其 基 本 思 想 是 ， 每一 步 从 未 选 的 边 中 ， 选 一 条 具 有 最 小 权 的 边 ，使 与 已 选 的 边 不 构 成 圈 ， 直 到 每 一 条 边 都 选 查过 为 止 。算 法 （ 破 圈 法 ） ： 其 基 本 思 想 是 ， 从 G中 任选 一 个 圈 ， 去 掉 圈 上 权 最 大 的 边 。 然 后 在 余 下图 中 ， 重 复 上 述 过 程 ， 直 到 无 圈 为 止 。 管 理 系 统 工 程 图 与 网 络 26 例 :某 工 厂 内 联 结 六 个 车 间 的 道 路 网 如 图 所 示 ，已 知 每 条 道 路 的 长 ， 要 求 沿 道 架 设 联 结 六 个 车间 的 电 话 线 网 ， 使 电 话 线 的 总 长 最 小 。 管 理 系 统 工 程 图 与 网 络 27 第 四 节 最 短 路 问 题1 狄 克 斯 特 拉 （ Dijkstra） 算 法步 骤 如 下 ：（ 1） 对 起 点 vs进 行 标 号 。 每 个 标 号 点 的 标 号包 含 两 部 分 ， 前 者 表 示 它 的 标 号 是 从 哪 一 点 来的 ； 后 者 表 示 从 起 点 vs到 该 点 的 最 短 距 离 。 对起 点 vs， 将 Lss=0填 进 vs近 旁 的 圆 括 号 内 ， 表 示vs点 已 标 号 。（ 2） 从 vS点 出 发 ， 找 出 与 vS相 邻 的 顶 点 中 距 离最 小 的 一 个 vr， 将 Lsr=Lss+dsr的 值 填 入 vr近 旁 圆括 号 内 ， 表 示 v r已 经 标 号 。 管 理 系 统 工 程 图 与 网 络 28 （ 3） 从 已 标 号 的 顶 点 出 发 ， 找 出 与 已 标 号 点 相邻 的 所 有 未 标 号 点 。 若式 中 vs， vr为 已 标 点 ， vp为 未 标 号 点 ， 则 对 vp进行 标 号 。（ 4） 重 复 第 3步 ， 直 到 vT点 得 到 标 号 为 止 。rs rpsrspsssp dLdLminL ， ， 管 理 系 统 工 程 图 与 网 络 29 例 4 求 如 图 18 15所 示 的 网 络 图 中 v1到 v6的 最短 距 离 及 其 路 线 。 管 理 系 统 工 程 图 与 网 络 30 例 5 某 厂 使 用 一 种 设 备 ， 每 年 年 初 都 要 决 定 该设 备 是 否 需 要 更 新 。 若 购 买 新 设 备 ， 每 年 需 支付 购 置 费 用 （ 第 i年 的 购 置 费 设 为 li） ； 若 继 续使 用 旧 设 备 ， 则 要 支 付 维 修 与 运 行 费 用 （ 第 i年的 维 修 与 运 行 费 为 Ci） 。 计 划 期 （ 五 年 ） 中 每 年的 li与 如 Ci表 18 1所 示 ， 工 厂 要 制 定 今 后 五 年的 设 备 更 新 计 划 ， 问 采 取 何 种 方 案 ， 使 总 费 用最 小 。 表 18 1 管 理 系 统 工 程 图 与 网 络 31 2 矩 阵 计 算 法 例 6 网 络 图 如 图 18 15所 示 ，用 矩 阵 计 算 法 求 各 点 之 间 的 最 短 距 离 。 管 理 系 统 工 程 图 与 网 络 32 解 设 dij表 示 相 邻 两 点 vi与 vj间 的 距 离 ， 若 vi与 vj不 相 邻 时 ， 令 dij= 。 666564636261 565554535251 464544434241 353534333231 262524232221 161514131211 dddddd dddddd dddddd dddddd dddddd dddddd 043 40231 3203 3023 13204 340 管 理 系 统 工 程 图 与 网 络 33 先 考 虑 vi与 vj之 间 有 一 个 中 间 点 情 况 ， 如图 18 15中 的 最 短 距 离 为为 此 可 以 构 造 一 个 新 的 矩 阵 D(1)， 令 D(1)， 中 每个 元 素 为则 矩 阵 D(1)给 出 了 网 络 中 任 意 两 点 之 间 直 接 到 达和 经 过 一 个 中 间 点 时 的 最 短 距 离 。 4rr16r1 641654154414341324121411 ddmin ddddddddddddmin 即 ， rjir1ij ddmind ）（ 管 理 系 统 工 程 图 与 网 络 34 再 构 造 矩 阵 D(2)， 令则 D(2)给 出 网 络 中 任 意 两 点 直 接 到 达 ， 经 过 一至 三 个 中 间 点 时 的 最 短 距 离 。一 般 ， 矩 阵 给 出 网 络 中 任 意 两 点 直 接 到 达 ， 经 过 一个 ， 两 个 ， ， 到 个 中 间 点 时 比 较 得 到 的 最短 距 离 。 ）（）（）（ 1rj1ir2ij ddmind ）（）（）（ 1krj1kirkij ddmind 管 理 系 统 工 程 图 与 网 络 35 求 中 心 在 一 个 连 通 图 G中 ， 设 d(vi ,vj)为 vi至 vj的 最 短 距 离 ， 令 ：为 点 vi至 点 vj的 最 大 距 离 ,若 G中 的 一 点 v*满 足 ：则 称 点 v *为 图 G的 中 心 。 ),(max)( jiVvi vvdvd j )(min)( iVv vdvd i 管 理 系 统 工 程 图 与 网 络 36 求 中 心 村 庄 之 间 的 最 短 距 离 dij * 村庄 max v1 v2 v3 v4 v5 v6 v7 v1 10 0 5 2 7 7 6 10 v2 8 5 0 7 2 5 4 8 v3 7 2 7 0 6 5 4 8 v4 7 7 2 6 0 3 2 6 v 5 7 7 5 5 3 0 1 3 v6 6* 6 4 4 2 1 0 4 v7 10 10 8 8 6 3 4 0 管 理 系 统 工 程 图 与 网 络 37 求 重 心在 一 个 连 通 图 G中 ， 设 w(vi)为 点 vi的 权 重 ， 令表 示 将 点 vi的 物 资 运 到 点 vj的 总 运 输 量 。 若 满 足则 称 点 为 图 G的 重 心 。 ),.,2,1(),()()( 1 njvvdvwvg ni jiij )(min)( jVv vgvg jv 管 理 系 统 工 程 图 与 网 络 38 例 ： 上 例 中 ， v1， v2， v3， v4， v5， v6， v7为 七 个 村 子 ， 现 决 定 要 办 一 所 小 学 ， 已 知各 村 学 生 人 数 分 别 为 ： v130， v240， v325， v420， v550， v660, v760，问 小 学 应 建 在 那 个 村 子 ， 使 学 生 上 学 走 的 路程 最 短 。解 ： 计 算 见 表 。 小 学 应 建 在 v 6村 。 管 理 系 统 工 程 图 与 网 络 39 求 重 心 村 庄 之 间 的 最 短 距 离 dij * 村庄 人 数 wi v1 v2 v3 v4 v5 v6 v7 v1 30 0 5 2 7 7 6 10 v2 40 5 0 7 2 5 4 8 v3 25 2 7 0 6 5 4 8 v4 20 7 2 6 0 3 2 6 v 5 50 7 5 5 3 0 1 3 v6 60 6 4 4 2 1 0 4 v7 60 10 8 8 6 3 4 0 wi dij * 1700 1335 1430 1070 835 770* 1330 管 理 系 统 工 程 图 与 网 络 40 例 ： 下 图 为 一 大 型 企 业 区 域 交 通 网 络 图 。 设 点v1 v7为 某 公 司 的 7个 分 厂 ， 边 表 示 经 过 测 绘 的交 通 路 线 ， 边 旁 的 数 字 表 示 两 点 之 间 的 距 离 。现 该 企 业 欲 修 建 正 规 道 路 使 各 分 厂 互 通 ， 并 欲在 某 一 分 厂 建 一 俱 乐 部 。 问 如 何 选 择 交 通 路 线来 修 建 正 规 道 路 既 保 证 各 分 厂 畅 通 ， 又 使 道 路总 长 度 最 短 ？ 俱 乐 部 应 建 在 那 个 分 厂 才 能 使 离该 俱 乐 部 最 远 的 分 厂 的 职 工 所 走 的 路 程 最 短 ？解 :显 然 ， 第 一 个 问 题 就 是 求 最 短 树 问 题 。 第二 个 问 题 就 是 求 中 心 问 题 。 用 避 圈 法 或 破 圈 法 求 出 最 小 部 分 树 见 图 。 管 理 系 统 工 程 图 与 网 络 41 管 理 系 统 工 程 图 与 网 络 42 先 用 公 式 计 算 d(vi)， 见 下 表 ：再 用 公 式 计 算 d(v *)， 由 表 可 知 ， 应 将 俱 乐 部 建 在 分 厂 v2或v6。 ),(max)( jiVvi vvdvd j )(min)( iVv vdvd i 管 理 系 统 工 程 图 与 网 络 43 例 ： 仍 以 上 例 为 例 ， 现 准 备 在 该 地 区 建 一 个中 心 仓 库 以 贮 存 分 发 给 各 分 厂 的 原 材 料 。 已知 各 分 厂 每 月 的 原 材 料 需 求 量 见 下 图 。 问 中心 仓 库 应 建 在 那 个 分 厂 ， 能 使 每 月 总 的 运 输量 最 小 。解 ： 由 计 算 重 心 的 公 式 ： 既 可 算 得 应 把 中 心 仓 库 建 在 v 6分 厂 ， 每 月的 最 小 运 输 量 为 122000。 ),.,2,1(),()()( 1 njvvdvwvg ni jiij )(min)( jVv vgvg j 管 理 系 统 工 程 图 与 网 络 44 管 理 系 统 工 程 图 与 网 络 45 第 五 节 最 大 流 问 题最 大 流 问 题 ， 就 是 在 一 定 条 件 下 要 求 流 过 网 络的 流 量 为 最 大 的 问 题 。以 图 18 18所 示 的 运 输 网 络 为 例 来 说 明 求 解 过程 。 管 理 系 统 工 程 图 与 网 络 46 一 、 基 本 概 念1 容 量在 D=（ V， A） 上 的 每 条 弧 （ vi， vj） ， 都 规 定对 应 一 个 正 数 Cij， 称 为 弧 （ vi， vj） 的 容 量 ，在 运 输 网 络 中 Cij表 示 弧 （ vi， vj） 的 最 大 通 过能 力 。 定 义 了 容 量 的 图 D， 称 为 容 量 网 络 。 记D=（ V， A， C） 。 管 理 系 统 工 程 图 与 网 络 47 在 容 量 网 络 上 通 常 规 定 一 个 发 点 vS， 一 个收 点 vT， 其 余 都 是 中 间 点 。 对 于 有 多 个 发 （ 收 ）点 的 网 络 ， 只 要 假 设 一 个 总 发 （ 收 ） 点 ， 并 分别 与 各 发 （ 收 ） 点 连 起 来 ， 这 样 多 个 发 （ 收 ）点 的 网 络 问 题 就 转 化 为 单 个 发 （ 收 ） 点 的 网 络问 题 了 。 最 大 流 问 题 就 是 ： 要 把 发 点 处 的 一 批 货 物运 到 终 点 去 ， 在 每 一 条 弧 上 通 过 货 物 的 总 量 不能 超 过 这 条 弧 的 容 量 ， 问 应 该 怎 样 安 排 运 输 ，才 能 使 发 点 到 收 点 的 总 运 量 达 到 最 大 。 管 理 系 统 工 程 图 与 网 络 48 2 流设 D=（ V， A， C） ， 则 称 定 义 在 弧 集 A上 的 函 数为 网 络 D的 一 个 流 ， 其 中 每 一 个 f（ vi， vj） ， 简记 为 fij， 称 为 弧 （ vi， vj） 上 的 流 量 。例 如 图 18 18 A)vv()vv(ff jiji ， 管 理 系 统 工 程 图 与 网 络 49 满 足 下 列 条 件 的 流 f， 称 为 可 行 流（ 1） 相 容 条 件 ： 对 每 一 条 弧 ， 有（ 2） 平 衡 条 件 ： 对 每 一 个 中 间 点 vij， 有其 中 等 式 左 端 第 一 项 表 示 从 点 vi流 出 货 物 的 总量 ， 简 记 为 f（ vi， V） ； 第 二 项 表 示 流 进 vi点 的货 物 的 总 量 ， 简 记 为 f（ V ， vi） 。（ 3） 对 于 发 点 vS， 收 点 vT， 有其 中 v（ f） 为 非 负 数 ， 称 为 可 行 流 的 流 量 。 ijij Cf0 0 Avv jiAvv ij ijji ff ），（），（ )()()( )()()( fvvVfVvf fvvVfVvf TT ss ， ， 管 理 系 统 工 程 图 与 网 络 50 零 流 是 最 简 单 的 可 行 流 。 在 所 有 可 行 流 中 使 流 量 v（ f*） 最 大 的 可 行流 f*， 称 为 最 大 流 。 管 理 系 统 工 程 图 与 网 络 51 把 流 量 fij作 为 变 量 ， 根 据 可 行 流 的 定 义 及网 络 最 大 流 问 题 的 提 法 ， 可 见 最 大 流 问 题 也 是一 个 线 性 规 划 问 题 ， 其 数 学 模 型 为 ： 求 一 组 流量 fij使 )(0 )( ni)( 1n.32i0 1i)()(max 对 所 有 的 弧对 所 有 的 弧 （ 收 点 ）当 （ 中 间 点 ），当 （ 发 点 ）当满 足 ij ijij jiijf Cf fvfvff fv 管 理 系 统 工 程 图 与 网 络 52 3 增 广 链定 义 设 网 络 D=（ V， A， C） 中 有 一 个 流 f=fij，则 称fij=Cij的 弧 （ vi， vj） 为 饱 和 弧 。fijCij的 弧 （ vi， vj） 为 非 饱 和 弧 。fij=0的 弧 （ vi， vj） 为 零 流 弧 。fij 0的 弧 （ vi， vj） 为 非 零 流 弧 。定 义 设 是 网 络 D中 从 vS到 vT的 一 条 链 ， 这 条 链上 的 弧 可 以 分 成 两 类 ， 把 弧 的 方 向 与 链 的 方 向 一 致的 弧 ， 称 为 前 向 弧 ， 链 中 的 全 体 前 向 弧 记 为 +；把 弧 的 方 向 与 链 的 方 向 相 反 的 弧 ， 称 为 后 向 弧 ， 链中 的 全 体 后 向 弧 记 为 -。 管 理 系 统 工 程 图 与 网 络 53 定 义 设 有 D中 一 条 从 vS到 vT的 链 ， 如 果 的所 有 前 向 弧 是 非 饱 和 弧 ， 的 所 有 后 向 弧 为 非零 流 弧 ， 则 称 为 增 广 链 。例 图 18-18 管 理 系 统 工 程 图 与 网 络 54 4 截 集 与 截 量 截 集 是 指 将 容 量 网 络 中 的 发 点 与 收 点 分 割开 ， 使 vS到 vT的 流 中 断 的 一 个 弧 的 集 合 。例 图 18-18 管 理 系 统 工 程 图 与 网 络 55 令 则 称 弧 的 集 合 （ v1， v2） ， （ v3， v4） ，（ v3， v5） 为 一 个 截 集 ， 记 为 ，即 （ v1， v2） ， （ v3， v4） ， （ v3， v5） 称 为 截 量 。这 里 vvV 311 ， vvvvV 65421 ， )VV()vv( ji11 11ji )vv(C)VV(C ， ，)VV( 11， )VV( 11，216510)VV(C 11 ， 管 理 系 统 工 程 图 与 网 络 56 管 理 系 统 工 程 图 与 网 络 57 若 对 于 一 个 可 行 流 f*， 网 络 图 中 有 一 个截 集 ， 使则 f*必 是 最 大 流 ， 而 是 D的 所 有 截 集中 截 量 最 小 的 一 个 ， 即 最 小 截 集 。定 理 3： 可 行 流 f是 最 大 流 的 充 分 与 必 要 条 件是 不 存 在 关 于 f的 增 广 链 。定 理 4（ 最 大 流 量 最 小 截 量 定 理 ） ： 任 一 个网 络 D中 ， 从 vS到 vT的 最 大 流 的 流 量 等 于 分 离v S， vT的 最 小 截 集 的 容 量 。)VV( 11 ， )VV( 11 ， )VV(C)f(v 11 ， 管 理 系 统 工 程 图 与 网 络 58 二 、 求 最 大 流 标 号 法福 特 福 尔 克 逊 （ Ford Fuldkerson） 标 号 法 。 标 号 法 的 具 体 步 骤 如 下 ：1 标 号 过 程标 号 过 程 就 是 寻 找 增 广 链 的 过 程 。先 给 发 点 vS标 号 ， 即 ， 然 后 从 已 标 号 点 vi出 发 ， 找 出 与 之 相 邻 的 未 标 号 点 vj， 考 虑 ：（ 1） 如 果 连 接 vi与 vj的 弧 （ vi， vj） 是 前 向 弧 ，且 ， 则 给 vj标 号 ， 即 。（ 2） 如 果 连 接 vi与 vj的 弧 （ vi， vj） 是 后 向 弧 ，且 ， 则 给 v j标 号 ， 即 。1s Vv ijij Cf 1j Vv 1j Vv 0fij 管 理 系 统 工 程 图 与 网 络 59 对 已 标 号 点 重 复 （ 1） ， （ 2） 步 骤 ， 如 果vT得 到 标 号 ， 则 找 到 增 广 链 ， 转 入 调 整 过 程 ；如 果 标 号 中 断 ， 说 明 不 存 在 增 广 链 ， 则 现 行 的可 行 流 即 为 最 大 流 。2 调 整 过 程由 标 号 过 程 得 到 一 条 增 广 链 ， 则 调 整 量 为然 后 在 增 广 链 的 一 切 前 向 弧 +上 增 加 ， 一切 后 向 弧 -上 减 少 ， 不 在 增 广 链 上 的 弧 流 量不 变 。 这 样 得 到 一 个 新 的 可 行 流 ， 对 新 的 可 行流 重 新 转 入 标 号 过 程 。 fmin)fC(minmin ijijij ， 管 理 系 统 工 程 图 与 网 络 60 例 7 求 图 18 20所 示 网 络 的 最 大 流 ， 弧 旁 的 数字 是 容 量 Cij， 弧 旁 括 号 内 的 数 字 是 流 量 fij。 管 理 系 统 工 程 图 与 网 络 61 管 理 系 统 工 程 图 与 网 络 62 管 理 系 统 工 程 图 与 网 络 63 某 河 流 中 有 几 个 岛 屿 ， 从 两 岸 至 各 岛 屿 及各 岛 屿 之 间 的 桥 梁 编 号 如 图 6-20所 示 。 在 一 次敌 对 的 军 事 行 动 中 ， 问 至 少 应 炸 断 几 座 及 哪 几座 桥 梁 ， 才 能 完 全 切 断 两 岸 的 交 通 联 系 。 管 理 系 统 工 程 图 与 网 络 64 管 理 系 统 工 程 图 与 网 络 65 例 ： 电 信 公 司 准 备 在 甲 、 乙 两 地 沿 路 架 设 一条 光 缆 线 ， 问 如 何 架 设 使 其 光 缆 线 路 最 短 ？ 图7-6给 出 了 甲 、 乙 两 地 间 的 交 通 图 ， 图 中 的 点 v1 ， v2 ， ， v7表 示 7个 地 名 ， 其 中 v1表 示 甲 地 ， v7表 示 乙 地 ， 点 之 间 的 联 线 （ 边 ） 表 示 两 地 之间 的 公 路 ， 边 的 赋 权 数 表 示 两 地 间 公 路 的 长 度（ 单 位 为 公 里 ） 。