最大流问题

源自优酷视频最大流问题的记录。

最大流问题

图中括号外的数字代表允许容量,括号内的数字代表了实际流量。
解法步骤:
(1)在已知可行流基础上,通过标号寻找增广链。
正向寻找非饱和弧,若无正向,寻找反向非0弧。
最大流问题

(2)修改增广链上的流量,非增广链的流量不变,得到新的可行流。(调整量取最小值)
上图中看到调整量 [6,2,2]中最小的是2。
(3)调整后,擦除原标记,重新搜寻增广链。
最大流问题
(4)重新搜寻增广链。
最大流问题

调整量[4,1,1,1]最小是1,所以调整后得到
最大流问题

(5)之后不断寻找后,直到无法标号,即不存在增广链,此可行流就为最大流,此处为14。
最大流问题

从s开始还能往下寻找非饱和的节点,归为和s一个集合。

看另一个例题:

最大流问题

寻找增广链,即不断寻找正向(流出)非饱和边,如果没有的话看是否有逆向(流进)非0边。
逆向边修改流量的时候减少之。

最大流问题

v1到v5这个逆向边最多减少3个单位流量。
修改后:
最大流问题
继续寻找增广链:
最大流问题

最大流 W = 5 + 4 + 2 = 11
最小割集 {(Vs, V1), (Vs, V2), (Vs, V6)}