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

Материал из WikiGrapp
Перейти к:навигация, поиск

\,k-Отделимость (\,k-Separability) — две несмежные вершины \,x и \,y в графе \,G называются \,k-отделимыми, если из графа \,G можно удалить не более \,k вершин, чтобы в оставшемся графе вершины \,x и \,y лежали в разных компонентах связности. Если вершины \,x и \,y в мультиграфе \,G соединены ребрами e_{1}, \ldots, e_{p} (p \geq 0), то \,x и \,y в \,G называются \,k-отделимыми, когда p \leq k и они \,(k-p)-отделимы в мультиграфе G \setminus \{e_{1}, \ldots, e_{p}\}.

Литература

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