Просмотр исходного текста страницы K-связность

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

{{Определение
|definition=
Граф называется '''<tex>k</tex> - вершинно связным''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным.


Граф <tex> G </tex>  является '''<tex>k</tex> - вершинно связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>k</tex> вершинно непересекающимися путями.

}}

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

Полный граф <tex> \varkappa (K_n) = n - 1 </tex>.

{{Определение
|definition=
Граф называется '''<tex> l </tex> - реберно связным''', если удаление любых <tex> (l - 1) </tex> ребер оставляет граф связным. 


Граф  <tex> G </tex> является '''<tex> l </tex> - реберно связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.
}}

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

При <tex> n = 1,   \lambda (K_1) = 0 </tex> . 


{{Теорема

|statement=  <tex> \varkappa (G) \leqslant  \lambda (G) \leqslant \sigma (G) </tex> , где  <tex> \sigma(G) </tex> - минимальная степень вершин графа <tex> G </tex>
|proof= 

<tex> \lambda (G) \leqslant \sigma (G) </tex> - очевидно.

Рассмотрим <tex> \varkappa (G) \leqslant  \lambda (G) </tex>.

Пусть <tex> \lambda (G)  = l </tex>.
Покажем, что можем удалить <tex> l </tex> вершин и сделать граф несвязным.

Выберем вершину из правой компоненты.Тогда возможны варианты:

1. Все <tex> l </tex> рёбер инцидентны вершине. Тогда:

# Если вершина не единственна - удаляем вершину.
# Если вершина единственная, тогда:
##Во второй компоненте  более <tex> l - 1 </tex> вершин - удаляем их.
## Удаляем её.

2. Удалив не более <tex> l - 1 </tex> вершин получаем несвязный граф.
}}

Если граф <tex>G </tex> имеет <tex>n </tex> вершин и <tex> \sigma (G)  \ge \left [ \frac{n}{2} \right ] \quad </tex>, то  <tex>  \lambda (G) = \sigma (G) </tex>.

==Смотри также==
* [[Теорема Менгера]]

==Литература==

* Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)


[[Категория:Связность в графах]]