0 值流，至少有 1 个边，流量大于 0，瓶颈边的最小子集

Question

我需要解决以下流量网络问题

1. 编写一个采用流网络 G 的高效算法 判断是否存在有效的0值s-t流 网络中至少有 1 个边且流量大于 0

2. 编写一个接受流网络 G 和最大流函数 f 的算法 并返回瓶颈边的最小集合，即当我们增加其容量时的边 它增加了最大流量值

对于第一个问题，我最初想到的是在图中找到流永远不会离开它们的流循环，因此会有这样的流边，并且我们可以找到有效的 0 值 s-t flow

对于第二个，我唯一想到的就是检查最小切割中的边缘，生成所有边缘子集并获取最小数量的边缘子集..

两者都不够，第一个只是一个线索，我无法扩展 第二个计算量非常大，所以我想知道我是否可以做得更好

另外，如果我的直觉不正确，我很乐意指出这一点

我想说，这里现有的问题和答案都对这些问题没有帮助，所以我发表了这篇文章。

Answer 1

查找网络流量的标准算法如下：

• 使用深度优先搜索查找从源到目的地的路径
• 找到路径上任意链路的最小容量
• 将路径上所有链路的容量减少最小容量
• 删除现在容量为零的所有边
• 重复上述步骤，直到找不到更多路径。

“瓶颈边的最小集合”

剩余产能为零的边缘是瓶颈。