科普: 什么是最小割

图解最小割

先说明, 最大流的最大, 说的是流的最大; 最小割的最小, 说的是容量的最小.

图解最大割

如图是最小割, 由于这个是无向无权图, 所以这个图的最小割是2.

这个图的最大割如下图, 是5.

Q&A

Q: 为什么一般ACM-ICPC不研究最大割问题?
A: 最大割问题是一个计算难题, 是Karp的21道NP完全问题之一, 同时他还是APX难的问题. 最大割和最小割并不是一对对称的问题. 最小割和最大流才是一对对称问题. ICPC一般不讨论NP完全的问题, 即使讨论也是在很小的数据量下面用暴力的方法解决(例如状压DP解决旅行商问题).

Q: 如何凭直觉解释最大流等于最小割?
A: 1.最大流不可能大于最小割, 因为最大流所有的水流都一定经过最小割那些割边, 流过的水流怎么可能比水管容量还大呢? 2.最大流不可能小于最小割, 如果小, 那么说明水管容量没有物尽其用, 可以继续加大水流.

Q: 如何严谨证明最大流等于最小割?
A: 1. 证明任意的s-t流量小于s-t割容量, 证明方法: 根据定义即可; 2. 根据Ford-Fulkerson算法求出的流来选出一个s-t割, S为残余网络中s可达的顶点集合, 这样就可以证出算法求出的流 = 这个割的容量, 再根据已经证明的1来得出算法求出的流是最大流, 对应的割是最小割.