the correctness of 2-satisfiability problem algorithm by using implication graph
-
29-09-2020 - |
Question
I learned finding a solution of 2-sat problem algorithm below.
The point are below
(1) when constructing the implication graph
(2) finding there is no occurrence of a variable x and its negation x' in any SCC in the graph.
(3) then there is always the solution at this 2-SAT problem.
it means that all false 2-SAT problem have a variable x and its negation x' in SCC of its implication graph.
I cannot understand this point (3).
How can I prove it has a solution if only if there is no x and x' in a SCC?
It looks like to me, although there is no x and x' in SCC, it can be false.
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange