Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 51: | Строка 51: | ||
Справедливость леммы 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> составляет не более | Справедливость леммы 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> составляет не более | ||
<math>\sum_{k=0}^{3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2} \binom{n_e}{k} = n_e^{O(m^2)}</math> | <math>\sum_{k=0}^{3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2} \binom{n_e}{k} = n_e^{O(m^2)}</math> | ||
Следовательно, K(a) можно вычислить за время | Следовательно, K(a) можно вычислить за время | ||
O( | |||
<math>\sum_e n_e^{O(m^2)} \le \bigg( \sum_e n_e \bigg) ^{O(m^2)} = n^{O(m^2)}</math> | |||
Доказательство истинности леммы 2 намного сложнее; его можно найти в [5]. | Доказательство истинности леммы 2 намного сложнее; его можно найти в [5]. | ||
Граничная область | Граничная область | ||
Пусть F – связное доминирующее множество G, удовлетворяющее неравенству jFj < 8opt+ 1. Обозначим за F(a) подмножество F, лежащее в граничной области Ba(h + 1). Поскольку построение F занимает полиномиальное время, необходимо рассмотреть только размер F(a). | Пусть F – связное доминирующее множество G, удовлетворяющее неравенству jFj < 8opt+ 1. Обозначим за F(a) подмножество F, лежащее в граничной области Ba(h + 1). Поскольку построение F занимает полиномиальное время, необходимо рассмотреть только размер F(a). | ||