Главное меню

Вход на сайт

Кто на сайте?

Сейчас 185 гостей и ни одного зарегистрированного пользователя на сайте

В заданном графе G = (X, V) (рис. 1) удалить указанные ребра (дуги) и новом графе G' найти все минимальные доминирующие множества (МДМ).
Ребро (дуга), которую необходимо удалить (Х4,Х5), (Х1,Х2)
Image

Решение

Image

Описываем каждую вершину с помощью дизъюнкции самой вершины и вершин, из которых она достижима. Например для Image и составим конъюнкцию таких выражений для всех вершин.
Image
Таким образом МДМ1 = {Х2, Х5}, МДМ2 = {Х3}, МДМ3 = {Х6}.

У Вас недостаточно прав для добавления комментариев.
Вам необходимо зарегистрироваться на сайте