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


Решение



Описываем каждое ребро (дугу) дизъюнкцией отрицаний и производим конъюнкцию всех дизъюнкций. Например ребро (Х2, Х1) описываем как  и т.д.
Получим

Производим упрощение.


Откуда из первой группы следует:
МНМ1 = {Х3}, МНМ2 = {Х6}, МНМ3 = {Х1, Х5}, МНМ4 = { Х1, Х4}.