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

Перейти к навигации Перейти к поиску

Связное доминирующее множество (посмотреть исходный код)

Версия от 16:01, 23 января 2013

112 байт добавлено ,  23 января 2013
м
→‎Основные результаты
Строка 87: Строка 87:
<math>\frac {1} {{\mathcal{b} m/(h + 1)\mathcal{c}}} \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F(i(h+1))| \le ( \varepsilon\ /2)opt</math>
<math>\frac {1} {{\mathcal{b} m/(h + 1)\mathcal{c}}} \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F(i(h+1))| \le ( \varepsilon\ /2)opt</math>


Это означает, что по меньшей мере половина <math>F(i(h + 1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> удовлетворяет соотношению<math>|F(i(h + 1))| \le \varepsilon\ \cdot opt</math>. □




Окончательный результат
Теперь рассмотрим K(a) и F(a). Согласно леммам 2 и 3, существуют <math>a \in \big\{ 0, h + 1, ... , (\mathcal{b} m/(h + 1)\mathcal{c} - 1)(h + 1) \big\} </math>, такие, что
<math>|K(a) \cup F(a)| \le (1 + \varepsilon\ )opt</math>.


Суммируя вышеприведенные положения, получаем следующий результат:


Теорема 1. Существует (1 + ")-аппроксимация для построения минимального связного доминирующего множества в связных графах единичных дисков, время исполнения которой составляет
'''Лемма 4.''' Для <math>0 \le a \le m — 1</math>, <math>K(a) \cup F(a)</math> представляет собой связное доминирующее множество для исходного связного графа G.
2


Доказательство. Очевидно, что <math>K(a) \cup F(a)</math> является доминирующим множеством для исходного графа G. Его связность можно показать следующим образом. Заметим, что центральная и граничная области перекрываются на область шириной 1. Таким образом, для любого связного компонента H подграфа <math>G_e(h) \; </math>, у F(a) имеется вершина в H. Следовательно, F(a) должен иметь связь с любым связным доминирующим множеством для H, особенно с <math>D_H \; </math> в K(a). Это означает, что <math>D_H \; </math> восстанавливает связи с F, потерянные в результате отрезания части в H. Следовательно, связность <math>K(a) \cup F(a)</math> следует из связности F. □




Подобным же образом, все FV(i(h + 1)) for i = 0;1,..., bm/(h + 1)J - 1 являются непересекающимися и
jFV(i(h + 1))| <  Fj < 8opt : i=0


Таким образом,
Суммируя вышеприведенные положения, получаем следующий результат:
i=0
i=0
< 16opt :
1
 
Это значит, что
\mlQi
l))\<(e/2)opt.
i=0
 
Это означает, что по меньшей мере половина F(i(h + 1)) для i = 0; 1; bm/(h + 1)J - 1 удовлетворяют соотношению
\F(i(h+l))\<s-opt. □
 
Окончательный результат
 
Теперь рассмотрим K(a) и F(a). Согласно леммам 2 и 3, существуют 2 f0;h+ 1, ... , (bm/(h + 1)J - 1)(h + 1)g, такие, что
jK(a)[F(a)j < (1 + ")opt:
 
Лемма 4. Для 0 < a < m — 1, K(a) [ F(a) представляет собой связное доминирующее множество для исходного связного графа G.


Доказательство. Очевидно, что K(a) [ F(a) является доминирующим множеством для исходного графа G. Его связность можно показать следующим образом. Заметим, что центральная и граничная области перекрываются на область шириной 1. Таким образом, для любого связного компонента H подграфа Ge(h), у F(a) имеется вершина в H. Следовательно, F(a) должен иметь связь с любым связным доминирующим множеством для H, особенно с DH в K(a). Это означает, что DH устанавливает связи с F, потерянные в результате отрезания части в H. Следовательно, связность K(a) [ F(a) следует из связности F. □
'''Теорема 1.''' Существует <math>(1 + \varepsilon\ )</math>-аппроксимация для построения минимального связного доминирующего множества в связных графах единичных дисков, время исполнения которой составляет <math>n^{O((1/ \varepsilon\ )log(1/ \varepsilon\ )^2)}</math>.


== Применение ==
== Применение ==
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10376

Навигация