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

Question

在这里，我试图以最小的边缘去除来断开图中的两个顶点。

在此图形中，在两个顶点A和Z之间，您可以找到很多答案。以最佳方式，您可以从A到B仅移除一条边。

是否有针对此的特定算法？

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

Answer 1

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

您可以将图形建模为网络流，如下所示：
1. 考虑A是源顶点，Z是汇顶点。
2. 设置每条边的容量为1个单位。

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

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