主题
Search

边连通度

图的边连通度，也称为线连通度，是从图 G 中删除后会使 G 断开连接的最小边数 lambda(G)。换句话说，它是最小边割的大小。非连通图的边连通度因此为 0，而具有图桥的连通图的边连通度为 1。

设 kappa(G) 为图 G 的顶点连通度，delta(G) 为其最小度，则对于任何图，

kappa(G)<=lambda(G)<=delta(G)

(Whitney 1932, Harary 1994, p. 43)。

连通无桥图是 2-边连通的。

图的边连通度可以使用 Wolfram 语言中的以下命令确定EdgeConnectivity[g]。 许多命名图的预计算边连通度可以使用以下命令获得GraphData[graph，"EdgeConnectivity"].

另请参见

连通图、循环边连通度、非连通图、边割、k-边连通图、最小边割、顶点连通度

使用 Wolfram|Alpha 探索

参考文献

Harary, F. 图论。 Reading, MA: Addison-Wesley, p. 43, 1994。Skiena, S. 离散数学实施：使用 Mathematica 的组合数学和图论。 Reading, MA: Addison-Wesley, pp. 177-178, 1990。Whitney, H. “全等图和图的连通性。” Amer. J. Math. 54, 150-168, 1932。

在 Wolfram|Alpha 上被引用

边连通度

请引用为

Weisstein, Eric W. “边连通度。” 来自 MathWorld—— Wolfram Web 资源。 https://mathworld.net.cn/EdgeConnectivity.html

主题分类