边连通性

图或两个顶点的边连通性，最近也称为组粘附性。

用法

edge_connectivity(graph, source = NULL, target = NULL, checks = TRUE)

edge_disjoint_paths(graph, source = NULL, target = NULL)

adhesion(graph, checks = TRUE)

参数

graph

输入图。

source

源顶点的 ID，对于 edge_connectivity() 可以为 NULL，请参见下面的详细信息。

target

目标顶点的 ID，对于 edge_connectivity() 可以为 NULL，请参见下面的详细信息。

checks

逻辑常量。是否检查图是否连通以及顶点的度。如果图不是（强）连通的，那么连通性显然为零。否则，如果最小度为 1，则边连通性也为 1。执行这些检查是个好主意，因为与连通性计算本身相比，它们可以快速完成。它们是由 Peter McMahan 提出的，感谢 Peter。

值

标量实数值。

edge_connectivity() 边连通性

一对顶点（source 和 target）的边连通性是消除从 source 到 target 的所有（有向）路径所需删除的最小边数。如果给出了 source 和 target 参数（而不是 NULL），edge_connectivity() 将计算此数量。

图的边连通性是图中每对（有序）顶点的边连通性的最小值。如果既未给出 source 也未给出 target 参数（即，它们都为 NULL），则 edge_connectivity() 将计算此数量。

edge_disjoint_paths() 两个顶点之间的最大边不相交路径数

如果两个顶点之间的一组路径不共享任何边，则称为边不相交。此函数使用最大流技术计算最大边不相交路径数。在有向图中考虑有向路径。

两个顶点之间的一组边不相交路径是它们之间的一组路径，其中不包含公共边。两个顶点之间的最大边不相交路径数与它们的边连通性相同。

当源和目标之间没有直接边时，顶点不相交路径的数量与两个顶点的顶点连通性相同。当存在某些边时，每条边都会贡献一条额外的路径。

adhesion() 图的粘附性

图的粘附性是获得非强连通图所需删除的最小边数。这与图的边连通性相同。

所有三个函数

此页面上记录的三个函数计算相似的属性，更准确地说，最通用的是 edge_connectivity()，包含其他函数只是为了具有更具描述性的函数名称。

参考文献

Douglas R. White 和 Frank Harary (2001)：社会网络中块的内聚力：节点连通性和条件密度，Sociological Methodology，vol. 31, 2001, pp. 305–59。

参见

其他流：dominator_tree()、is_min_separator()、is_separator()、max_flow()、min_cut()、min_separators()、min_st_separators()、st_cuts()、st_min_cuts()、vertex_connectivity()

作者

Gabor Csardi csardi.gabor@gmail.com

示例

g <- sample_pa(100, m = 1)
g2 <- sample_pa(100, m = 5)
edge_connectivity(g, 100, 1)
#> [1] 1
edge_connectivity(g2, 100, 1)
#> [1] 5
edge_disjoint_paths(g2, 100, 1)
#> [1] 5

g <- sample_gnp(50, 5 / 50)
g <- as_directed(g)
g <- induced_subgraph(g, subcomponent(g, 1))
adhesion(g)
#> [1] 1