主题
Search

k-边连通图

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

如果不存在移除 k-1 条边就能断开图连接的边的集合，则该图是 k-边连通的（Skiena 1990，p. 177）。给定图的最大边连通性是任何节点的最小度数，因为删除这些边会断开图的连接。完全二分图具有最大边连通性。

k-边连通性图检查在 Wolfram 语言中实现为KEdgeConnectedGraphQ[g, k].

下表给出了 n 节点图的 k-边连通图的数量。

kOEISn=1, 2, ...
0A0007190, 1, 2, 5, 13, 44, 191, ...
1A0524460, 1, 1, 3, 10, 52, 351, ...
2A0524470, 0, 1, 2, 8, 41, 352, ...
3A0524480, 0, 0, 1, 2, 15, 121, ...
40, 0, 0, 0, 1, 3, 25, ...
50, 0, 0, 0, 0, 1, 3, ...
60, 0, 0, 0, 0, 0, 1, ...

另请参阅

循环边连通性, 边连通性, 边割, 图桥, k-连通图

使用 Wolfram|Alpha 探索

参考文献

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 45, 1994.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences A000719/M1452, A052446, A052447, and A052448 in "The On-Line Encyclopedia of Integer Sequences."

在 Wolfram|Alpha 中被引用

k-边连通图

请引用为

Weisstein, Eric W. "k-边连通图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/k-Edge-ConnectedGraph.html

主题分类