删除最少的边数以断开图中的两个顶点
在这里，我试图断开图中最小边移除的两个顶点。
在这两个顶点A和Z之间的图中，您可以通过多种方式找到答案。 以最佳方式，您可以只从A到B移除一个边缘。
如果有什么具体的算法呢？
我发现了一些建议，通过使用最大流最小切割问题来解决这个问题，但是我没有得到将这个问题转换成最大流最小割定理的一般想法。 同样在这个过程中，我最终可能会删除F和G之间无用的边。
这可以使用Max Flow - Min Cut问题来解决。
您可以按如下方式将您的图形建模成网络流：
1.考虑A是源顶点， Z是sink顶点。
2.将每个边的容量设置为1个单位。
现在，解决上述网络中的Max Flow - Min Cut问题。 有了它，您将能够找到从A到Z的边数不相交的路径。 对于每个这样的路径，删除第一个边缘（源于源A边缘）。
证明 ：
观察到除去上面的边缘后，你将无法达到A到Z 如果你有一条路径，那么最大流算法会将这条路径包含在一组边缘不相交路径中。
另外，通过构建网络，您不能删除较少数量的边缘以将A与Z断开连接
上一篇: Removing minimum no of edges to disconnect two vertices in a graph
下一篇: An algorithm to draw graphs without checking all pairs of vertices?