数学模型3-2最大流问题.pdf

最大流问题 所谓最大流问题就是在一定的条件下 要求流过 网络的物流 能量流或信息流等流量为最大的问 题 在最大流问题中一般有如下约定 网络有一个起点vs和一个终点vt 网络是有向网络 即流有方向性 在网络各条弧上都有一个权 表示允许流过的 最大流量 若以 ij表示由vi到vj的弧上允许流过 的最大流量 以xij表示实际流过该弧的流量 则 网络中 除起点vs和终点vt之外的任何顶点 流 入量总和应该等于流出量的总和 最大流问题的数学模型 vs 10 11 6 5 4 7 3 9 15 vt v5v3 v4v2 可行流 可行流 是指所有弧上流量满足容量限制 所有中间点满足平衡条件的流 零流是可行流 从零流到最大流 Ford Fulkerson方法 Ford Fulkerson方法原理 依据最大流问题的要求 为网络分配一个 可行流 可以取零流 若这一可行流的流量就是最大流量 则问 题已经解决 若不是最大流量 则增加流量获得流量更 大的可行流 Ford Fulkerson方法流图 求一个初始可行流 是 判断初始可行流是否最优结 束 不是 求使目标得到改善的可行流 求一个初始可行流 是 判断初始可行流是否最优结 束 不是 求使目标得到改善的可行流 Ford Fulkerson方法关键 关键问题 如何增加流量 怎样判断是否 需要增加流量 借助一个概念 伴随增量网络 伴随增量网络 给定网络G V E W W e 和可行流 e 对应的伴随增量网络G0 V0 E0 如 下定义 顶点集合V0 V 边集定义 任意e vivj E 若该边非饱和 即 e 0 u Q v P 则在伴随增量网络中包含一条从v到u的逆 向弧 从而u可达 这与u Q矛盾 对原网络中任意 e u v E 且u P v Q e w e 若不然 w e e 则在伴随 增量网络中包含一条从u到v的正向弧 从 而v可达 这与v Q矛盾 最小切割容量和最大流 给定网络流 即网络中每条边上的容量给 定 流量满足流平衡条件 任给一个切 割 P Q 前面定义的切割容量C P Q 是切割的函数 最小切割容量就是最大流 说明 切割容量作为切割的函数对任意可 行流都满足流量公式 即切割容量不小于 流量 对最大流来说 不等式取等号 vs 10 11 6 5 4 7 3 9 15 vt v5v3 v4v2 P Vs c P Q 24 P Vs V3 V5 c P Q 33 P Vs V2 c P Q 20 P Vs V2 V4 c P Q 24 P Vs V2 V3 c P Q 22 P Vs V5 c P Q 34 P Vs V3 c P Q 29 P Vs V4 c P Q 35 P V2 V2 V4 V3 V5 c P Q 21 关于FF算法的说明 FF算法只对有理数容量成立 对于有理数容量 进行适当的 单位 转换为整数 容量 对于整数容量 由于每次通过增广链调整 的容量为整数 故有限步总可以调整到最大流 反例 Zwick Uri The smallest networks on which the Ford Fulkerson maximum flow procedure may fail to terminate Theoretical Computer Science 148 1 165 170 1995 反例 From Wikipedia http en wikipedia org wiki Ford E2 80 93Fulkerson algorithm r s v1 t v2 v4 v3 r 1 1 m m m mm m 反例 增广链 Residual Capacity StepPath Sent flow e1 v2 v1 e2 v4 v3 e3 v2 v3 0 r0 1r1 1p01r0 1r0 2