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