Edge connectivity

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

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)\}.