|
|
| Строка 32: |
Строка 32: |
| | |proof= | | |proof= |
| | | | |
| − | <tex> \lambda (G) \leqslant \sigma (G) </tex> - очевидно.
| + | [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины | См. статью по этой теме]] |
| | | | |
| − | Рассмотрим <tex> \varkappa (G) \leqslant \lambda (G) </tex>.
| |
| − |
| |
| − | Пусть <tex> \lambda (G) = l </tex>.
| |
| − | Покажем, что можем удалить <tex> l </tex> вершин и сделать граф несвязным.
| |
| − |
| |
| − | Выберем вершину из правой компоненты.Тогда возможны варианты:
| |
| − |
| |
| − | 1. Все <tex> l </tex> рёбер инцидентны вершине. Тогда:
| |
| − |
| |
| − | # Если вершина не единственна - удаляем вершину.
| |
| − | # Если вершина единственная, тогда:
| |
| − | ##Во второй компоненте более <tex> l - 1 </tex> вершин - удаляем их.
| |
| − | ## Удаляем её.
| |
| − |
| |
| − | 2. Удалив не более <tex> l - 1 </tex> вершин получаем несвязный граф.
| |
| | }} | | }} |
| | | | |
Версия 01:04, 3 ноября 2011
Связность - одна из топологических характеристик графа.
| Определение: |
| Граф называется [math]k[/math] - вершинно связным, если удаление любых [math] (k - 1) [/math] вершин оставляет граф связным.
Граф [math] G [/math] является [math]k[/math] - вершинно связным [math]\Leftrightarrow [/math] любая пара его вершин соединена по крайней мере [math]k[/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] G [/math] является [math] l [/math] - реберно связным [math]\Leftrightarrow [/math] любая пара его вершин соединена по крайней мере [math] l [/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]\triangleleft[/math] |
Если граф [math]G [/math] имеет [math]n [/math] вершин и [math] \sigma (G) \ge \left [ \frac{n}{2} \right ] \quad [/math], то [math] \lambda (G) = \sigma (G) [/math].
Смотри также
Литература
- Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
