Вершинный бисектор (биссектриса): различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Вершинный бисектор (биссектриса)''' (''Node bisector'') - Вершинным бисектором граф...)
 
Нет описания правки
 
(не показаны 3 промежуточные версии 2 участников)
Строка 1: Строка 1:
'''Вершинный бисектор (биссектриса)''' (''Node bisector'') -
'''Вершинный бисектор''' ('''биссектриса''' или ''[[Node bisector]]'') графа <math>\Gamma</math> — такое подмножество <math>\Omega</math> [[вершина|вершин]] [[граф|графа]] <math>\Gamma</math>, что <math>\Gamma</math> может быть представлен в
Вершинным бисектором графа <math>\Gamma</math> называется подмножество <math>\Omega</math>
вершин графа <math>\Gamma</math> такое, что <math>\Gamma</math> может быть представлен в
виде прямой суммы
виде прямой суммы


:::<math>\Gamma = \Omega_{1} \cup \Omega \cup \Omega_{2},</math>
:::<math>\Gamma = \Omega_{1} \cup \Omega \cup \Omega_{2},</math>


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

Текущая версия от 15:36, 26 ноября 2010

Вершинный бисектор (биссектриса или 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]