聊聊最大流与最小割定理的简单理解

浅谈最大流最小割定理

本篇随笔简单讲解一下网络流中的最大流最小割定理。

---

一、前置知识

​

关于割的定义

肖战割割

割顾名思义就是分割。将源点和汇点分割开。具体地，就是选取一些边删除，把源点和汇点分割到不同的两个点集。其大小等于边的容量和。那么最小割就是最小的割...

---

二、定理内容

就一句话：

最大流等于最小割。

最大流为什么会等于最小割呢？

证明用个反证法：

假设最小割对应的流为f，其流量等于最小割，若f不是最大流，则一定能找到不属于f的边，使其能构成新的连通路径到达t，才能增加流量值。但最小割的边集合全在流f中，意味着，目前去掉最小割的边后，图已经不连通，则添加非最小割边不能改变图的连通性，即目前已经无法增加流量。所以最小割对应的流的流量已经达到最大，即最大流。