maxFlowMinCut && 最大流最小割求法

Posted on Edited on

1 最大流-最小割本身含义

首先 起始点 s, 终止点 t, 从s->t的所有通路中，能够流过来的最大流量就是最大流，这里举个例子：
比如有如下的图：
1 -> 2 管道是5的容量，
2 -> 4 管道是4的容量，
1 -> 3 管道是3的容量，
3 -> 4 管道是6的容量，
那么从1->4的最大流，就是4 + 3 = 7

最小割：
最小割是指，从图中移除一些边的集合以达到隔断从s到t的目的，成为一个图割，然后最小割，就是所有图割中，边权(管道的流量)之和最小的一个图割，最小割的值和最大流的值是相等的

2 最大流最小割算法

MinCutMaximumFlowAlgorithm

其过程就是：

  • 1 对于G中的每一个顶点，先将f(u, v)和f(v, u)都置为0
  • 2 当存在从s->t的一条路径(这样的一条路径称之为增广路径):
    • 2.1 找出这个路径上的最小边权，称为tmpC
    • 2.2 对增广路径上的每一条边，都做: f(u, v) += tmpC, f(v, u) = -f(u, v)
  • 3 G中的更改过后的图，称之为残余图(residual graph)
    上面过程的tmpC之和就是最大流的值

3 例子

引用自: https://www.baeldung.com/cs/minimum-cut-graphs
minCutEg

在上述例子里的残余图中：
可以看出： 最大流为: 4 + 4 + 3 + 2 = 13

4 最小割

在上述例子里的残余图中：
首先按照从s能够到达的点和不能到达的点分成2个集合set1(reaching by s)和set2(not reaching by s)，这两个set在残余图中的连线构成的那些边成为最小割

那么set1是： (a, b, c, e)
set2是：(d, f)]
残余图中，set1和set2相关连的边为： b->d, c->f, e->f,最小割值为： 4 + 3 + 6 = 13