连接性

连接性和割算法

边增强

寻找 k-边增强的算法

k-边增强是一组边，添加到图后，能确保图是 k-边连通的；即除非移除 k 条或更多边，否则图不会断开。通常，目标是找到权重最小的增强。一般而言，不能保证 k-边增强总是存在。

另请参阅

edge_kcomponents：寻找 k-边连通分量的算法 connectivity：确定边连通性的算法。

k_edge_augmentation(G, k[, avail, weight, ...])	找到使 G 达到 k-边连通的边集。
is_k_edge_connected(G, k)	测试图是否为 k-边连通。
is_locally_k_edge_connected(G, s, t, k)	测试图中的边是否为局部 k-边连通。

K-边分量

寻找 k-边连通分量和子图的算法。

k-边连通分量（k-edge-cc）是 G 中节点的最大集合，其中所有节点对的边连通度至少为 k。

k-边连通子图（k-edge-subgraph）是 G 中节点的最大集合，其中由这些节点定义的 G 的子图的边连通度至少为 k。

k_edge_components(G, k)	生成 G 中每个最大 k-边连通分量中的节点。
k_edge_subgraphs(G, k)	生成 G 中每个最大 k-边连通子图中的节点。
bridge_components(G)	找到 G 中所有桥连通分量。
边分量辅助图()	一种寻找图中所有 k-边连通分量的简单算法。

K-节点分量

Moody 和 White 的 k-分量算法

k_components(G[, flow_func])

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

K-节点割集

Kanevsky 的所有最小节点 k 割集算法。

all_node_cuts(G[, k, flow_func])

返回无向图 G 的所有最小 k 割集。

基于流的不相交路径

基于流的节点和边不相交路径。

edge_disjoint_paths(G, s, t[, flow_func, ...])	返回源节点和目标节点之间的边不相交路径。
node_disjoint_paths(G, s, t[, flow_func, ...])	计算源节点和目标节点之间的节点不相交路径。

基于流的连接性

基于流的连接性算法

average_node_connectivity(G[, flow_func])	返回图 G 的平均节点连接度。
all_pairs_node_connectivity(G[, nbunch, ...])	计算图 G 中所有节点对之间的节点连接度。
edge_connectivity(G[, s, t, flow_func, cutoff])	返回图或有向图 G 的边连接度。
local_edge_connectivity(G, s, t[, ...])	返回图 G 中节点 s 和 t 之间的局部边连接度。
local_node_connectivity(G, s, t[, ...])	计算节点 s 和 t 之间的局部节点连接度。
node_connectivity(G[, s, t, flow_func])	返回图或有向图 G 的节点连接度。

基于流的最小割

基于流的割算法

minimum_edge_cut(G[, s, t, flow_func])	返回使 G 断开的最小基数边集。
minimum_node_cut(G[, s, t, flow_func])	返回使 G 断开的最小基数节点集。
minimum_st_edge_cut(G, s, t[, flow_func, ...])	返回最小 (s, t)-割的割集中的边。
minimum_st_node_cut(G, s, t[, flow_func, ...])	返回在 G 中使源节点与目标节点断开的最小基数节点集。

Stoer-Wagner 最小割

Stoer-Wagner 最小割算法。

stoer_wagner(G[, weight, heap])

使用 Stoer-Wagner 算法返回加权最小边割。

基于流的连接性工具函数

连接性包的工具函数

build_auxiliary_edge_connectivity(G)	用于计算基于流的边连接度的辅助有向图
build_auxiliary_node_connectivity(G)	从无向图 G 创建有向图 D 以计算基于流的节点连接度。