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

这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。
若有向图G=(V,E)满足下列条件:
1、有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。
2、有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。
3、每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。
则称之为网络流图，记为G = (V, E, C)
譬如图5-1就是一个网络流图。
1.可行流
对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
1、每一条弧(i,j)有fij≤cij 。
2、除源点S和汇点T以外的所有的点vi，恒有:
该等式说明中间点vi的流量守恒，输入与输出量相等。
3、对于源点S和汇点T有:
这里V(f)表示该可行流f的流量。
例如对图5-1而言，它的一个可行流如下:
流量V(f) = 5 。
2.可改进路
给定一个可行流f= 。若fij = cij，称为饱和弧;否则称为非饱和弧。若fij = 0，称为零流弧;否则称为非零流弧。
定义一条道路P，起点是S、终点是T 。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+;把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P- 。
譬如在图5-1中，P = (S, V1, V2, V3, V4, T)，那么
P+ = {, , , }
P- = {}
给定一个可行流f，P是从S到T的一条道路，如果满足:
那么就称P是f的一条可改进路。(有些书上又称:可增广轨)之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。具体方法下一节会重点介绍，此不赘述。
3.割切
要解决网络最大流问题，必须先学习割切的概念和有关知识。
G = (V, E, C)是已知的网络流图，设U是V的一个子集，W = V\U，满足S U，T W 。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。
对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用(U，W)表示。把割切(U，W)中所有弧的容量之和叫做此割切的容量，记为C(U，W)，即:
例如图5-1中，令U = {S, V1}，则W = {V2, V3, V4, T}，那么
C(U, W) =+ + +=8+4+4+1=17
定理:对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有:V(f) ≤ C(U, W) 。
【最小截集什么意思,网络流的资料】通俗简明的讲:“最大流小于等于最小割” 。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。
下面我们给出证明。
网络流、可改进路、割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。
二、求最大流
何谓最大流?首先它必须是一个可行流;其次，它的流量必须达到最大。这样的流就称为最大流。譬如对图5-1而言，它的最大流如下:
下面探讨如何求得最大流。
在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则” 。
对可改进路P上的弧，分为两种情况讨论:
第一种情况:∈P+，可以令fij增加一个常数delta 。必须满足fij + delta ≤ cij，即delta ≤ cij – fij 。
第二种情况:∈P-，可以令fij减少一个常数delta 。必须满足fij - delta ≥ 0，即delta ≤ fij