Изменения

Пусть задана булева формула в <math>3-SAT</math>, в которой <math>k</math> скобок. Построим для нее соответствующий граф. Для каждой скобки нарисуем три вершины, соединим их попарно ребрами и подпишем их именами соответствующих переменных. При этом если переменная входит в формулу с отрицанием, отобразим это в графе. Так же соединим ребрами пары вершин вида <math>x,\overline{x}</math>.