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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''<math>k</math>-Отделимость''' (''<math>k</math>-Separability'') - две несмежные вершины <math>x</math> ...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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>-отделимы в мультиграфе
<math>G \setminus \{e_{1}, \ldots, e_{p}\}</math>.
<math>G \setminus \{e_{1}, \ldots, e_{p}\}</math>.
==Литература==
==Литература==
[Зыков/84]
* Зыков А.А. Основы теории графов. — М.: Наука, 1984.

Текущая версия от 11:36, 2 июня 2011

[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].

Литература

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