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