研究论文：网络最大流算法的改进（可编辑）

研究：网络最大流算法的改进（可编辑） 研究论文:网络最大流算法的改进 邵 阳 高专 学报 年 第 卷 第 期 网络 最 大流 算 法 的 改 进 罗 会 兰 校长室 摘 要 将 已有的 网络最大流 的算法 一标号法改进 为断路法 , 从而加快 了求 网络最大流 的速 度并减少作标号图的麻烦 关键词 最大流 同向路 满值弧 断路法 分类号 幻 网络最大流 的有关概念简述 , , , 图论 中一个重要 问是求 网络 的最大流 在有 向图 一 中 总可视 为 只有一个发 , , , ‘ , , , 一 ‘, 、, , , 一 点 一个收点 其余 皆为 中间 点 „ 中的每一条弧 都对 , , , 应一个数 一般称为最大通 过 能力 简记 为 , 称为弧 , 的容量 这样 的赋权有 向图叫 做一个容量 网络 如 图 其 中每条弧 旁标 出的数 即为这条弧 的容量 图 、 、 , 。 , 、 , 。 在 网络 中 把通过 弧 , 的运量 诸 如货物量 车流量 信息量等等 记 为 关 称为弧 上 的 , , 流量 显然 镇 关 簇 ’ , , 二 王 , 关 上 流 当 关 足下列 时 网络上流量 的集合 称为 网络 的 王 满 条件 镇 关 镇 , , ‘ , , “ 对于 中间点 ‘ 有 艺关 一 艺 一 艺几示 由 流 出的流量和 艺 表示 ?? , , 流入 的流量和 即流 出量 一 流入量 , , , , 对于 发 点 , 记 习二, 一 习九, 一 二 即用 二 表 示 , 的净发 出量 一般它是 的函数 之 ?? 。 , , 、 , 一 二 那 么 对于 收点 则有 艺式 一 , 一 二 即 从 的净收量等 于 , 的净 发 量 , 一 二 则称 为 为一可行 流 此 时 称 为可行流 的流量 , , , , , , 。 任意 网络 中 可行流 总是存在 的 比方令 所有 的 关 一 就得 到 可行 的零流 此 时 一 图 ?? 即表示对 应 的可行 流 为零 流 , , , , 网络上最 大流 的 问题 就是要在给 定 的 网络上 求一个可行流 一 关 使得 流量 试 取 得最大值 求最大 流 间题 , 又 联 系着可增值 路 概念 收 稿 日期 一 一 ? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. , , , ‘ , 设 网络 中有一条从 发点 到收 点 的路 凡与路指 向相 同的弧 称为前 向 弧 , 上 , , ‘ 有 关, , 与路指 向相反 的弧 称为后 向 弧 , 上 有 几 则称这样 的路为增值路 找最大流 的 用 是 是找 路 , 可 流 网 常 标号法 标号法 即 可增 值 的方法 在给定初始 行 的 络 , 通过 一定 则 网 于 , 不 , 到 一 , 中 规 给 络 中的点标号 限 篇幅 本文 详述标号规则 找 条 增值路 然 , , 后给这增值路按一定 的规则增加流量 得 到一个新 的可行流 尹 画 出 对应新 的可行流 尹 的网 络 图 , 然后再标号 , 再找一条 可增值路 , 得第二个新 的可行 流 尹 , 画 出对应 尸 的网络 图, 再标号 „ „ 到 不 , 网 画 , 二 直 找 出可增值路 了 则得 到 络 的最大流 它 的缺点就是要 多个标号 图 很麻烦 求 网络最大流 的改进方法 断路法 ― 在标号法 的启发下 , 笔者根据找增值路 的思想 以及 最大流 最 小截量 , 认 为可 以 , ― 把 网络最大流 的方法如下简化 不 网 已 , 到 , 妨假设 络初始可行流 为零流 即使 给 定别 的初始可行流 也可退 零流 因为这 不 影 响最后所求得 的最大流 的值 在此基础 上按 以下步骤操作 , , , 第一步 找一条 以发 点 , 为起 点 以收 点 为终点且 中间点较少 的路 若这 条路上有后 向 , , 上 , , 以后 , 弧 则弃之 另找 根据刚才 的假设 后 向弧 流量为零 故丢弃这样 的路 不影 响 的调整 , , 以 , 因此 约定找 的路上仅含前 向弧 这样 的路总是可 找到 的 否则 网络上 的最大流量就是零流 , , , , , 把仅含前 向弧 的 , 到 的路 叫做 同 向路 比方 在 图 中找到这样 的路 为 。 , , , 第二步 比较所找 出的路 中弧 的容量 设其各弧容量 的 最小值为 。 则令此路上各弧 的流 , , , 量均增加 。 这 时对应容量为最 小值 勘 的 弧 , 上有流量 亏 容量 称此弧 为满值弧 在这满值 弧上划 “ ” , 表示此 路已断 , 下次不可再走 比方 图 中已找到 的 路 , , , , 中, 弧 , , , , , , , 。 容量最小 其值为 则在这条路上各弧上增加流量 用括 号括住 且 除去弧 外 , , , , , , “ ” 均 只写左边括号 右边 空着 以便 以后可往上加数 同时弧 为满值弧 在其上划 到 , 一 上 , 于 , 画 一 如 图 本文最后会看 到 这 些 工作 可画在 个 总 图 这 里 为便 说 明 暂且每步均 图 三步 , 观 已找路 的 一 弧 否 , , 量 于 已有流 , 原 量 第 察 第 条 是 满值 若未满值 即其容 大 量 将 有容 已 , , 后 否 到 通 收 减去 有 流量 的值称为余容量 即余容量不 为零 时 则考虑 接此 弧 是 还 可 找 往 点 , , , , 已 , 的同 向路 若可找到 则按第二步操作 若找不 到 则将第一条弧 上 给流量右边加上括号 表示此条 弧流量 已达最大 如 图 中第一条弧 , 虽未满值 , 但紧接只有后 向 弧 , , , , , 无 同 向路通 故在 弧 , 的流量 右 边加括号 已在 图 中实 施 , , , 以后 则重复第一步到第三 步 的操作 在这过 程 中如果有 的弧上 流量 不 为 。 则该弧 的容 , , “ ” 量应理解为余容量 直到 图中由 到 的同向路都被 断掉 则这 时最大流就是 以 为 起 点 的各条路上 的第一条弧上 的各流量之和 , , , , , , , 如 图 中 重复第一步 可找到 第二条 同 向 路 , 。 声 明一点 的是不 能找 , , 。, 了 , 因 , , 后 者 中间点较多 中间点较多 的路 总在稍后再 找 这样可避免把 中间点较少 , , , , , , 的路 去掉 所 以总是先找 中间 点较少 的路 这条路上 第一条 弧 , 。 容量最 小 。一 故 , , , , “ ” 将这条路 上各弧 的流量 由 。增 为 同时 弧 已满值 在其上划 如 图 图 图 再重 复第一步 找到 第三 条 同 向 路 、 , 。 , 这 条路 上 弧 , 的容量 要理解 为余容 , , , , , 量 一 一 与弧 的容量 同为最 小 故在这条 路上 各弧 的流量均增加 同时 弧 ’ ‘ , , 。 ” , 和 均 满值 在其上均 划 考察这 条路上 的第一条 弧 。还 未满值 有 余容 ? 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. ,