Изменения
Нет описания правки
{{Определение
|definition=
Граф называется '''<tex>k</tex> - вершинно связным''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным. Граф <tex> G </tex> является '''<tex>k</tex> - вершинно связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>k</tex> вершинно непересекающимися путями.
}}
|definition=
Граф называется '''<tex> l </tex> - реберно связным''', если удаление любых <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>.
Рассмотри граф <tex> G </tex> .
Пусть <tex> S </tex> - множество вершин/ребер/вершин и ребер.
Возьмем рассмотрим вершины <tex> u </tex> и <tex> v </tex>.
<tex> S </tex> разделяет <tex> u </tex> и <tex> v </tex>, если <tex> u, v </tex> принадлежат разным компонентам связности графа <tex> G \smallsetminus S </tex>.
Отсюда справедливы следующие утверждения:
Наименьшее число вершин, разделяющих две несмежные вершины <tex> u </tex> и <tex> v </tex>, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих <tex> u </tex> и <tex> v </tex>.
* Граф <tex> G </tex> является '''<tex>k</tex> - вершинно связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>k</tex> вершинно непересекающимися путями.
* Граф <tex> G </tex> является '''<tex> l </tex> - реберно связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.
==Смотри также==
* Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
* Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966
[[Категория:Связность в графах]]
