Всего за 80 руб. Купить полную версию
Или подмножество вершин по четыре во множества подмножеств по восемь или семь.
В полном соответствии с правилами русского метода, указанными в задаче коммивояжера.
Определим число входов в вершину графа рёбер графа для данного множества подмножеств по пять, или шесть, или семь, или восемь, в зависимости от условий задачи, которые запомним для этого множества подмножеств.
Определим, получен ли искомый результат или нет.
Если получен, то заканчиваем поиск.
Переход к этапу12.
Иначе переходим к следующему этапу.
Этап11.
Данную процедуру повторяем, пока число вершин в подмножествах не сравняются с числом вершин графа. Так, как осуществляется эта процедура, примерно, в задаче коммивояжера русским методом.
Определим
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) путём просмотра всех подмножеств вершин.