Изменения

Перейти к: навигация, поиск

K-связность

335 байт добавлено, 06:15, 25 октября 2011
Нет описания правки
{{Определение
|definition=
Граф называется '''<tex>k</tex>-вершинно связным''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным.
}}
Вершинной связностью графа называется
<tex> \varkappa (G) = \max \{ k | G </tex> вершинно <tex>k </tex> - связный связен <tex> \} </tex>
{{Определение
|definition=
Граф называется '''<tex> l </tex> - реберно связным''', если удаление любых <tex> (l - 1) </tex> ребер оставляет граф связным.
}}
 
Реберной связностью графа называется <tex> \lambda(G) = \max \{ l | G </tex> реберно <tex> l </tex> - связен <tex> \} </tex>
{{Теорема
{{Определение|definitionstatement=Граф называется ''' <tex>k\varkappa (G) \leqslant \lambda (G) \leqslant \sigma (G) </tex>-реберно связным''', если [[Вершинная,_реберная_связность,_связь_между_ними_и_минимальной_степенью_вершины|где <tex>\lambdasigma(G) \ge k</tex>]]- минимальная степень вершин графа <tex> G </tex>|proof= smth
}}
Анонимный участник

Навигация