最小截集什么意思,网络流的资料( 三 ) _设备更新

根据以上分析可以得出delta的计算公式:
因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，所以delta > 0 。
容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”(即输入量等于输出量)，又可以使得总的流量有所增加(因为delta > 0) 。
因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在的问题是:倘若在f中找不到可改进路，是不是f就一定是最大流呢?
答案是肯定的。下面我们给出证明。
定理1 可行流f是最大流的充分必要条件是:f中不存在可改进路。
证明:
首先证明必要性:已知最大流f，求证f中不存在可改进路。
若最大流f中存在可改进路P，那么可以根据一定规则(详见上文)修改P中弧的流量。可以将f的流量放大，这与f是最大流矛盾。故必要性得证。
再证明充分性:已知流f，并且f中不存在可改进路，求证f是最大流。
我们定义顶点集合U, W如下:
(a) S∈U，
(b) 若x∈U，且fxy 若x∈U，且fyx>0，则y∈U 。
(这实际上就是可改进路的构造规则)
(c) W = V \ U 。
由于f中不存在可改进路，所以T∈W;又S∈U，所以U、W是一个割切(U, W) 。
按照U的定义，若x∈U，y∈W，则fxy = cxy 。若x∈W，y∈U，则fxy = 0 。
所以，
又因 v(f)≤C(U,W)
所以f是最大流。得证。
根据充分性证明中的有关结论，我们可以得到另外一条重要定理:
最大流最小割定理:最大流等于最小割，即max V(f) = min C(U, W) 。
至此，我们可以轻松设计出求最大流的算法:
step 1. 令所有弧的流量为0，从而构造一个流量为0的可行流f(称作零流) 。
step 2. 若f中找不到可改进路则转step 5;否则找到任意一条可改进路P 。
step 3. 根据P求delta 。
step 4. 以delta为改进量，更新可行流f 。转step 2 。
step 5. 算法结束。此时的f即为最大流。
三、最小费用最大流
1.问题的模型
流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。
图5-8是一个最简单的例子:弧上标的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的花费，譬如fs1=4，所需花费为3*4=12 。
容易看出，此图的最大流(流量是8)为:fs1 = f1t = 5, fs2 = f2t = 3 。所以它的费用是:3*5+4*5+7*3+2*3 = 62 。
一般的，设有带费用的网络流图G = (V, E, C, W)，每条弧对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足:
(a) 流量V(f)最大。
(b) 满足a的前提下，流的费用Cost(f) = 最小。
就称f是网络流图G的最小费用最大流。
2.算法设计
我们模仿求最大流的算法，找可改进路来求最小费用最大流。
设P是流f的可改进路，定义为P的费用(为什么如此定义?) 。如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。
求最小费用最大流的基本思想是贪心法。即:对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。
算法可描述为:
step 1. 令f为零流。
step 2. 若无可改进路，转step 5;否则找到最小费用可改进路，设为P 。
step 3. 根据P求delta(改进量) 。
step 4. 放大f 。转step 2 。
step 5. 算法结束。此时的f即最小费用最大流。