Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
Центральная область | Центральная область | ||
Пусть | Пусть <math>G_e(d) \; </math> обозначает часть исходного графа G, лежащую в области <math>C_e(d) \; </math>. Точнее говоря, <math>G_e(h) \; </math> представляет собой часть графа G, лежащую в центральной области e. <math>G_e(h) \; </math> может состоять из нескольких связных компонентов. Пусть <math>K_e \; </math> обозначает подмножество вершин <math>G_e(0) \; </math> с минимальной мощностью, таких, что для каждого связного компонента H области <math>G_e(h),/math подмножество <math>K_e \; </math> содержит связную компоненту, являющуюся [[доминатор|доминатором]] H. Иными словами, <math>K_e \; </math> представляет собой минимальное объединение связных доминирующих множеств в <math>G(0) \; </math> для связных компонент <math>G_e(h) \; </math>. | ||
Теперь обозначим за K(a) объединение <math>K_e \; </math> для e по всем ячейкам разбиения P(a). K(a) обладает двумя важными свойствами. | |||
Лемма 2. | '''Лемма 1. K(a) можно вычислить за время <math>n^{O(m2)} \; </math>''' | ||
'''Лемма 2. <math>|K^a| \le opt</math> для <math>0 \le a \le m - 1</math>.''' | |||
Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины p2/2 порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин Ge(0) имеет размер не более (dp2me)2. Следовательно, размер Ke составляет не более 3(d p2me)2, поскольку любое доминирующее множество в связном графе имеет остовное дерево с дугами длиной не более 3. Предположим, что Ge(0) имеет ne вершин. Тогда количество кандидатов для Ke составляет не более | Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины p2/2 порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин Ge(0) имеет размер не более (dp2me)2. Следовательно, размер Ke составляет не более 3(d p2me)2, поскольку любое доминирующее множество в связном графе имеет остовное дерево с дугами длиной не более 3. Предположим, что Ge(0) имеет ne вершин. Тогда количество кандидатов для Ke составляет не более | ||