k-edge-connected graph

对于一张图，若不存在大小为k − 1的点集或边集，使得从图中移除该集合后，图就变为非连通图，则称该图是k-点连通图（英语：k-vertex-connected graph）或k-边连通图（英语：k-edge-connected graph）。k-点连通图通常也简称k-连通图。 二分图（英語：bipartite graph

k-edge-connected graph）λ(G)是最小的边割集的大小，两个顶点u到v的局部边连通度λ(u, v)是u到v最小的边割集的大小，同样，局部边连通度是对称的。如果一个图的边连通度为k或更大，则称该图为k-边连通的。

连通图（英語：Connected graph）是图论中最基本概念之一，其定义基于连通的概念。在一个无向图G中，若从顶点 v i {\displaystyle v_{i}} 到顶点 v j {\displaystyle v_{j}} 有路径相连（从 v j {\displaystyle v_{j}}

k-edge-connected graph）。 对无源汇最小割问题加以推广，可以得到最小k割问题（英语：minimum k-cut），即将图分为至少k个子图的最小割问题。对于一个确定的k，这个问题可以在多项式时间内完成，虽然算法在k较大时并不理想。

Siek, Jeremy; Lee, Lie-Quan; Lumsdaine, Andrew, 7.1 Connected components: Definitions, The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley: