Главное меню

Вход на сайт

Кто на сайте?

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

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

Решение

Image

Описываем каждое ребро (дугу) дизъюнкцией отрицаний и производим конъюнкцию всех дизъюнкций. Например ребро (Х2, Х1) описываем как Image и т.д.
Получим
Image
Производим упрощение.
Image
Image
Откуда из первой группы следует:
МНМ1 = {Х3}, МНМ2 = {Х6}, МНМ3 = {Х1, Х5}, МНМ4 = { Х1, Х4}.

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