网络流中的最大流最小割定理(最大流量=最小割容量)证明

/ 0评 /

之前已经介绍过,网络流中最大流就是满足网络流的三个限制前提下,源点到汇点的最大流量,可以用 Edmonds-Karp 算法或者 Dinic 算法求解。
网络流的一个割,定义为对所有点集的一个二划分(就是划分为两个点集),使得源点和汇点处于不同的点集中。假设源点 s 在点集 S 中,汇点 t 在点集 T 中,割集就是这两个点集中的点分别连的边,也就是 (u,v),u\in S,v \in T。最小割就是使割集内边权和最小的割集。
下面我们要证明一个结论:网络流的最小割容量=最大流量。

回顾网络流

一些定义

……我们先来复习一下网络流的一些定义……
以下均来自网络流最大流算法总结(Edmonds-Karp 算法+Dinic 算法)一文。

基本性质

网络流任何时刻总满足以下三条性质:

1. 容量限制(Capacity Constraints)f(u,v)≤c(u,v),即一条边的流不能超过它的容量。(不然水管就要被挤爆了……)
2. 斜对称(Skew Symmetry)f(u,v)=-f(v,u),即由 uv 的净流必须是由 vu 的净流的相反。假设有 x 的流量从 u 流到 v,那么就相当于有 -x 的流量从 v 流到 u
3. 流守恒(Flow Conservation):对于除了源点 s 和汇点 t 以外的所有点,都满足:

\displaystyle \sum_{p\in G} f(p,u)= \sum_{q\in G} f(u,q)

也就是说任何一个点的入流等于其出流,源点和汇点除外。

又一些定义

前文说了

定理概述

这是一条非常重要的定理:

最大流最小割定理(Maximum Flow, Minimum Cut Theorem):网络的最大流等于最小割。
The maximum flow between vertices v_i and v_j in a graph G is exactly the weight of the smallest set of edges to disconnect G with v_i and v_j in different components.

证明

证明要分为三部分。

任意一个流都小于等于任意一个割

说得正经一点:

如果 f 是网络中的一个流,CUT(S,T) 是一个割,那么 f 的值不超过割 CUT(S,T) 的容量。

这个其实很好理解,yy一下就好了……我们要砍掉这个割集里所有的边,代价是边集里所有边的容量之和(也就是前文所述的“边权之和”);而原来通过这些边的流量之和一定小于等于容量之和,而这个流又一定小于等于这些流量之和。所以任意一个流小于等于任意一个割。

最大流小于等于任何割

根据前面“任意一个流都小于等于任意一个割”不难得出。

最小割 = 最大流

根据刚才的两个结论其实足够得出了:

令割 CUT(S,T) 的容量为 c,流 f 的流量也为 c
假设另外的任意流 f_1,流量为 c_1,根据流量不超过割的容量,则 c_1\leqslant c,所以 f 是最大流。
假设另外的任意割 CUT(S_1,T_1),容量为 c_1,根据流量不超过割的容量,所以有 c\leqslant c_1 ,故 CUT(S,T) 是最小割。

证完了。

参考

网络流:最大流,最小割 基本概念及算法 - CSDN博客
Community - Data Science - Data Science Tutorials - A New Approach to the Maximum Flow Problem
最大流最小割定理_百度百科
最大流最小割定理 - 维基百科,自由的百科全书


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/maximum-flow-minimum-cut-theorem/


发表评论

电子邮件地址不会被公开。 必填项已用*标注