Изменения

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

K-связность

1152 байта убрано, 05:13, 27 октября 2011
Нет описания правки
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> тривиально.
Анонимный участник

Навигация