Connectivity#

连通性和割算法

Edge-augmentation#

算法用于寻找 k-边增广

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

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

k-边连通分量（k-edge-cc）是图 G 中的一个最大节点集合，其中每对节点之间的边连通性至少为 k。

k-边连通子图（k-edge-subgraph）是图 G 中的一个最大节点集合，由这些节点定义的 G 的子图具有至少 k 的边连通性。

莫迪和怀特算法用于k-组件

k_components(G[, flow_func])

返回图 G 的 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, ...])	返回一个最小基数的节点集合，该集合在图中将源节点与目标节点断开。

Stoer-Wagner最小割算法。

stoer_wagner(G[, weight, heap])

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

连接性包的实用工具

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

`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边连通的。