4551
правка
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
м
Связное доминирующее множество (посмотреть исходный код)
Версия от 15:40, 23 января 2013
, 23 января 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
Доказательство. Обозначим за | Доказательство. Обозначим за <math>F_H(a) \; </math> подмножество вершин F(a) с расстоянием менее h + 1 от горизонтальной (и за <math>F_V(a) \; </math> - соответственно, от вертикальной) границы некоторой ячейки в P(a). Тогда <math>F(a) = F_H(a) \cup F_V(a)</math>. Более того, все <math>F_H(i(h+1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> являются непересекающимися. Следовательно, | ||
F(a) = | <math>\sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F_H(i(h+1))| \le |F| \le 8opt</math> | ||
Подобным же образом, все <math>F_V(i(h+1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> являются непересекающимися и | |||
<math>\sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F_V(i(h+1))| \le |F| \le 8opt</math> | |||
E | E | ||
i=0 | i=0 | ||