Изменения

Связность <tex>k</tex>- cвязность {{---}} одна из топологических характеристик графа.  

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

[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Вершинной связностью ]] графа называется<tex> \varkappa (G) = \max \{ k | \mid G </tex> вершинно <tex> k </tex> - связен <tex> \} </tex>. Полный граф , при этом для полного графа полагаем <tex> \varkappa (K_n) = n - 1 </tex>.

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

[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью ]] графа называется <tex> \lambda(G) = \max \{ l | \mid G </tex> реберно <tex> l </tex> - связен <tex> \} </tex>, для тривиального графа считаем <tex> \lambda (K_1) = 0 </tex>.   ==k-связность и непересекающиеся пути между вершинами==

При Рассмотрим граф <tex> n = 1, \lambda (K_1) = 0 G </tex> и вершины <tex> u </tex> и <tex> v </tex> .

Из теоремы [[Теорема Менгера, альтернативное доказательство|statement= теоремы Менгера для вершинной <tex> \varkappa (G) \leqslant \lambda (G) \leqslant \sigma (G) k</tex> -связности]] имеем, что наименьшее число вершин, где разделяющих две несмежные вершины <tex> u </tex> и <tex> \sigma(G) v </tex> - минимальная степень , равно наибольшему числу простых путей, не имеющих общих вершин графа , соединяющих <tex> G u </tex>|proof= и <tex> v </tex>.

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

Пусть <tex> \lambda (G) = l </tex>Подобная теорема справедлива и для реберной связности.ПокажемТо есть из [[Теорема Менгера, что можем удалить альтернативное доказательство|''теоремы Менгера для реберной <tex> l k</tex> вершин и сделать граф несвязным.-связности'']] следует:

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

1==См. Все <tex> l </tex> рёбер инцидентны вершине. Тогда:также==* [[Теорема Менгера]]* [[Теорема Менгера, альтернативное доказательство]]

2* Харари Ф. Возьмем вершину во второй компонентеТеория графов.Удалим у ребер[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, инцидентных 2006. — 296 с этими двумя вершинами.)* Форд Л., все левые концыФалкерсон Д., а у остальных - все правые концыПотоки в сетях, пер.с англ., М., 1966[[Категория:Алгоритмы и структуры данных]][[Категория:Связность в графах]]{{Заголовок со строчной буквы}}