连通性

连通性和切割算法

边缘增强

寻找k边增广的算法

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

参见

edge_kcomponents
寻找k边连通分量的算法
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以计算基于流的节点连接。