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

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