边连接度#

edge_connectivity(G, s=None, t=None, flow_func=None, cutoff=None)[source]#

返回图或有向图 G 的边连接度。

边连接度等于断开 G 或使其成为平凡图所需移除的最小边数。如果提供了源节点和目标节点，此函数将返回局部边连接度：断开 G 中所有从源到目标的路径所需移除的最小边数。

参数:

GNetworkX 图: 无向图或有向图
s节点: 源节点。可选。默认值：None。
t节点: 目标节点。可选。默认值：None。
flow_func函数: 一个用于计算一对节点间最大流的函数。该函数必须接受至少三个参数：一个有向图、一个源节点和一个目标节点，并返回一个遵循 NetworkX 惯例的残差网络（详见 maximum_flow()）。如果 flow_func 为 None，则使用默认的最大流函数（edmonds_karp()）。详情请参见下文。默认函数的选择可能会因版本而异，不应依赖。默认值：None。
cutoff整数, 浮点数, 或 None (默认值: None): 如果指定，当流值达到或超过截止值时，最大流算法将终止。这仅适用于支持 cutoff 参数（大多数都支持）的流算法，否则将被忽略。

返回:

K整数: G 的边连接度，如果提供了源和目标，则为局部边连接度

另请参阅

local_edge_connectivity()
local_node_connectivity()
node_connectivity()
maximum_flow()
edmonds_karp()
preflow_push()
shortest_augmenting_path()
k_edge_components()
k_edge_subgraphs()

注释

这是全局边连接度的基于流的实现。对于无向图，该算法通过寻找 G 的一个‘小’支配集节点（参见 [1] 中的算法 7），并计算支配集中任意一个节点与其中其余节点之间的局部最大流（参见 local_edge_connectivity()）来工作。这是 [1] 中算法 6 的实现。对于有向图，该算法对最大流函数进行 n 次调用。这是 [1] 中算法 8 的实现。

参考文献

[1] (1,2,3)

Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

示例

>>> # Platonic icosahedral graph is 5-edge-connected
>>> G = nx.icosahedral_graph()
>>> nx.edge_connectivity(G)
5

您可以使用替代的流算法来进行底层最大流计算。在稠密网络中，shortest_augmenting_path() 算法通常会比默认的 edmonds_karp() 表现更好，后者对于具有高度偏斜度分布的稀疏网络更快。必须从 flow 包中显式导入替代的流函数。

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> nx.edge_connectivity(G, flow_func=shortest_augmenting_path)
5

如果将一对节点（源和目标）指定为参数，此函数将返回局部边连接度值。

>>> nx.edge_connectivity(G, 3, 7)
5

如果需要在同一图上针对不同的节点对执行多次局部计算，建议您重用最大流计算中使用的数据结构。详见 local_edge_connectivity()。