graph - 将连通图拆分为两个组件的算法

Question

假设给定一个加权的连通图。我想找到一个可以从图中删除的边列表，将其分成两个组件，以便删除边的权重总和很小。理想情况下，我希望得到最小的总和，但我会接受一个合理的近似值。

这似乎是一个难题。有没有什么好的算法可以做到这一点？

如果有帮助，在我的情况下，节点数约为 50，并且图形可能很密集，因此大多数节点对之间都会有一条边。

Answer 1

我认为您正在寻找最小切割算法。维基百科

在 Edmunds-Karp 算法之前出现了Ford-Fulkerson 算法。值得一提的是，算法书 [Cormen, Rivest] 在图论一章中引用了这两种算法。

Answer 2

我相信您正在寻找的是一种用于计算最小切割的算法。Edmonds-Karp 算法对流网络（具有源和汇顶点）执行此操作。Hao 和 Orlin (1994)将其推广到有向加权图。他们的算法在 O( nm lg( n ^2/ m )) 中运行n个顶点和m个边。切库里等人。(1997)从经验上比较了几种算法，其中一些算法的大 O 比 Hao 和 Orlin 更好。

Answer 3

我的想法可能有误，但Ford Fulkerson算法没有找到解决这个问题的方法，因为 Ford Fulkerson 假设存在源节​​点和目标节点，并且尝试将材料从源传输到目标。因此，该算法无法计算所有可能的最小切割。