4551
правка
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Связное доминирующее множество (посмотреть исходный код)
Версия от 13:51, 22 января 2013
, 22 января 2013→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется ''связным доминирующим множеством''. Связное доминирующее множество минимальной мощности называется ''минимальным связным доминирующим множеством'' (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ H(\Delta\ )</math> для <math>\rho\ < 1</math>, за исключением случая NP | Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется ''связным доминирующим множеством''. Связное доминирующее множество минимальной мощности называется ''минимальным связным доминирующим множеством'' (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ H(\Delta\ )</math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>, где H – гармоническая функция, а <math>\Delta\ </math> – максимальная степень исходного графа [10]. | ||
Единичным диском называется диск с радиусом, равным единице. Граф единичных дисков ассоциирован с множеством единичных дисков на евклидовой плоскости. Каждая вершина является центром единичного диска. Между двумя вершинами u и v существует дуга в том и только том случае, если juvj < 1, где juvj – евклидово расстояние между u и v. Это означает, что две вершины u и v связаны дугой в том и только том случае, если диск вершины u покрывает v, а диск v покрывает u. | Единичным диском называется диск с радиусом, равным единице. Граф единичных дисков ассоциирован с множеством единичных дисков на евклидовой плоскости. Каждая вершина является центром единичного диска. Между двумя вершинами u и v существует дуга в том и только том случае, если juvj < 1, где juvj – евклидово расстояние между u и v. Это означает, что две вершины u и v связаны дугой в том и только том случае, если диск вершины u покрывает v, а диск v покрывает u. | ||