K-Отделимость

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