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

Материал из WikiGrapp
Версия от 14:13, 1 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Вершинный бисектор (биссектриса)''' (''Node bisector'') - Вершинным бисектором граф...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Вершинный бисектор (биссектриса) (Node bisector) - Вершинным бисектором графа [math]\displaystyle{ \Gamma }[/math] называется подмножество [math]\displaystyle{ \Omega }[/math] вершин графа [math]\displaystyle{ \Gamma }[/math] такое, что [math]\displaystyle{ \Gamma }[/math] может быть представлен в виде прямой суммы

[math]\displaystyle{ \Gamma = \Omega_{1} \cup \Omega \cup \Omega_{2}, }[/math]

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

Литература

[Math. Syst. Theory]