Связное доминирующее множество: различия между версиями

Перейти к навигации Перейти к поиску
Строка 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(m2)} \; </math>'''
 
'''Лемма 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 показать несложно. Заметим, что вершины квадрата со сторонами длины p2/2 порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин Ge(0) имеет размер не более (dp2me)2. Следовательно, размер Ke составляет не более 3(d p2me)2, поскольку любое доминирующее множество в связном графе имеет остовное дерево с дугами длиной не более 3. Предположим, что Ge(0) имеет ne вершин. Тогда количество кандидатов для Ke составляет не более
 
Справедливость леммы 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)  ■


Источник — http://pco.iis.nsk.su/wega/index.php/Связное_доминирующее_множество