4511
правок
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Связное доминирующее множество (посмотреть исходный код)
Версия от 15:00, 23 января 2013
, 23 января 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 43: | Строка 43: | ||
Теперь обозначим за K(a) объединение <math>K_e \; </math> для e по всем ячейкам разбиения P(a). K(a) обладает двумя важными свойствами. | Теперь обозначим за K(a) объединение <math>K_e \; </math> для e по всем ячейкам разбиения P(a). K(a) обладает двумя важными свойствами. | ||
'''Лемма 1. K(a) можно вычислить за время <math>n^{O( | |||
'''Лемма 1. K(a) можно вычислить за время <math>n^{O(m^2)} \; </math>''' | |||
'''Лемма 2. <math>|K^a| \le opt</math> для <math>0 \le a \le m - 1</math>.''' | '''Лемма 2. <math>|K^a| \le opt</math> для <math>0 \le a \le m - 1</math>.''' | ||
Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины | |||
Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины <math>\sqrt{2}/2</math> порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин <math>G_e(0) \; </math> имеет размер не более <math>( \mathcal{d} \sqrt{2m} \mathcal{e} )^2</math>. Следовательно, размер <math>K_e \; </math> составляет не более <math>3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2</math>, поскольку любое доминирующее множество в связном графе имеет остовное дерево с дугами длиной не более 3. Предположим, что <math>G_e(0) \; </math> имеет <math>n_e \; </math> вершин. Тогда количество кандидатов для <math>K_e \; </math> составляет не более | |||
£ V) ■ | £ V) ■ | ||