如何在O(V+E)时间复杂度下查找流网络中的瓶颈边？

嘿，先明确一下：我已经看过《在图中查找‘瓶颈边’》的内容，咱们这个问题和它不是一回事——之前那个提问者明显把最小割和瓶颈边搞混了，我来帮你把这俩概念掰扯清楚：

定义上的本质区别 #

• 瓶颈边：流网络中的一类边，核心特征是只要提升这条边的容量，整个网络的最大流就会随之增加。它是当前限制最大流提升的关键单条边，但它未必属于最小割的边集合。
• 最小割：根据最大流最小割定理，它是一个边的集合，这个集合的容量等于网络的最大流——切断这些边就能把源点和汇点分开，它的容量是限制最大流的整体上限。

举个反例帮你理解 #

拿这个简单的流网络举例：o-1->o-1->o（两条单向边的容量均为1，从左到右依次连接）

• 这个网络的最大流是1，最小割可以任选其中一条边（割的容量都是1）；
• 但你尝试单独提升任意一条边的容量：比如把第一条边容量改成2，最大流还是1（第二条边的容量1依然卡着）；把第二条边容量改成2，最大流还是1（第一条边的容量1限制着）。所以这个网络里不存在瓶颈边——没有任何一条边，单独提升它的容量就能让最大流变大。

一句话总结 #

最小割是限制最大流的“整体瓶颈”，而瓶颈边是能直接突破最大流的“单个关键边”，二者不能划等号。

内容的提问来源于stack exchange，提问作者nedlaback