1

如果有人可以帮助我，那就太好了。

我有一个无向图，其中每个顶点都有权重，而没有边有权重。我想找到一组总权重最小的节点，它们的删除会使图表断开连接。例如，在删除一个权重为 10 的节点使图断开连接和删除总权重为 6 的 2 个节点使图断开连接之间，结果集应包含这 2 个节点。

这个问题有什么已知的算法吗？

这是我到目前为止所做的。我使用networkx（python）制作了我的代码。我已经将我的图表更改为定向。例如，对于节点 1，我考虑 1in 和 1out 节点。我通过节点 1 的权重将 1in 连接到 1out。我还添加了 s 和 t 节点（我不确定它是否正确）。我还定义了新有向图中每条边的容量。

运行代码时，我收到此错误：NetworkXUnbounded: Infinite capacity path, flow unbounded above.

deg_G = nx.degree(G)
max_weight = max([deg for i,deg in deg_G])+1

st_Weighted_Complement_G = nx.DiGraph()
r = np.arange(len(Complement_G.nodes))

nodes = ['s','t']
edges = []
for i in r:
    nIn = (str(i)+'in')
    nOut = (str(i)+'out')
    nodes.extend([nIn,nOut])
    edges.extend([(nIn,nOut,{'capacity':deg_G[i],'weight':deg_G[i]}),('s',nIn,{'capacity':math.inf,'weight':0}),
                  (nOut,'t',{'capacity':math.inf,'weight':0})])

for edge in Complement_G.edges:
    print(edge[0],edge[1])
    edges.extend([((str(edge[0]))+'out',(str(edge[1]))+'in',{'capacity':max_weight,'weight':0}),
                  ((str(edge[1]))+'out',(str(edge[0]))+'in',{'capacity':max_weight,'weight':0})])

print(edges)
st_Weighted_Complement_G.add_nodes_from(nodes)
st_Weighted_Complement_G.add_weighted_edges_from(edges)

mincostFlow = nx.max_flow_min_cost(st_Weighted_Complement_G, 's', 't',capacity='capacity',weight='weight')
print(mincostFlow)

谢谢

4

0 回答 0