Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина. Геннадий Степанов

теории графов доминирующее множество для графаG = (V, E) – это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D.

      Число доминирования γ (G) – это число вершин в наименьшем доминирующем множестве G.

      Задача о доминирующем множестве заключается в проверке, верно ли неравенство γ (G) ≤ K для заданного графа G и числа K.

      Задача является классической NP- полной проблемой разрешимости в теории вычислительной сложности.

      Таким образом, в настоящее время полагают, что не существует эффективного алгоритма для нахождения наименьшего доминирующего множества для заданного графа.

      Точные алгоритмы

      Минимальное доминирующее множество графа с nвершинами может быть найдено за время O (2nn) путём просмотра всех подмножеств вершин.