graph - 图中的割集

Question

我对网络中的最大流量有疑问。我试图在图表中找到一个可以断开源和目标的割集。我探索了图中从源到目的地的所有边缘独立路径。接下来，我从这些路径中的每一个中挑选一个边缘并将它们组合在一起。所以基本上我列举了从每条路径中获取一条边的所有可能组合。所以我有一组这样的组。这是否意味着我最终找到了该特定源和目标的网络切割集？这是一种有效的方法吗？

Answer 1

这听起来像是指数级的复杂性。我不能确切地说，因为我不知道“所有边缘独立路径”是什么意思。例如：

   A
   |
   B
  / \
 C   D
  \ /
   E

从 A 到 E 有两条路径，但它们不是边缘独立的。

图上的最大流与最小割是对偶的，并且有很多标准算法可以在（小）多项式时间内找到一个。如果您对任何切割都满意，只需删除所有边缘 - 这会在 O(E) 时间内运行。

你的限制是什么？