Изменения

Связность <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>G </tex> имеет и вершины <tex>n u </tex> вершин и <tex> \sigma (G) \ge \left [ \frac{n}{2} \right ] \quad </tex>, то <tex> \lambda (G) = \sigma (G) </tex>, где <tex> \sigma(G) </tex> - минимальная степень вершин графа <tex> G v </tex>.

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

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

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

Отметим справедливость следующих высказываний:{{Утверждение  [[Теорема Менгера, альтернативное доказательство|''Теорема Менгера для вершинной <tex>k - </tex> связности'']] Наименьшее число вершин, разделяющих две несмежные вершины <tex> u </tex> и <tex> v </tex>, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих <tex> u </tex> и <tex> v </tex>. statement=  Тогда: * Граф  <tex> G </tex> является '''реберно <tex>kl</tex> - вершинно связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>kl</tex> вершинно -реберно непересекающимися путями.}}

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

==ЛитератураИсточники информации==