|
|
| Строка 45: |
Строка 45: |
| | 2. Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинами, все левые концы, а у остальных - все правые концы. | | 2. Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинами, все левые концы, а у остальных - все правые концы. |
| | }} | | }} |
| − |
| |
| − | {{Определение
| |
| − | |definition=
| |
| − | Множество <tex>S</tex> вершин, ребер или вершин и ребер '''разделяет''' <tex>u</tex> и <tex>v</tex>, если <tex>u</tex> и <tex>v</tex> принадлежат различным [[Отношение_связности,_компоненты_связности| компонентам графа]] <tex>G \setminus S</tex>
| |
| − | }}
| |
| − |
| |
| − | {{Определение
| |
| − | |definition=
| |
| − | Говорят, что вершины <tex>u</tex> и <tex>v</tex> <tex>k</tex>'''-разделимы''', если минимальная мощность множества, разделяющего <tex>u</tex> и <tex>v</tex> равна <tex>k</tex>
| |
| − | }}
| |
| − |
| |
| − | Многие утверждения для связных графов можно обобщить для случая <tex>k</tex>-связности, однако аналог тривиального утверждения часто оказывается содержательным. Простейший пример - [[Теорема Менгера]], утверждение которой для <math>k=1</math> тривиально.
| |
Версия 05:13, 27 октября 2011
Связность - одна из топологических характеристик графа.
| Определение: |
| Граф называется [math]k[/math] - вершинно связным, если удаление любых [math] (k - 1) [/math] вершин оставляет граф связным. |
Вершинной связностью графа называется
[math] \varkappa (G) = \max \{ k | G [/math] вершинно [math] k [/math] - связен [math] \} [/math].
Полный граф [math] \varkappa (K_n) = n - 1 [/math].
| Определение: |
| Граф называется [math] l [/math] - реберно связным, если удаление любых [math] (l - 1) [/math] ребер оставляет граф связным. |
Реберной связностью графа называется [math] \lambda(G) = \max \{ l | G [/math] реберно [math] l [/math] - связен [math] \} [/math]
При [math] n = 1, \lambda (K_1) = 0 [/math] .
| Теорема: |
[math] \varkappa (G) \leqslant \lambda (G) \leqslant \sigma (G) [/math] , где [math] \sigma(G) [/math] - минимальная степень вершин графа [math] G [/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math] \lambda (G) \leqslant \sigma (G) [/math] - очевидно.
Рассмотрим [math] \varkappa (G) \leqslant \lambda (G) [/math].
Пусть [math] \lambda (G) = l [/math].
Покажем, что можем удалить [math] l [/math] вершин и сделать граф несвязным.
Выберем вершину из правой компоненты.Тогда возможны варианты:
1. Все [math] l [/math] рёбер инцидентны вершине. Тогда:
- Если вершина не единственна - удаляем вершину.
- Если вершина единственная, тогда:
- Во второй компоненте [math] l [/math] вершин - (??).
- Удаляем её.
2. Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинами, все левые концы, а у остальных - все правые концы. |
| [math]\triangleleft[/math] |
