K-связность

Связность - одна из топологических характеристик графа.

Определение:

Граф называется [math]k[/math] - вершинно связным, если удаление любых [math] (k - 1) [/math] вершин оставляет граф связным.

Вершинной связностью графа называется [math] \varkappa (G) = \max \{ k | G [/math] вершинно [math] k [/math] - связен [math] \} [/math].

Полный граф [math] \varkappa (K_n) = n - 1 [/math].

Определение:

Граф называется [math] l [/math] - реберно связным, если удаление любых [math] (l - 1) [/math] ребер оставляет граф связным.

Реберной связностью графа называется [math] \lambda(G) = \max \{ l | G [/math] реберно [math] l [/math] - связен [math] \} [/math]

При [math] n = 1, \lambda (K_1) = 0 [/math] .

Теорема:

[math] \varkappa (G) \leqslant \lambda (G) \leqslant \sigma (G) [/math] , где [math] \sigma(G) [/math] - минимальная степень вершин графа [math] G [/math]

Доказательство:

[math]\triangleright[/math]

[math] \lambda (G) \leqslant \sigma (G) [/math] - очевидно. Рассмотрим [math] \varkappa (G) \leqslant \lambda (G) [/math]. Пусть [math] \lambda (G) = l [/math]. Покажем, что можем удалить [math] l [/math] вершин и сделать граф несвязным. Выберем вершину из правой компоненты.Тогда возможны варианты: 1. Все [math] l [/math] рёбер инцидентны вершине. Тогда: Если вершина не единственна - удаляем вершину. Если вершина единственная, тогда: Во второй компоненте более [math] l - 1 [/math] вершин - удаляем их. Удаляем её. 2. Удалив не более [math] l - 1 [/math] вершин получаем несвязный граф.

[math]\triangleleft[/math]