java - 删除最小边数以断开图中的两个顶点

Question

在这里，我试图断开图中的两个顶点，尽可能减少边缘移除。

在这个位于两个顶点 A 和 Z 之间的图中，您可以通过多种方式找到答案。以最佳方式，您可以只删除从 A 到 B 的一条边。

有没有具体的算法呢？

我发现了一些通过使用最大流最小切割问题来解决这个问题的建议，但我没有得到将这个问题转换为最大流最小切割定理的一般想法。同样在这个过程中，我可能最终会删除 F 和 G 之间的边缘，这是无用的。

Answer 1

这可以使用 Max Flow - Min Cut 问题来解决。

您可以按如下方式将图形建模为网络流:
1. 将A作为源点，Z作为汇点。
2. 设置每条边的容量为1个单位。

现在，解决上述网络中的 Max Flow - Min Cut 问题。有了它，您将能够找到从 A 到 Z 的边不相交路径的数量。对于每条这样的路径，删除第一条边(源自源 A 的边)。

证明:
观察到在移除上面的边缘之后，您将无法到达 A 到 Z。如果你有一条路径，那么最大流算法会将这条路径包含在一组边不相交的路径中。
此外，通过构建网络，您无法删除较少数量的边来断开 A 与 Z

的连接