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

然后再求可改进路(反向弧必须满足fij≥Aij，而非fij≥0)，不断放大f，直到求出最大流。
我们看到，上几节所讨论的一种可行网络流实际上是{Aij = 0}的一种特殊网络流，这里提出的模型更一般化了。解决一般化的复杂问题，我们采取的思路是将其转化为特殊的简单问题，加以研究、推广，进而解决。这是一种重要的基本思想:化归--简单有效。基于这种思想，请读者自行思考解决:
1、有上下界的最小流。
2、有上下界的最小费用最大流。
五、多源点、多汇点的最大流
已知网络流图有n个源点S1、S2、……、Sn，m个汇点T1、T2、……、Tm，，求该图的最大流。这样的问题称为多源点、多汇点最大流。
它的解决很简单:
1、增设一个“超级源”S’，对每个源点Si，新增弧，容量为无穷大。
2、增设一个“超级汇”T’，对每个汇点Ti，新增弧，容量为无穷大。
3、以S’为源点、T’为汇点求最大流f 。
4、将f中的S’和T’去掉，即为原图的最大流。
算法正确性显然。
六、顶点有容量限制的最大流
上一节已经提出了这个问题，即对于进出每个顶点的流量也规定一个上限，这样的最大流如何求?
既然我们已经解决了“边限制”问题，现在何不把“点限制”问题转化为“边限制”呢?具体办法如下:
1、对除源点和汇点之外的每个顶点i拆分成两个顶点i’和i’’ 。新增一条弧，其容量为点i的流量限制。
2、对于原图中的弧，我们将其变换成。
3、对变换后的图求最大流即可。
这里我们又一次运用到了化归的思想:将未知的“点限制”问题转化为已知的“边限制”问题。
七、网络流与二部图的匹配
{二部图和匹配的定义可参见本书专门介绍二部图匹配的章节}
设二部图为G = (X, Y, E) 。
增设点S’，对于所有i∈X，新增弧，容量为1;增设点T’，对于所有i∈Y，新增一条弧，容量也为1 。原图中所有的弧予以保留，容量均为+∞ 。对新构造出来的网络流图以S’为源点、T’为汇点求最大流:流量即为最大匹配数;若弧(i∈X，j∈Y)的流量非零，它就是一条匹配边。
二部图最大匹配问题解决。
那么二部图的最佳匹配问题又如何?
仍然按照上述方法构图。同时令原图中弧的费用保持不变;新增弧的费用置为0 。然后以S’为源点、T’为汇点求最小费用最大流即可。最大流的费用即为原二部图最佳匹配的费用。
复制的我快吐了~