Вершинный бисектор (биссектриса): различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Вершинный бисектор (биссектриса)''' (''Node bisector'') - Вершинным бисектором граф...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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:50, 7 октября 2009
Вершинный бисектор (биссектриса) (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]