网络最大流问题.ppt

课程讲授 黄玉诚 运筹学 中国矿业大学 北京 第六章图与网络分析 第一节图的基本知识第二节树第三节最短路问题第四节网络最大流问题第五节最小费用最大流问题 第四节网络最大流问题 图10 23是联结某产品产地v1和销地v6的交通网 每一弧 vi vj 代表从vi到vj的运输线 产品经这条弧由vi输送到vj 弧旁的数字表示这条运输线的最大通过能力 现在要求制定一个运输方案使从v1运到v6的产品数量最多 图10 23 图10 24给出了一个运输方案 每条弧旁的数字表示每条运输线上的运输数量 这个方案使8个单位的产品从v1运到v6 在这个运输网络中 从v1到v6的最大输送量是多少呢 图10 23 图10 24 一 基本概念与基本定理 1 网络与流定义1给一个有向图D V A 在V中指定了一点 称为发点 记为vs 和另一点 称为收点 记为vt 其余的点叫中间点 对于每一个弧 vi vj A 对应有一个c vi vj 0 或简写为cij 称为弧的容量 通常把这样的D叫作一个网络 记作D V A C 对D中的任一弧 vi vj 有流量f vi vj 有时也简记作fij 称集合f fij 为网络D上的一个流 2 可行流与最大流 定义2满足下述条件的流f称为可行流 1 容量限制条件 对每一弧 vi vj A0 fij cij 可行流 2 平衡条件 对于中间点 流出量 流入量 即对每个i i s t 有 对于发点vs 式中v f 称为这个可行流的流量 即发点的净输出量 或收点的净输入量 所谓最大流问题就是在网络中 寻找流量最大的可行流 即 求一个流 fij 使其流量v f 达到最大 并且满足0 fij cij vi vj A 最大流 可行流总是存在的 例如 fij 0就是一个流量为0的可行流 3 增广链 若给一个可行流f fij 我们把网络中使fij cij的弧称为饱和弧 使fij0的弧称为非零流弧 若 是网络中联结发点vs和收点vt的一条链 我们定义链的方向是从vs到vt 则链上的弧被分为两类 一类是弧的方向与链的方向一致 叫作前向弧 前向弧的全体记为 另一类弧与链的方向相反 称为后向弧 后向弧的全体记为 定义3设f是一个可行流 是从vs到vt的一条链 若 满足下列条件 称之为 关于可行流f的 一条增广链 在弧 vi vj 上 0 fij cij 即 中每一弧是非饱和弧 在弧 vi vj 上 0 fij cij 即 中每一弧是非零流弧 图10 24中 链 v1 v2 v3 v4 v5 v6 是一条增广链 因为 和 中的弧满足增广链的条件 如 v1 v2 f12 50 4 截集与截量 设S T V S T 我们把始点在S 终点在T中的所有弧构成的集合 记为 S T 定义4给网络D V A C 若点集V被剖分为两个非空集合V1和 使vs V1 vt 则把弧集 V1 称为是 分离vs和vt的 截集 可以看出 从网络中去掉任一截集 则从vs到vt便不存在路 所以 截集是从vs到的vt必经之路 定义5给一截集 V1 把截集 V1 中所有弧的容量之和称为这个截集的容量 简称为截量 记为c V1 即 任何一个可行流的流量v f 都不会超过任一截集的容量 即 显然 若对于一个可行流f 网络中有一个截集 V1 使v f c V1 则f 必是最大流 而 V1 必定是D的所有截集中容量最小的一个 即最小截集 定理1可行流f 是最大流的充分必要条件是不存在从vs到vt的 关于f 增广链 由增广链的定义 可知 0 令网络上的另一个流 仍为可行流 即满足容量限制条件与平衡条件 但的总流量等于的流量加 即 这与是最大流的前提矛盾 二 充分性 若不存在关于f 增广链 那么f 是最大流 显然有 那么 可行流f 上的流量 则f 必然是最大流 最大流量最小截量定理 任一个网络D中 从vs到vt的最大流的流量等于分离vs vt的最小截集的容量 增广链的实际意义是 沿着这条链从vs到vt输送的流 还有潜力可挖 只需按照定理1证明中的调整方法 就可以把流量提高 调整后的流 在各点仍满足平衡条件及容量限制条件 即仍为可行流 这样就得到了一个寻求最大流的方法 从一个可行流开始 寻求关于这个可行流的增广链 若存在 则可以经过调整 得到一个新的可行流 其流量比原来的可行流要大 重复这个过程 直到不存在关于该流的增广链时就得到了最大流 寻求最大流的思路 利用定理1中对V1 定义 根据vt是否属于V1 来判断D中有无关于f的增广链 实际计算时 可以用给顶点标号的方法来确定属于V1 的点 在标号过程中 有标号的顶点表示是V1 中的点 没有标号的点表示不是V1 中的点 一旦vt有了标号 就表明找到一条增广链 如果标号过程进行不下去 而vt尚未标号 则说明不存在增广链 于是得到最大流 而且同时也得到一个最小截集 二 寻求最大流的标号法 在标号过程中 网络中的点分为两类 1 标号点 又分为已检查和未检查两种 每个标号点的标号内容包含两部分 标号的第一部分表明它的标号是从哪一点得到的 以便找出增广链 标号的第二部分是为确定增广链的调整量 用的 2 未标号点 标号过程 1 给发点vs标上 0 这时vs是标号而未检查的点 其余都是未标号点 2 取一个标号而未检查的点vi 对于vi的所有未给标号的相邻点vj按下列规则处理 a 若在弧 vi vj 上 fij cij 则给vj标号 vi l vj 这里l vj min l vi cij fij 这时点vj成为标号而未检查的点 b 若在弧 vj vi 上 fji 0 则给vj标号 vi l vj 这里l vj min l vi fij 这时点vj成为标号而未检查的点 这样 vj成为标号而已检查过的点 若vt未获得标号 而标号过程无法进行时 则算法结束 这时的可行流f就是最大流 3 重复步骤 2 直到vt被标上号 表明得到一条从vs到vt的增广链 转入调整过程 例如 设vt的第一个标号为vk 则弧 vk vt 是 上的弧 接下来检查vk的第一个标号 若为vi 则找出 vi vk 再检查vi的第一个标号 依此下去 直到vs为止 这时被找出的弧就构成了增广链 1 找出增广链 按vt及其它点的第一个标号 利用 反向追踪 的办法 找出增广链 2 在增广链上调整流量 令调整量 为l vt 即vt的第二个标号 3 去掉所有的标号 对新的可行流 重新进入标号过程 例用标号法求图10 25所示网络的最大流 弧旁的数是 cij fij 解 一 标号过程 1 首先给vs标上 0 0 图10 25 2 检查vs vs 4 弧 vs v1 上 fs1 1 cs1 5 fs1 cs1 则v1的标号为 vs l v1 其中 l v1 min l vs cs1 fs1 min 5 1 4 在弧 vs v2 上 fs2 cs2 3 不满足标号条件 3 检查v1 v1 1 在弧 v2 v1 上 f21 1 0 则给v2记下标号为 v1 l v2 这里l v2 min l v2 f21 min 4 1 1 在弧 v1 v3 上 f13 2 c13 2 不满足标号条件 4 检查v2 v2 1 v2 1 在弧 v2 v4 上 f21 3 c24 4 f24 c24 则给v4标号 v2 l v4 l v4 min l v2 c24 f24 min 1 1 1 在弧 v3 v2 上 f32 1 0 给v3标号 v2 l v3 l v3 min l v2 f32 min 1 1 1 5 在v3 v4中任选一个进行检查 v4 1 例如 在弧 v4 vt 上 f4t 3 c4t 5 f4t c4t 给vt标号为 v4 l vt 这里l vt min l v4 c4t f4t min 1 2 1 因vt有了标号 故转入调整过程 二 调整过程 1 按点的第一个标号找到一条增广链 2 在增广链上调整流量 在增广链上 vs v1 v2 v4 v4 vt v2 v1 上 调整后的网络图如下 0 一 标号过程 1 首先给vs标上 0 0 2 检查vs vs 3 弧 vs v1 上 fs1 2 cs1 5 fs1 cs1 则v1的标号为 vs l v1 其中 l v1 min l vs cs1 fs1 min 5 3 3 在弧 vs v2 上 fs2 cs2 3 不满足标号条件 0 vs 3 3 检查v1 标号过程无法继续下去 算法结束 在弧 v2 v1 上 f21 0 不满足标号条件 在弧 v1 v3 上 f13 2 c13 2 不满足标号条件 这时的可行流即为所求最大流 最大流量为 v f fs1 fs2 f4t f3t 5 同时 可以得到已标号点集合V1 vs v1 和未标号点集合 v2 v3 v4 vt 相应地 弧集合 vs v2 v1 v3 即为最小截集 它的容量也是5 等于最大流量 由此 也可以体会到最小截集的意义 网络从发点到收点的各通路中 向容量决定其通过能力 最小截集则是这些路中的咽喉部分 或者叫瓶颈 其容量最小 它决定了整个网络的最大通过能力 要提高整个网络的运输能力 必须首先改进这个咽喉部分的通过能力 图10 23 例如 图10 23就是一个网络 指定v1是发点 v6是收点 其它的点是中间点 弧旁的数字为cij 图10 24所示的运输方案 就可看作是这个网络上的一个流 每个弧上的运输量就是该弧上的流量 如 f12 5 f24 2 f13 3 f34 1 图10 24 图10 24给出了一个运输方案 每条弧旁的数字表示每条运输线上的运输数量 这个方案使8个单位的产品从v1运到v6 在这个运输网络中 从v1到v6的最大输送量是多少呢 图10 23 图10 24 图10 24中 v5 v4 是饱和弧 其它的弧为非饱和弧 所有弧都是非零流弧 图10 23 图10 24 图10 23 图10 23中 在链 v1 v2 v3 v4 v5 v6 中 v1 v2 v2 v3 v3 v4 v5 v6 v5 v4 图10 24中 链 v1 v2 v3 v4 v5 v6 是一条增广链 因为 和 中的弧满足增广链的条件 比如 v1 v2 f12 50 图10 24 图10 23 1 1 1 1 1 图10 23 例如 弧集 v1 v2 v2 v3 v2 v5 v2 v4 弧集 v2 v4 v2 v5 v3 v4 v3 v5 都是网络D的截集 弧集 v4 v6 v2 v5 v3 v5 也是网络D的截集 图10 23 例如 弧集 v1 v2