假设我有一个带权重的连通图。我想找到一组边，从图中删除这些边可以将其分为两个部分，并且所删除的边的权重之和很小。理想情况下，我想要最小的权重和，但是对于合理的近似值我也会满足。
这似乎是一个难题。是否有任何好的算法可以解决这个问题？
如果有帮助的话，在我的情况下，节点数量大约为50个，图可能很密集，因此大多数节点对之间将有一条边连接。
这似乎是一个难题。是否有任何好的算法可以解决这个问题？
如果有帮助的话，在我的情况下，节点数量大约为50个，图可能很密集，因此大多数节点对之间将有一条边连接。
3个回答
3
我认为您正在寻找一种最小割算法。维基百科
在Edmunds-Karp算法之前，有Ford-Fulkerson算法。就算价值而言，算法书[Cormen, Rivest]在图论章节中引用了这两个算法。
- Steve Tjoa
2
我相信你正在寻找的是计算最小割的算法。Edmonds-Karp算法可以用于流网络（具有源和汇点）。Hao和Orlin（1994）将其推广到了有向加权图。他们的算法运行时间为O（nm lg（n ^ 2 / m）），其中n表示顶点数，m表示边数。Chekuri等人（1997）在实证比较中比较了几种算法，其中一些的大O复杂度优于Hao和Orlin算法。
- Fred Foo
0
我的想法可能是错误的，但是Ford Fulkerson算法不能解决这个问题，因为Ford Fulkerson假设存在源节点和汇节点，并尝试将材料从源传输到汇。因此，该算法无法计算所有可能的最小割。
- Goktug
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接