K-Отделимость: различия между версиями

'''<math>\,k</math>-Отделимость''' (''[[k-Separability|<math>\,k</math>-Separability]]'') —

две [[смежные вершины|несмежные вершины]] <math>\,x</math> и <math>\,y</math> в [[граф|графе]] <math>\,G</math> называются

<math>\,k</math>-отделимыми, если из графа <math>\,G</math> можно удалить не более <math>\,k</math> вершин,

чтобы в оставшемся графе вершины <math>\,x</math> и <math>\,y</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>-отделимы в мультиграфе

* Зыков А.А. Основы теории графов. — М.: Наука, 1984.