эта процедура, примерно, в задаче коммивояжера русским методом.
Определим
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 (2nn) путём просмотра всех подмножеств вершин.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.
