4194
правки
K-Отделимость: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''<math>k</math>-Отделимость''' (''<math>k</math>-Separability'') - две несмежные вершины <math>x</math> ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Отделимость''' (''<math>k</math>-Separability'') - | '''<math>k</math>-Отделимость''' (''[[k-Separability|<math>k</math>-Separability]]'') - | ||
две несмежные вершины <math>x</math> и <math>y</math> в графе <math>G</math> называются | две [[смежные вершины|несмежные вершины]] <math>x</math> и <math>y</math> в [[граф|графе]] <math>G</math> называются | ||
<math>k</math>-отделимыми, если из графа <math>G</math> можно удалить не более <math>k</math> вершин, | <math>k</math>-отделимыми, если из графа <math>G</math> можно удалить не более <math>k</math> вершин, | ||
чтобы в оставшемся графе вершины <math>x</math> и <math>y</math> лежали в разных компонентах | чтобы в оставшемся графе вершины <math>x</math> и <math>y</math> лежали в разных [[компонента связности|компонентах связности]]. Если вершины <math>x</math> и <math>y</math> в [[мультиграф|мультиграфе]] <math>G</math> соединены [[ребро|ребрами]] | ||
связности. Если вершины <math>x</math> и <math>y</math> в мультиграфе <math>G</math> соединены ребрами | |||
<math>e_{1}, \ldots, e_{p}</math>(<math>p \geq 0</math>), то <math>x</math> и <math>y</math> в <math>G</math> называются | <math>e_{1}, \ldots, e_{p}</math>(<math>p \geq 0</math>), то <math>x</math> и <math>y</math> в <math>G</math> называются | ||
<math>k</math>-отделимыми, когда <math>p \leq k</math> и они <math>(k-p)</math>-отделимы в мультиграфе | <math>k</math>-отделимыми, когда <math>p \leq k</math> и они <math>(k-p)</math>-отделимы в мультиграфе | ||