3 ms·
The graph explanation is saying: The 'x1 or x2 or x3' node can't be blue (as you say, it's connected to a blue node!) It doesn't take too long to convince you
by CJefferson 2y ago
The graph explanation is saying:
The 'x1 or x2 or x3' node can't be blue (as you say, it's connected to a blue node!)
It doesn't take too long to convince yourself that if we coloured the right-hand node of x1, x2 and x3 all blue, there is no valid colouring of the 'clause 1' bit of the graph where the 'x1 or x2 or x3' node is not blue -- which means there is no colouring of the whole graph.
On the other hand, if I make at least one of the right-hand nodes of x1, x2 or x3 red, then I can colour the 'clause 1' bit of the graph such that the 'x1 or x2 or x3' node isn't blue, so all is fine!
They are trying to explain that this graph correctly represents the SAT problem, because it has a valid colouring if and only if the SAT problem has a solution -- and we do this by checking the clauses one at a time.
- jstanley 2y agoThanks.