在图中断开两个顶点的最小边数

Question

12

我试图在尽可能少地删除边的情况下，在图中断开两个顶点之间的连接。

在这张图中，你可以以多种方式在顶点A和Z之间找到答案。最优解是只需从A到B中删除一条边。

是否有专门的算法可解决此问题？

我发现可以通过使用最大流最小割问题来解决此问题，但我不知如何将此问题转化为最大流最小割定理的一般思路。同时，我可能会删除一个无用的F到G之间的边。

- full_stuck_developer

正如您所说，这确实是最小割：删除最少数量的边缘以分割图形。由于最小割是最大流的对偶，因此解决其中一个问题的任何算法也可以解决另一个问题。 - dhke

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rishit Sanmukhani · Accepted Answer

这个问题可以使用最大流 - 最小割算法来解决。您可以按以下方式将图形建模为网络流：
1. 将A视为源顶点，将Z视为汇顶点。
2. 将每个边的容量设置为1单位。

现在，在上述网络中解决最大流 - 最小割问题。通过它，您将能够找到从A到Z的边不相交路径的数量。对于每条这样的路径，请删除第一条边（从源A发出的边）。

证明：
观察到在删除上述边缘后，您将无法到达A到Z。如果您有一条路径，则最大流算法将包括此路径在边不相交路径集合中。
此外，通过网络的构建，您不能删除较少的边以将A与Z断开连接。