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

Определим

N уг = N макс.

Если равен то переходим к этапу 12.

Иначе увеличиваем N уг, допустим, на 1 и переходим к этапу 3.

Этап12.

Анализ полученного результата.

Оценка полученного решения.

Если не удовлетворяет то уточняем N уг и N макс.

Переходим к этапу 2.

Иначе заканчиваем работу.

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

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

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

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

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

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

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

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.