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

Литература

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