06.6最大流.ppt

* * 运 筹 学 Operations Research 在生产生活中有许多网络，如电网、供水网、原油管道运输网、交通运输网、通讯网、国际互联网等．以供水网络为例，设仅有一个出水口和一个进水口．网络每段管道都有一个容量（单位时间内通过管道的最大水量）．水由出水口流出经过水管网络后流入进水口，这就形成一个水的实际的稳定的有向的流动，称之为流． 显然，流具有如下性质： （1）每段管道中通过的流量不超过该管道的容量； （2）网络的每个内部顶点处的流入量等于与流出量； （3）出水口的总流出量等于进水口的流入量．因受自身网络结构的限制，通过水管网络的流必有一个最大界限，称之为最大流． §6.6 最大流问题 运 筹 学 Operations Research 网络（network）： 单发点单收点网络： 发点：s（只流出） 收点：t（只流入） 中间点： （中转） 运 筹 学 Operations Research 弧的容量： 割（cut）： 割是从s到t的必经之道（桥），而割的容量则为桥的最大通过能力. 运 筹 学 Operations Research 割的容量： 最小割（minimum cut）：容量最小的割. 如 运 筹 学 Operations Research 弧的流量（flux）： 流（flow）： f 符号： 运 筹 学 Operations Research 可行流（feasible flow）： 流值（flow value）： 运 筹 学 Operations Research 零流（zero flow）：弧的流量都是0的流. 显然，零流是一个可行流，且流值为0. 最大流（maximum flow）：流值最大的可行流. 最大流问题：在网络中找一个最大流. 弧的分类： （1）按流量和容量的大小关系分： 饱和弧（saturated arc）： 不饱和弧（unsaturated arc）： 运 筹 学 Operations Research （2）按流量和0的大小关系分： 零弧（zero arc）： 非零弧（nonzero arc，positive arc）： （3）按流量和有向路的关系分： 设P是一条有向(s，t)-路，其方向为s→ t. 前（正）向弧（forward arc）：与P的方向一致的弧 后（反）向弧（forward arc）：与P的方向相反的弧 运 筹 学 Operations Research 可增广路（augmenting path）：前向弧均为不饱和弧，后向弧均为非零弧的路. ▌ ▌ 运 筹 学 Operations Research ▌ 运 筹 学 Operations Research Th2 设f是网络N的一个可行流，则f是最大流 N中不存在关于f的可增广路.▌ Th3（最大流最小割定理，max-flow，min-cut theorem）网络的任一最大流的流值等于任一最小割的容量.▌ 最大流算法 理论依据：Lemma 1和Th2. 算法的关键：找可增广路. 基本思想：流程 运 筹 学 Operations Research 运 筹 学 Operations Research 计算过程： 运 筹 学 Operations Research 若T在到达t之前停止生长，则不存在关于f的可增广路，f即为最大流； 若T生长到达t（breakthough），则T中的有向(s,t)-路即为一条可增广路；此时，t被标号，且l(P)= l(t).修改f. 重复上述过程，直到得到最大流. 运 筹 学 Operations Research 生长过程应遵循“先标号者，先检查”的原则，以尽可能地减少修改次数. 运 筹 学 Operations Research 例1 求解最大流问题： 解： 运 筹 学 Operations Research 运 筹 学 Operations Research ▌ 运 筹 学 Operations Research 例2 求网络的最大流和最小割： 解： ▌ * * *