K-связность — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
| (не показано 12 промежуточных версий 8 участников) | |||
| Строка 1: | Строка 1: | ||
| − | + | <tex>k</tex>-cвязность {{---}} одна из топологических характеристик графа. | |
{{Определение | {{Определение | ||
| + | |id=def_1 | ||
|definition= | |definition= | ||
| − | Граф называется ''' | + | Граф называется '''вершинно <tex>k</tex>-связным''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным. |
}} | }} | ||
| − | Вершинной связностью графа называется | + | [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Вершинной связностью]] графа называется |
| − | <tex> \varkappa (G) = \max \{ k | + | <tex> \varkappa (G) = \max \{ k \mid G </tex> вершинно <tex>k</tex>-связен <tex> \} </tex>, при этом для полного графа полагаем <tex> \varkappa (K_n) = n - 1 </tex>. |
| − | |||
| − | |||
{{Определение | {{Определение | ||
| + | |id=def_2 | ||
|definition= | |definition= | ||
| − | Граф называется ''' | + | Граф называется '''реберно <tex>l</tex>-связным''', если удаление любых <tex> (l - 1) </tex> ребер оставляет граф связным. |
}} | }} | ||
| − | Реберной связностью графа называется <tex> \lambda(G) = \max \{ l | + | [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью]] графа называется <tex> \lambda(G) = \max \{ l \mid G </tex> реберно <tex>l</tex>-связен <tex> \} </tex>, для тривиального графа считаем <tex> \lambda (K_1) = 0 </tex>. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | ==k-связность и непересекающиеся пути между вершинами== | |
| + | Рассмотрим граф <tex> G </tex> и вершины <tex> u </tex> и <tex> v </tex>. | ||
| − | + | Пусть <tex> S </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>k</tex>-связности]] имеем, что наименьшее число вершин, разделяющих две несмежные вершины <tex> u </tex> и <tex> v </tex>, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих <tex> u </tex> и <tex> v </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>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 с.) | * Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.) | ||
| − | |||
* Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966 | * Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966 | ||
| + | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Связность в графах]] | [[Категория:Связность в графах]] | ||
| + | {{Заголовок со строчной буквы}} | ||
Текущая версия на 19:05, 4 сентября 2022
-cвязность — одна из топологических характеристик графа.
| Определение: |
| Граф называется вершинно -связным, если удаление любых вершин оставляет граф связным. |
Вершинной связностью графа называется
вершинно -связен , при этом для полного графа полагаем .
| Определение: |
| Граф называется реберно -связным, если удаление любых ребер оставляет граф связным. |
Реберной связностью графа называется реберно -связен , для тривиального графа считаем .
k-связность и непересекающиеся пути между вершинами
Рассмотрим граф и вершины и .
Пусть — множество вершин/ребер/вершин и ребер.
разделяет и , если и принадлежат разным компонентам связности графа , который получается удалением элементов множества из .
Из теоремы теоремы Менгера для вершинной -связности имеем, что наименьшее число вершин, разделяющих две несмежные вершины и , равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих и .
Отсюда непосредственно следует:
| Утверждение: |
Граф является вершинно -связным любая пара его вершин соединена по крайней мере вершинно непересекающимися путями. |
Подобная теорема справедлива и для реберной связности. То есть из теоремы Менгера для реберной -связности следует:
| Утверждение: |
Граф является реберно -связным любая пара его вершин соединена по крайней мере -реберно непересекающимися путями. |
См. также
Источники информации
- Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
- Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966
