运筹学第7章 最大流问题(精简).ppt

最大流问题 给定一个有向图G V E 其中仅有一个点的入次为零称为发点 源 记为vs 仅有一个点的出次为零称为收点 汇 记为vt 其余点称为中间点 基本概念 3 5 1 1 4 2 3 5 2 vs v2 v1 v3 v4 vt 对于G中的每一条边 vi vj 相应地给一个数cij cij 0 称为边 vi vj 的容量 我们把这样的网络G称为容量网络 记为G V E C 网络上的流 是指定义在边集E上的函数f f vi vj 并称f vi vj 为边 vi vj 上的流量 简记为fij 3 1 5 2 1 0 1 0 4 1 2 2 3 1 5 2 2 1 vs v2 v1 v3 v4 vt 标示方式 每条边上标示两个数字 第一个是容量 第二是流量 可行流 可行流的流量 最大流 可行流是指满足如下条件的流 1 容量限制条件 对G中每条边 vi vj 有 2 平衡条件 对中间点 有 即中间点vi的物资输入量等于输出量 对收点vt与发点vs 有 即vs发出的物资总量等于vt接收的物资总量 W是网络的总流量 可行流总是存在的 例如f 0 就是一个流量为0的可行流 所谓最大流问题就是在容量网络中寻找流量最大的可行流 一个流f fij 当fij cij 则称f对边 vi vj 是饱和的 否则称f对边 vi vj 不饱和 对于不饱和的 其间隙为 ij cij fij最大流问题实际上是一个线性规划问题 但利用它与图的密切关系 可以利用图直观简便地求解 给定容量网络G V E C 若点集V被剖分为两个非空集合V1和V2 使vs V1 vt V2 则把边集 V1 V2 称为 分离vs和vt的 割集 显然 若把某一割集的边从网络中去掉 则从vs到vt便不存在路 所以 直观上说 割集是从vs到vt的必经之路 3 5 1 1 4 2 3 5 2 vs v2 v1 v3 v4 vt vs v1 v4 v3 vt v2 边集 vs v1 v1 v3 v2 v3 v3 vt v4 vt 是G的割集 其顶点分别属于两个互补不相交的点集 去掉这五条边 则图不连通 去掉这五条边中的任意1 4条 图仍然连通 割集的容量 简称割量 最小割集 割集 V1 V2 中所有起点在V1 终点在V2的边的容量的和称为割集容量 例如下图中所示割集的容量为5 3 5 1 1 4 2 3 5 2 vs v2 v1 v3 v4 vt 在容量网络的所有割集中 割集容量最小的割集称为最小割集 最小割 对于可行流f fij 我们把网络中使fij cij的边称为饱和边 使fij0的边称为非零流边 设f是一个可行流 是从vs到vt的一条链 若 满足前向边都是非饱和边 后向边都是都是非零流边 则称 是 可行流f的 一条可增广链 3 1 5 2 1 0 1 0 4 1 2 2 3 1 5 2 2 1 vs v2 v1 v3 v4 vt 若 是联结发点vs和收点vt的一条链 我们规定链的方向是从vs到vt 则链上的边被分成两类 前向边 后向边 对最大流问题有下列定理 定理1容量网络中任一可行流的流量不超过其任一割集的容量 定理2 最大流 最小割定理 任一容量网络中 最大流的流量等于最小割集的割量 推论1可行流f fij 是最大流 当且仅当G中不存在关于f 的增广链 求最大流的标号法 标号法思想是 先找一个可行流 对于一个可行流 经过标号过程得到从发点vs到收点vt的增广链 经过调整过程沿增广链增加可行流的流量 得新的可行流 重复这一过程 直到可行流无增广链 得到最大流 标号过程 1 给vs标号 vs成为已标号未检查的点 其余都是未标号点 2 取一个已标号未检查的点vi 对一切未标号点vj 若有非饱和边 vi vj 则vj标号 vi l vj 其中l vj min l vi cij fij vj成为已标号未检查的点 若有非零边 vj vi 则vj标号 vi l vj 其中l vj min l vi fji vj成为已标号未检查的点 vi成为已标号已检查的点 3 重复步骤 2 直到vt成为标号点或所有标号点都检查过 若vt成为标号点 表明得到一条vs到vt的增广链 转入调整过程 若所有标号点都检查过 表明这时的可行流就是最大流 算法结束 调整过程 在增广链上 前向边流量增加l vt 后向边流量减少l vt 下面用实例说明具体的操作方法 例 3 3 5 1 1 1 1 1 4 3 2 2 3 0 5 3 2 1 vs v2 v1 v3 v4 vt 3 3 5 1 1 1 1 1 4 3 2 2 3 0 5 3 2 1 vs v2 v1 v3 v4 vt 在图中给出的可行流的基础上 求vs到vt的最大流 vs 4 v1 1 v2 1 v2 1 v3 1 3 3 5 2 1 0 1 0 4 3 2 2 3 0 5 3 2 2 vs v2 v1 v3 v4 vt vs 3 得增广链 标号结束 进入调整过程 无增广链 标号结束 得最大流 同时得最小割 下图中已经标示出了一个可行流 求最大流 vs 3 vs 4 v2 4 v4 2 v4 3 如图已经得到增广链 然后进行调整 调整后的可行流如下图 vs 3 vs 1 v2 1 v4 1 v3 1 v5 1 如图已经得到增广链 然后进行调整 调整后的可行流如下图 vs 3 如图所示最小割集的容量 即当前可行流的流量 就是最大流的流量 注 用该方法可以同时得到最小割集 即图中连结已标号的点与未标号的点的边集 具有实际背景的例子 国庆大假期间旅游非常火爆 机票早已订购一空 成都一家旅行社由于信誉好 服务好 所策划的国庆首都游的行情看好 要求参加的游客众多 游客甚至不惜多花机票钱辗转取道它地也愿参加此游 旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题 很快 各办事处将其已订购机票的情况传到了总社 根据此资料 总社要作出计划 最多能将多少游客从成都送往北京以及如何取道转机 下面是各办事处已订购机票的详细情况表 用图来描述就是 发点vs 成都 收点vt 北京 前面已订购机票情况表中的数字即是各边上的容量 允许通过的最大旅客量 当各边上的实际客流量为零时略去不写 以零流作为初始可行流 利用标号法 经5次迭代 可以得到从成都发送旅客到北京的最大流量如图所示 重 武 昆 上 广 西 郑 沈