24
правки
Изменения
2SAT
,Добавлены примеры решения 2-SAT
Компоненты сильной связности найдем за <tex>O(N + M)</tex>, затем проверим каждую из <tex>N</tex> переменных за <tex>O(N)</tex>. Следовательно асимптотика <tex>O(N + M)</tex>
== Примеры решения 2-SAT ==
=== Первый пример ===
Рассмотрим следующую функцию: <tex> (a \vee b) \wedge
(a \vee c) \wedge
(\overline b \vee c) \wedge
(\overline b \vee a) </tex>
Данная функция эквивалентна функции
<tex>
\overline a \to b \wedge
\overline b \to a \wedge
\overline a \to c \wedge
\overline c \to a \wedge
b \to c \wedge
\overline c \to \overline b \wedge
\overline a \to \overline b \wedge
a \to b
</tex>
Построим граф и рассмотрим пути:
* <tex> \overline a \to b \to a </tex>
* <tex> \overline a \to \overline b \to a </tex>
* <tex> \overline c \to a </tex>
* <tex> a \to c </tex>
* <tex> \overline a \to b \to c </tex>
Т.к. <tex> \overline a \to a </tex>, то <tex> a = 1, \overline a = 0 </tex>
Т.к. <tex> a \to c </tex> и <tex> a = 1 </tex>, то <tex> c = 1, \overline c = 0 </tex>
Значения <tex> b </tex> может быть любым, т.к. все вершины, из которых можно добраться в <tex> b </tex> имеют значение ноль
<b> Ответ: </b> <tex> a = 1, b = 0, c = 1 </tex> или <tex> a = 1, b = 1, c = 1 </tex>
=== Второй пример ===
Рассмотрим следующую функцию:
<tex>
(\overline a \vee c) \wedge
(\overline c \vee \overline a) \wedge
(a \vee b) \wedge
(\overline b \vee a)
</tex>
Данная функция эквивалентна функции
<tex>
a \to c \wedge
\overline c \to \overline a \wedge
c \to \overline a \wedge
a \to \overline c \wedge
\overline a \to b \wedge
\overline b \to a \wedge
b \to a \wedge
\overline b \to \overline a
</tex>
Заметим следующий путь: <tex> a \to c \to \overline a \to b \to a </tex>
Отсюда следует, что <tex> a \to \overline a \to a </tex>
Следовательно по ранее доказанной теореме, у данной функции решений нет
<b> Ответ: </b> Решений нет
== Использование 2-SAT ==
