最大流最小割（maxflow-mincut）是图像分割的经典算法之一，同时也在"Graph Cut"、"Grab Cut"等算法中都有被使用过。本文记录相关算法。
上图浅蓝色线条为流水方案，路径与水量用
S->1->2->3->T:2表示，但显然这个并不是流量最大的流。
沿着增广路径增加flow。增广路径是一条从 $s$ 到 $t$ 的无向路径，但也有些条件，可以经过没有满容量的前向路径（$s$ 到 $t$）或者是不为空的反向路径( $t$ -> $s$)
核心思路在于用深度优先或广度优先搜索增广路径时提供反向流水（反悔）的可能
假设以源点s和汇点t在图结构上构造两颗没有交集的树，分别为树S和树T，如下图所示。树S中的所有边都是由父节点指向子节点（存在流量），树T中则由子节点指向父节点。不在两树中的节点为“自由”状态。搜索树S和T中的节点只有两种状态：“主动”和“被动”。主动态的节点表示搜索树的外边界节点，意思是从该节点出发还可以扩展搜索树，而被动态节点表示搜索树内部的节点，树不能由该节点向外扩展。主动态节点因为可以向外扩展，所以有可能会搜索到另一搜索树的节点，当主动节点检测到另一搜索树的节点，就找到了一条增广路径。
Yuri提出的算法主要循环以下三个步骤：
初始化
初始化时，搜索树S只有源点s为主动节点，搜索树T只有汇点t作为主动节点，增长搜索树直到它们的主动节点相遇，得到一条增广路径P。如果P为空则算法终止，反之则对P进行增广流量处理。然后对孤点进行领养处理，以此循环。
增长阶段
主动态节点搜索相邻且邻边仍有可用流量的自由节点作为搜索树新的子节点，新增长的子节点又称为该搜索树的主动态节点，搜索树继续扩展增长。当主动态节点的所有邻点都检测过，主动态节点变为被动态节点。当两颗搜索树的主动态节点搜索到对方的节点时，增长阶段终止。然后根据当前建树情况，找到一条增广路径。
增广阶段
这个阶段根据增长阶段找到的增广路径进行增广流量统计，即求出经过该路径的最大流量，意味着路径中至少有一条边达到饱和态，也就是所经流量等于该边的流量值。因此搜索树S和T中会出现一种新的节点，称为“孤点”（orphans），意思就是连接它与其父节点的边已达饱和态，没有流可以再到达这个节点。
所以在增广阶段搜索树S和T可能会拆分为多棵子树，从而形成森林。源点s和汇点t仍充当两颗子树的根节点，而孤点成为其余子树的根节点。
首先找到路径P的瓶颈值，即最小流量边，为该路径的最大流量值。流量经过后，路径P中至少有一条边变为饱和态，即所经流量等于自身流量值，该边连接的子节点变为孤点。
领养阶段
领养阶段字面上理解就能看出是针对孤点进行处理的阶段，该阶段也是为了恢复搜索树S和T的单一性，即图中除了两颗搜索树，其余节点都归为主动态、被动态和自由态，消除孤点。做法是为每个孤点找到一个新的合法父节点，该父节点原来必须与孤点属于同一搜索树，而且父节点与孤点间有一条未饱和（仍有可经流量）的边。若没有符合要求的父节点，该孤点变为自由节点。以此处理所有孤点和孤点的子节点。当所有孤点都处理后，领养阶段结束，最终只剩下原有的搜索树S和T。
最大流的求解过程就是循环重复以上三个阶段，直到搜索树S和T不能再增长。
最大流不可能大于最小割
因为最大流所有的水流都一定经过最小割那些割边，流过的水流怎么可能比水管容量还大呢？
最大流不可能小于最小割
如果小，那么说明水管容量没有物尽其用，可以继续加大水流。
flow 的和减去从 $B$ 到 $A$ 边 $flow$ 的和。
那么现在我们可以引出两个定理：
增广路径定理（Augmenting Path theorem）: 一个流 $f$ 是最大流当且仅当没有增广路径。
最小割最大流定理（Maxflow-mincut theorem）: Maxflow 的值等于最小割的容量。
要证明上面的定理，只要证明下面三个条件是等价的就可以了：
存在一个割的容量等于$flow\ f$ 的值
$f$ 是最大流
对于$f$没有增广路径
首先我们证明 1->2。假设我们有一个割 $cut(A,B)$ 的容量等于 $f$ 的值，那么利用弱对偶的关系，其他流的值<= $cut(A,B)$ 的容量，而由于 1 的假设，$cut(A,B)$ 的容量等于 $f$ 的值，因此得到其他流的值都小于 $f$ 的值，从而 2 成立
接着证明 2->3。我们来证明它的逆否命题。对于 $f$ 如果还有增广路径，那$f$不是最大流，这很显然，如果按照 Ford-Fulkerson 算法的话，我们还可以增加 flow f 的值，因此 $f$ 就不会是最大流，因此逆否命题成立，也就代表 2->3成立。
最后证明从 3->1。让割 $cut(A,B)$ 满足这么一个条件：$s$ 在 $A$ 中，且 $A$ 中的顶点通过一些无向的边连接而成，这些边要么是不是满的前向边要么是非空的反向边。如下图中加粗的边。
那么根据定义，$s$ 在 $A$ 中，由于没有增广路径，因此 $t$ 在 $B$中。
由于这个割的 $B$ 到 $A$ 的边流量全是 0
这个割的容量 = 沿着这个割的 netflow (从 $A$ 到 $B$ 边的流量 - 从 $B$ 到 $A$ 边的流量)
又根据 flow-value 引理，**net flow = value of low,**因此推出 1
根据最大流的解得到最小割的解：就是和证明
3->1中的一样让割 $cut(A,B)$ 满足这么一个条件：$s$ 在 $A$ 中，且 $A$ 中的顶点通过一些无向的边连接而成，这些边要么是不是满的前向边要么是非空的反向边
文章链接：
https://www.zywvvd.com/notes/study/algorithm/graph/max-flow-min-cut/max-flow-min-cut/
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。