- Подробности
- Автор: Super User
- Категория: Теория графов
- Просмотров: 4766
В заданном графе G = (X, V) (рис. 1) удалить указанные ребра (дуги) и новом графе G' найти все максимальные независимые множества (МНМ).
Ребро (дуга), которую необходимо удалить (Х4,Х5), (Х1,Х2)
Решение

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

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


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

Решение

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

Получим

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


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