networkx minimum_node_cut和node_connectivity [英] networkx minimum_node_cut and node_connectivity

问题描述

我正在使用networkx，这是我的网络.

I am using networkx and here is my network.

import networkx as nx
G = nx.from_edgelist([['a','b'], ['b','c'], ['c','a']])
nx.draw_networkx(G)

您能告诉我为什么minimum_node_cut返回b，而node_connectivity返回2吗?

Can you please tell me why minimum_node_cut returns b, whereas node_connectivity returns 2?

nx.minimum_node_cut(G, 'a', 'c')
{'b'}

nx.node_connectivity(G, 'a', 'c')
2

我期望minimum_node_cut的长度等于node_connectivity.

推荐答案

来自文档:

networkx.minimum_node_cut-如果提供了源节点和目标节点，则此函数返回最小基数的节点集，如果删除该节点，将破坏G中源和目标之间的所有路径.

networkx.minimum_node_cut - If source and target nodes are provided, this function returns the set of nodes of minimum cardinality that, if removed, would destroy all paths among source and target in G.

networkx.node_connectivity-如果提供了源节点和目标节点，此函数将返回本地节点连接性:必须断开以断开G中从源到目标的所有路径的最小节点数.

networkx.node_connectivity - If source and target nodes are provided, this function returns the local node connectivity: the minimum number of nodes that must be removed to break all paths from source to target in G.

第一个返回一组节点，这些节点在删除后会破坏本地连接，第二个返回需要删除以破坏本地连接的最少节点数.

The first returns a set of nodes that when removed will break local connectivity, the second returns the minimum number of nodes needed to be removed to break local connectivity.

在我看来，由networkx.minimum_node_cut返回的集合排除了源节点和目标节点，因为删除其中任何一个都会轻易破坏它们之间的连接性. networkx.node_connectivity正确地报告必须删除2个节点才能中断本地连接.

It seems to me that the set returned by networkx.minimum_node_cut excludes the source and target nodes as the removal of either would trivially break connectivity between them. networkx.node_connectivity rightfully reports that 2 nodes must be removed to break local connectivity.

这篇关于networkx minimum_node_cut和node_connectivity的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！