Дан граф G(X,U), где множество вершин X={x
1
,x
2
,x
3
,x
4
}, а множество рёбер U={(x
1
x
2
),(x
3
x
4
),(x
3
x
2
),(x
1
x
3
)}. Требуется найти минимальное выражение Π в виде дизъюнкции конъюнкций логических переменных x
1
,x
2
,x
3
,x
4
, которое описывает все максимальные пустые (независимые) подграфы графа G.
Для решения задачи о нахождении минимального выражения в виде дизъюнкции конъюнкций логических переменных, которое описывает все максимальные пустые (независимые) подграфы графа
У нас есть множество вершин:
И множество рёбер:
Независимый подграф — это подграф, в котором нет рёбер между любыми двумя вершинами. Мы должны найти все возможные комбинации вершин, которые не соединены рёб...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Не нашел нужную задачу?