无向、加权图划分

Question

我需要以节点 X 和节点 Y 不再连接的方式对图进行分区。此外，删除边的权重之和必须尽可能低。

例如：

    3       1       2
X ----- Z ----- W ----- Y

应该变成：

    3               2
X ----- Z       W ----- Y

我一开始想到可以用一个循环来计算X和Y之间的最短路径，去掉最便宜的边，直到没有路径为止。但是，仔细想想，我发现这种方法并非适用于所有情况。

在维基百科中搜索让我找到了 Kernighan–Lin 和 Fiduccia-Mattheyses 算法，但看起来它们旨在解决其他分区问题。

有没有标准的算法可以解决这个问题？

Answer 1

您要查找的称为图的最小割。

由Max-flow_min-cut_theorem最小割的值等于最大流的值

计算网络中的最大流量是一个标准问题，根据图形的性质，有多种算法可用于计算此问题。

一个很好的教程是 here on topcoder。

这里是示例 Python 代码，使用 Networkx library:

计算图表的值

import networkx as nx
G = nx.Graph()
G.add_edge('x','z', capacity = 3)
G.add_edge('z','w', capacity = 1)
G.add_edge('w','y', capacity = 2)
print nx.minimum_cut_value(G, 'x', 'y')

无向、加权图划分

Undirected, weighted graph partitioning

language-agnostic

algorithm

graph-algorithm