graph - 在图中找到最小割，使得给定的顶点不连接

Question

前段时间我读到了通用的最小割算法，该算法将图形作为输入并删除一个最小值。边的数量，以便保留两个断开的组件。

我现在正在处理一个具有 10k+ 个节点和 500k+ 条边(两个顶点之间没有多条边)的无向图。为了对节点之间的交互进行归因，我考虑计算断开两个给定顶点(或与流相关的度量)的最小切割。

是否有有效的算法为图中的每对顶点提供一个值(最小割集的基数)？作为这个话题的新手，如果有人能提供指向论文或其他资源的链接，我将不胜感激，这些资源概述了以合理的运行时复杂性运行的算法。

谢谢!

Answer 1

有几种算法(参见 Wiki 的介绍)可以找到网络中的最大流。我知道的那些(Ford-Fulkerson、Dinic、Karp-Edmond)应该在单位容量上表现良好(=整数容量在所有边缘上等于 1)(可变容量增加了复杂性，非整数容量会出现更多问题)

对于任何一对顶点，您可以通过将 source/sink 设置为这对顶点来从图中创建网络。您可以使用其中一种算法获得最大流量，您可以使用该算法进行切割，如下所示:

选择流使用的任何边。该边缘将属于切割。

重复，但现在在没有选定边的图上进行流搜索，直到流为 0

最后，你有最小的切割，最大流量的大小。

如果你真的想强调性能，你可能想看看这篇论文: Flows in Undirected Unit Capacity Networks (1997) 作者:Andrew V. Goldberg, Satish Rao，但我可能会坚持使用更简单的。