4551
правка
Точные алгоритмы построения доминирующего множества: различия между версиями
Перейти к навигации
Перейти к поиску
Точные алгоритмы построения доминирующего множества (посмотреть исходный код)
Версия от 13:16, 2 февраля 2014
, 2 февраля 2014→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
'''Определение 1'''. Пусть задан простой неориентированный граф G = (V, E). Подмножество вершин <math>D \subseteq V</math> называется [[доминирующее множество|доминирующим множеством]], если каждая вершина <math>u \in V</math> — <math>D \; </math> имеет соседа в D. Задача построения минимального доминирующего множества (minimum dominating set, MDS) заключается в поиске минимального доминирующего множества графа G, т.е. доминирующего множества G с минимальной мощностью. | '''Определение 1'''. Пусть задан простой неориентированный граф G = (V, E). Подмножество вершин <math>D \subseteq V</math> называется [[доминирующее множество|доминирующим множеством]], если каждая вершина <math>u \in V</math> — <math>D \; </math> имеет соседа в D. Задача построения минимального доминирующего множества (minimum dominating set, MDS) заключается в поиске [[минимальное доминирующее множество|минимального доминирующего множества]] графа G, т.е. доминирующего множества G с минимальной [[мощность|мощностью]]. | ||
Задача 1 (минимальное доминирующее множество, MDS) | '''Задача 1 (минимальное доминирующее множество, MDS)''' | ||
Дано: простой неориентированный граф G = (V, E). | |||
Требуется: найти минимальное доминирующее множество D графа G. | |||
Представляют интерес различные модификации задачи построения доминирующего множества; некоторые из них были получены посредством накладывания дополнительных ограничений на доминирующее множество – к примеру, оно может быть независимым или связным. В теории графов проблеме доминирования и множеству ее модификаций посвящен обширный список работ (см., например, [9]). В контексте графовых алгоритмов задача построения минимального доминирующего множества и некоторых его модификаций (таких как независимое доминирующее множество или связное доминирующее множество) рассматривается как типовая для решения NP-полных задач с использованием различных алгоритмических подходов. | Представляют интерес различные модификации задачи построения доминирующего множества; некоторые из них были получены посредством накладывания дополнительных ограничений на доминирующее множество – к примеру, оно может быть независимым или связным. В теории графов проблеме доминирования и множеству ее модификаций посвящен обширный список работ (см., например, [9]). В контексте графовых алгоритмов задача построения минимального доминирующего множества и некоторых его модификаций (таких как независимое доминирующее множество или связное доминирующее множество) рассматривается как типовая для решения NP-полных задач с использованием различных алгоритмических подходов. | ||