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>-отделимы в мультиграфе | ||
Версия от 00:42, 10 декабря 2009
[math]\displaystyle{ k }[/math]-Отделимость ([math]\displaystyle{ k }[/math]-Separability) - две несмежные вершины [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] в графе [math]\displaystyle{ G }[/math] называются [math]\displaystyle{ k }[/math]-отделимыми, если из графа [math]\displaystyle{ G }[/math] можно удалить не более [math]\displaystyle{ k }[/math] вершин, чтобы в оставшемся графе вершины [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] лежали в разных компонентах связности. Если вершины [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] в мультиграфе [math]\displaystyle{ G }[/math] соединены ребрами [math]\displaystyle{ e_{1}, \ldots, e_{p} }[/math]([math]\displaystyle{ p \geq 0 }[/math]), то [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] в [math]\displaystyle{ G }[/math] называются [math]\displaystyle{ k }[/math]-отделимыми, когда [math]\displaystyle{ p \leq k }[/math] и они [math]\displaystyle{ (k-p) }[/math]-отделимы в мультиграфе [math]\displaystyle{ G \setminus \{e_{1}, \ldots, e_{p}\} }[/math].
Литература
[Зыков/84]