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

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

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

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

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

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

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

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