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