Редактирование: K-связность
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
| − | + | Связность - одна из топологических характеристик графа. | |
{{Определение | {{Определение | ||
| − | |||
|definition= | |definition= | ||
| − | Граф называется '''вершинно <tex>k</tex>-связным''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным. | + | Граф называется '''[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|вершинно <tex>k</tex> - связным]]''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным. |
}} | }} | ||
| − | + | Вершинной связностью графа называется | |
| − | <tex> \varkappa (G) = \max \{ k | + | <tex> \varkappa (G) = \max \{ k | G </tex> вершинно <tex> k </tex> - связен <tex> \} </tex>. |
| + | |||
| + | Полный граф <tex> \varkappa (K_n) = n - 1 </tex>. | ||
{{Определение | {{Определение | ||
| − | |||
|definition= | |definition= | ||
| − | Граф называется '''реберно <tex>l</tex>-связным''', если удаление любых <tex> (l - 1) </tex> ребер оставляет граф связным. | + | Граф называется ''' [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|реберно <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 \ | + | <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= | |statement= | ||
| − | Граф <tex> G </tex> является '''вершинно <tex>k</tex>-связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>k</tex> вершинно непересекающимися путями. | + | Граф <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= | |statement= | ||
| − | Граф <tex> G </tex> является '''реберно <tex>l</tex>-связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>l</tex>-реберно непересекающимися путями. | + | Граф <tex> G </tex> является '''реберно <tex> l </tex> - связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями. |
}} | }} | ||
| − | == | + | ==Смотри также== |
* [[Теорема Менгера]] | * [[Теорема Менгера]] | ||
* [[Теорема Менгера, альтернативное доказательство]] | * [[Теорема Менгера, альтернативное доказательство]] | ||
| + | ==Литература== | ||
| − | + | * Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.) | |
| − | |||
* Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966 | * Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966 | ||
| − | |||
[[Категория:Связность в графах]] | [[Категория:Связность в графах]] | ||
| − | |||
