Изменения

Связность <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>.  

При <tex> n = 1, \lambda (K_1) = 0 </tex> . k-связность и непересекающиеся пути между вершинами==

|statement= Пусть <tex> \varkappa (G) \leqslant \lambda (G) \leqslant \sigma (G) </tex> , где <tex> \sigma(G) S </tex> {{--- минимальная степень }} множество вершин графа <tex> G </tex>|proof= <tex> \lambda (G) \leqslant \sigma (G) <ребер/tex> - очевидновершин и ребер.

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

Выберем вершину из правой компоненты.Тогда возможны варианты:1)Все Из теоремы [[Теорема Менгера, альтернативное доказательство|теоремы Менгера для вершинной <tex> l k</tex> рёбер инцидентны вершине.Тогда: 1.1)Если вершина не единственна - удаляем вершину. 1.2)Если вершина единственнаясвязности]] имеем, что наименьшее число вершин, тогда 1.2.1)Во второй компоненте разделяющих две несмежные вершины <tex> l u </tex> и <tex> v </tex> вершин - (??) 1.2.2)Удаляем её.2)Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинамиравно наибольшему числу простых путей, все левые концыне имеющих общих вершин, а у остальных - все правые концысоединяющих <tex> u </tex> и <tex> v </tex>.

{{ОпределениеПодобная теорема справедлива и для реберной связности. То есть из [[Теорема Менгера, альтернативное доказательство|definition=Множество ''теоремы Менгера для реберной <tex>Sk</tex> вершин, ребер или вершин и ребер '''разделяет'-связности'' ]] следует: {{Утверждение|statement=Граф  <tex>uG </tex> и является '''реберно <tex>vl</tex>, если -связным''' <tex>u\Leftrightarrow </tex> и <tex>v</tex> принадлежат различным [[Отношение_связности,_компоненты_связности| компонентам графа]] любая пара его вершин соединена по крайней мере <tex>G \setminus Sl</tex>-реберно непересекающимися путями.

{{Определение==См. также==|definition=* [[Теорема Менгера]]Говорят* [[Теорема Менгера, что вершины <tex>u</tex> и <tex>v</tex> <tex>k</tex>'''-разделимы''', если минимальная мощность множества, разделяющего <tex>u</tex> и <tex>v</tex> равна <tex>k</tex>альтернативное доказательство]] }}==Источники информации==

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