Вершинный бисектор (биссектриса)

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

Вершинный бисектор (биссектриса или Node bisector) графа \Gamma — такое подмножество \Omega вершин графа \Gamma, что \Gamma может быть представлен в виде прямой суммы

\Gamma = \Omega_{1} \cup \Omega \cup \Omega_{2},

где |\Omega_{1}| \geq \frac{1}{3}|\Gamma|, |\Omega_{2}| \geq \frac{1}{3}|\Gamma| и любой путь из \Omega_{1}в \Omega_{2} проходит через \Omega.

Литература

[Math. Syst. Theory]