nx.node_connectivity 和 nx.minimum_node_cut 不匹配

Question

这个returns1:

nx.node_connectivity(G_sc,97,38)

但是， nx.minimum_node_cut(G_sc, 97, 38) returns 一个空列表。为什么？

Answer 1

通过检查示例图，可能的解释可能如下所示。举个例子：

G = nx.from_edgelist([[1,4], [1,3], [4,3], [4,5], [1,2], [2,5]])
nx.draw(G, with_labels=True, node_color='lightgreen')

如果我们假设，节点 3 和 5:

nx.node_connectivity(G,3,5) 
# 2
nx.minimum_node_cut(G, 3,5)
# {2, 4}

一切似乎都符合预期，因为正如 nx.minimum_node_cut 中的文档中所述，这是一组断开连接 G.

的最小基数节点

虽然如果我们尝试 4 和 5 例如：

nx.node_connectivity(G,4,5) 
# 2
nx.minimum_node_cut(G, 4,5)
#{}

由于 nx.minimum_node_cut，我们得到一个空的 set，尽管很明显我们需要删除两条路径来断开它们，正如 nx.node_connectivity 所指定的.

的解释似乎是在nx.minimum_node_cut中指定的source和target节点相邻的情况下，返回的子集不考虑任何其他路径，因为解决方案排除了删除连接两个相邻节点的边缘的简单答案。所以这很可能就是您的实际情况。

nx.node_connectivity and nx.minimum_node_cut arent' matching up