我最近对图论感兴趣。我遇到了有向图的 st 切割。我在网上了解到最小割等于最大流量，并且有标准算法可以解决有向图的最小割。
但是我似乎找不到太多关于无向图的 st 割的材料，我看到有人提到我可以用两个相反方向的有向边替换一个无向边，以将无向图转换为有向图。但是，当我找到新的有向图的最大流或最小割时，为什么它与原始无向图有任何关系？我想新的有向图的最小切割通常应该只包含uv和vu边之一，但不能同时包含两者。
我只是看不出转换后的有向图与原始无向图有什么关系。
问问题
1255 次
1 回答
1
在最大流/最小切问题中，实际上你不可能有无向图的想法。该图可能没有沿边的方向。s但是，无论如何，您都需要从to获取流t，当您找到它时，您最终会得到一个有向图（从 s -> t 的流路径/增强路径）？
我希望您已经知道使用Ford-Fulkerson 算法解决最大流量问题的想法。即使您有一个无向图，您仍然可以从该路径中找到一条路径s -> t并沿着该路径流动。每当您在路径中添加一些流时，都需要在更新的残差图中添加具有相同流的后向边。
如果您不了解 Ford-Fulkerson 算法，我强烈建议您观看上面链接的视频。这真的很有趣。
s如果你在图中找到从到的最大流t，那么你可以很容易地找到最小切。Min-cut 不采用后向边缘。因此，如果您在残差图中同时具有uv和vu边，则只会uv在最小切割中考虑（假设uv在 的方向上s-t）。
希望有帮助！
于 2019-03-13T16:10:49.760 回答