连通性

连通性和切割算法

边缘增强

寻找k边增广的算法

k-边增广是一组边，一旦添加到图中，确保图是k-边连接的；即，除非移除k或更多边，否则无法断开图。通常，目标是找到最小重量的增强。一般来说，不能保证存在K边增广。

另请参阅

edge_kcomponents : algorithms for finding k-edge-connected components connectivity : algorithms for determening edge connectivity.

k_edge_augmentation(G, k[, avail, weight, ...])	查找k-edge-connect g的边集。
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-边-子图）是g中最大的一组节点，使得由这些节点定义的g的子图具有至少k的边连通性。

k_edge_components(G, k)	在G中的每个最大k边连接组件中生成节点。
k_edge_subgraphs(G, k)	在G中的每个最大k边连通子图中生成节点。
bridge_components(G)	查找所有桥接组件G。
EdgeComponentAuxGraph()	在图中查找所有k边连接组件的简单算法。

K节点组件

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[, ...])	返回节点s和t在g中的本地边缘连接。
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(G[, weight, heap])

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

用于基于流的连接的实用程序

连接包实用程序

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