k_连通分量#

k_components(G, flow_func=None)[source]#

返回图 G 的 k-连通分量结构。

一个 k-连通分量是图 G 的一个极大子图，它至少具有节点连通度 k：我们需要移除至少 k 个节点才能将其分解为更多分量。k-连通分量具有固有的层次结构，因为它们在连通性方面是嵌套的：一个连通图可以包含多个 2-连通分量，每个 2-连通分量又可以包含一个或多个 3-连通分量，依此类推。

参数:
GNetworkX 图
flow_func函数

用于执行底层流计算的函数。默认值为 edmonds_karp()。此函数在具有右尾度分布的稀疏图中表现更好。shortest_augmenting_path() 在密度更大的图中表现更好。

返回:
k_components字典

一个字典，其键是输入图中所有的连通级别 k，其值是形成级别 k 的 k-连通分量的节点集合列表。

引发:
NetworkXNotImplemented

如果输入图是有向图。

另请参阅

node_connectivity
all_node_cuts
biconnected_components

此函数在 k=2 时的特例

k_edge_components

类似于此函数，但使用边连通度而不是节点连通度

注意

Moody 和 White [1] (附录 A) 提供了一种识别图中 k-连通分量的算法，该算法基于 Kanevsky 的算法 [2]，用于查找图的所有最小节点割集（实现在 all_node_cuts() 函数中）

  1. 计算输入图 G 的节点连通度 k。

  2. 使用 Kanevsky 算法识别当前连通度级别的所有 k-割集。

  3. 根据移除这些割集生成新的图分量。割集中的节点属于生成的割的两侧。

  4. 如果图既不是完全图也不是平凡图，则返回步骤 1；否则结束。

此实现还使用了一些启发式方法（详见 [3]）来加快计算速度。

参考文献

[1]

Moody, J. and D. White (2003). Social cohesion and embeddedness: A hierarchical conception of social groups. American Sociological Review 68(1), 103–28. http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf

[2]

Kanevsky, A. (1993). Finding all minimum-size separating vertex sets in a graph. Networks 23(6), 533–541. http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract

[3]

Torrents, J. and F. Ferraro (2015). Structural Cohesion: Visualization and Heuristics for Fast Computation. https://arxiv.org/pdf/1503.04476v1

示例

>>> # Petersen graph has 10 nodes and it is triconnected, thus all
>>> # nodes are in a single component on all three connectivity levels
>>> G = nx.petersen_graph()
>>> k_components = nx.k_components(G)
在此页上