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

Связность - одна из топологических характеристик графа.
{{Определение
|definition=
Граф называется '''[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|вершинно  <tex>k</tex> -  связным]]''', если удаление любых  <tex> (k  -  1) </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> \lambda(G) = \max \{ l | G </tex> реберно <tex> l </tex> -  связен <tex> \} </tex>

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


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


Рассмотрим граф <tex> G </tex> .

Пусть <tex> S </tex> - множество вершин/ребер/вершин и ребер.

Рассмотрим вершины <tex> u </tex> и  <tex> v </tex>. 

<tex> S </tex> разделяет <tex> u </tex> и <tex> v </tex>, если <tex> u </tex> и <tex> v </tex> принадлежат разным компонентам связности графа <tex> G \smallsetminus S </tex>, который получается удалением элементов множества <tex> S </tex> из <tex> G </tex>.


Справедливы следующие утверждения:

* Наименьшее число вершин, разделяющих две несмежные вершины <tex> u </tex> и <tex> v </tex>, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих <tex> u </tex> и <tex> v </tex>. (См.[[Теорема Менгера, альтернативное доказательство|''Теорема Менгера для вершинной <tex>k - </tex> связности'']])


Тогда:

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

Подобная теорема справедлива и для реберной связности. То есть:

* <tex>\lambda(G) = k</tex> <tex>\Leftrightarrow</tex>  для всех пар вершин <tex> u </tex> и <tex> v </tex> существует <tex>k</tex> реберно непересекающихся путей из <tex> u </tex> в <tex> v </tex>. (См.[[Теорема Менгера, альтернативное доказательство|''Теорема Менгера для реберной <tex>k - </tex> связности'']])


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

==Смотри также==
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
==Литература==

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

* Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966
[[Категория:Связность в графах]]