下载文档原格式
⽹络流基础-最⼤流最⼩割定理
最⼤流最⼩割定理，指⽹络流的最⼤流等于其最⼩割。
最⼤流指符合三个性质的前提下，从S到T能流过的最⼤流量。
最⼩割指符合割的定义，最⼩的割容量。
求最⼤流：
不断寻找增⼴路，计算能增加的最⼩流量，然后增加。
找到⼀条增光路，最多能流过2，则：
找到第⼆条路径：
最后还剩a-c-e⼀条，则可计算出最⼤流量为4。
但遇到以下情况，且第⼀条路径为a-b-c-d时，就不⾏了：
此时需要增加反向路径，即当减去增⼴路时，反向加上减去的流量，提供后悔的选择：
这样，当考虑a-c-b-d时，可以对冲掉b-c的流量。
证明：
定理⼀：对于任⼀割和任⼀流，流量等于正向割边流量减去反向割边流量。
即f = f c+ - f c-，其中c+代表正向割边流量。
推论：任⼀割容量必定⼤于等于任⼀流量，由于：C+ > f c+ > f c+ - f c- > f。
则如果存在某流量和某割，则此流量必定为最⼤流，此割必定为最⼩割。
当我们计算出最⼤流时，不妨思考下此时的残留⽹络：
此时残留⽹络不存在增⼴路，即不存在⼀条能从S到T的路径。
此时残留⽹络中，我们把S能到达的节点记为s'集，能到达T的节点记为t’集，则s'和t'构成割集。
在残留⽹络中，流量指容量为0的边（满流），⽽这些边⼜是割边，所以流量和等于割的容量和。
⽐如对于：
其⼀个残留⽹络为：
其中两条虚线边为满流的边，也是割边。
第七章Operational厂§ 4网络最大流问题网络最大流冋题是网络的另一个基本冋题。
许多系统包含了流量问题。
例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。
许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。
4.1基本概念与定理1. 1.网络与流定义14 （1）网络：例1如图7-20是连结某产品产地’和销地一的交通图。
弧:1 表示从二到匚的运输线，弧旁的数字表示这条运输线的最大通过能力，.，括号内的数字表示该弧上的实际流一［。
现要求制定一个运输方案，使从一运到尸，的产品数量最多。
可行流与最大流输网络的实际问题中，我们可以看出，对于流有两个基本要求：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力(即该弧的容量)二是起点发出的流的总和(称为流量)，必须等于终点接收的流的总和，且各中间点流 入的流量之和必须等于从该点流出的流量之和， 即流入的流量之和与流出的流量之和的差为 零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。
因此有下面所谓的可行流的定义。
定义14对于给定的网络 D=(V,A,C )和给定的流 』」：.「，若「满足下 列条件:(1)容量限制条件：对每一条弧 .-，有- -(7.9)(2)平衡条件： 对于中间点：流出量=流入量，即对于每一个对于出发带点T ：，有SA -'K/)对于收点①，有 工二 'I(7.12)则称/ - ■为一个可行流，•-称为这个可行流的 流量。
注意，我们这里所说的出发点 r 是指只有从匚发出去的弧，而没有指向J 的弧;收点二是指只有弧指向--，而没有从它的发出去的弧。
在运i (i 丰 s,t)，有(7.10)(7.11)可行流总是存在的。
例如令所有弧上的流，就得到一个可行流，（称为零流）,其流量 ': 一。
如图7-20中，每条弧上括号内的数字给出的就是一个可行流 3 - f/yJ ，它显然满足定义中的条件（1 ）和（2）。
1、网络与流设一个赋权有向图D=（V, A ）,在V 中指定一个发点v s 和一个收点v t (本题中，1V 和7V 分别是发点和收点)其它的点叫做中间点。
对于D 中的每一个弧（v i , v j ）∈A ,（i ，j {1，2，3，4，5，6，7}） 都有一个非负数c ij ,叫做弧的容量。
我们把这样的图D 叫做一个容量网络， 简称网络，记做D =（V ，A ，C ）。
弧的容量：是对网络上的每条弧(v i ,v j )都给出一个最大的通过能力，记为c (v i ,v j )或简写为c ij 。
2．流：加在网络各条弧上的一组负载量f(v i ,v j )：加在弧(v i ,v j )上的负载量，简记为f ij ，为非负数网络上的流：是指定义在弧集合上的一个函数f={f(v i ,v j )},其中f(v i ,v j )称为弧（v i ,v j )上的流量，流也可看作一个双下标变量。
3.弧的流量f(v i ,v j )：表示弧(v i ,v j )上每单位时间内的实际通过能力 弧的容量c(v i ,v j )：表示弧（v i ,v j )上每单位时间内的最大通过能力 对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。
(2)每一个中间点的流入量与流出量的代数和等于零。
(3)每一个弧上的流量不能超过它的最大通过能力（即容量）.4.可行流与最大流称满足下列条件的流为可行流：（1）容量限制条件：对于每一个弧（v i ,v j ）∈A ，有 0≤f(v i ,v j ) ≤c(v i ,v j ) （简记为0≤ f ij ≤ c ij ）（2）平衡条件1，对出发点1V 有，()11j j f f V f -=∑∑2.对于收点7V 有， ()77j j f f V f -=-∑∑式子中V(f)称为可行流f 的流量,即发点的净输出量（或收点的净输入量）。
3.对于中间点: 流入量=流出量。
给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。
对于A中的每一条弧，对应一个数（简记），称之为弧的容量。
通常我们把这样的D叫做网络，记为D=(V,A,C)。
（2）网络流：在弧集A上定义一个非负函数。
是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。
§4 网络最大流问题网络最大流问题是网络的另一个基本问题。
许多系统包含了流量问题。
例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。
许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。
4.1 基本概念与定理1．1．网络与流定义14 （1）网络：例1如图7-20是连结某产品产地和销地的交通图。
弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。
现要求制定一个运输方案，使从运到的产品数量最多。
可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个基本要求：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）；二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。
因此有下面所谓的可行流的定义。
定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件：（1）容量限制条件：对每一条弧，有(7.9)（2）平衡条件：对于中间点：流出量=流入量，即对于每一个i (i≠s,t)，有(7.10)对于出发带点，有(7.11)对于收点，有(7.12)则称为一个可行流，称为这个可行流的流量。
注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧；收点是指只有弧指向，而没有从它的发出去的弧。
