可行割边与关键割边

kgxw0430 2019-03-23 原文

引入

我们当前有一个张网络流图$G = (V, E)$，这个图中存在关键割边与可行割边。

关键割边：在任意一个最小割集中总是存在的边。
可行割边：存在一个最小割集使得这条边属于这个割集。

可行割边的判定
首先我们要注意到，不管一条是可行割边还是关键割边，其在残余网络上都应该是只存在反向弧，即满流。如果一条割边$(u, v)$ 是可行割边，那么就意为着如果我们给原图加边 $S→ u（inf）$, $v→ T（inf）$，是不会对图的最小割的大小造成任何影响，我们只需要构造出那个这条边输出最小割的割集即可。
显然我们不可能每次都给原图加两条边再跑一遍网络流，我们考虑如何快速的判定。如果上述是不成立的，即加边后最小割的大小发生了改变，那么一定意味着在残余网络上还存在一条从$u$到 $v$ 的增广路，使得最小割也就是最大流得以扩充。
换句话说，我们只需要判定在残余网络上是否存在一条从 $u$ 到 $v$ 的路径即可，我们知道残余网络上一定存在 $v$ 到 $u$ 的路径，也就是如果存在，那么 $u, v$ 一定位于同一个强联通分量中。
所以，我们只需要在残余网络上求一遍强连通分量即可。如果一条边的两个点在原网络流图上满流同时不属于一个强连通分量，那么这条边就是一条可行割边。

关键割边的判定
了解了可行割边的判定，那么关键割边的判定就是相对容易的。
考虑我们在计算最小割时，虽然理论上是把原图的点分为了 $S$ 与 $T$ 两个集合。但是事实上如果我们在残余网络上分别从 $S,T$ 进行 $BFS$，会发现其并无法覆盖到所有的点。其原因也是显然的，我们考虑这样一张简单的图：
在实际运算时这张图我们计算的最小割是 1，红色边都会满流。图中的点集实际被划分为了 $S,T,$ {1, 2, 3}。
我们可以断言，对于我们实际的残留网络来说，如果一条满流边的两个端点分别处在 $S,T$ 集，那么这条割边就是关键割边。我们还可以发现，假设一个点位于 $S$ 集，那么必定在残余网络上存在一条从 $S$ 到这个点的路径。同时因为他所连的边被割，那么在参与网络上也必定存在一条从该点到 $S$ 的路径，也就是说这个点属于 $S$ 所属于的那个强连通分量，$T$ 集也是同理。也就是说，如果一条边是关键割边，当且仅当这条边满流，同时在残余网络上分别属于 $S,T$ 集所在的强联通分量。