# Edge connectivity

Перейти к:навигация, поиск

Edge connectivity --- реберная связность.

We define the edge-connectivity, $K_{e}(G)$ or $K_{e}$, for the connected graph $G$ to be the size of the smallest cut-set of $G$. $G$ is said to be $h$-edge-connected for any positive integer $h$ satisfying $h \leq K_{e}(G)$. We denote the smallest degree of any vertex in a graph by $\delta$. Since the set of edges incident with any vertex forms a cut-set, we have $\delta \geq K_{e}(G)$.

For any connected graph $G$:

$K_{v}(G) \leq K_{e}(G) \leq \delta.$

$K_{v}(G)$ is the vertex-connectivity.

The local-edge-connectivity $\lambda(u,v)$ of two vertices $u$ and $v$ in a graph or digraph $D$ is the maximum number of edge-disjoint $u-v$-paths in $D$, and the edge-connectivity of $D$ is defined as $\lambda(D) = \min\{\lambda(u,v) | u,v \in V(D)\}$.