4551
правка
Связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Связное доминирующее множество (посмотреть исходный код)
Версия от 13:50, 22 января 2013
, 22 января 2013→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «Связное доминирующее множество (Connected_dominating_set) Ключевые слова и синонимы: [[техники разб…») |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим граф G = (V, E). Множество C множества V называется доминирующим множеством, если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется связным доминирующим множеством. Связное доминирующее множество минимальной мощности называется минимальным связным доминирующим множеством (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности | Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется ''связным доминирующим множеством''. Связное доминирующее множество минимальной мощности называется ''минимальным связным доминирующим множеством'' (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ H(\Delta\ )</math> для <math>\rho\ < 1</math>, за исключением случая NP С DTIME(nO(lnlnn)), где H – гармоническая функция, а Л – максимальная степень исходного графа [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. | ||