Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина. Геннадий Степанов
Читать онлайн книгу.
target="_blank" rel="nofollow" href="https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2">теории графов доминирующее множество для графаG = (V, E) – это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D.
Число доминирования γ (G) – это число вершин в наименьшем доминирующем множестве G.
Задача о доминирующем множестве заключается в проверке, верно ли неравенство γ (G) ≤ K для заданного графа G и числа K.
Задача является классической NP- полной проблемой разрешимости в теории вычислительной сложности.
Таким образом, в настоящее время полагают, что не существует эффективного алгоритма для нахождения наименьшего доминирующего множества для заданного графа.
Точные алгоритмы
Минимальное доминирующее множество графа с nвершинами может быть найдено за время O (2nn) путём просмотра всех подмножеств вершин.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.