找到节点的最小代价集，这样一旦移除，图就断开连接

Question

如果有人能帮我就太好了。你知道吗

我有一个无向图，其中每个顶点都有权，没有边有权。我想找到一组总权重最小的节点，移除这些节点会使图断开连接。例如，在移除一个权重为10的节点（使图形断开）和移除两个总权重为6的节点（使图形断开）之间，结果集应该包含这两个节点。你知道吗

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

这是我到目前为止所做的。我已经使用networkx（python）编写了代码。我已经把我的图表改成定向图了。例如，对于节点1，我考虑1入和1出节点。我用节点1的重量连接1进1出。我还添加了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)

谢谢