Graph Theory37 sections · 1633 units
Open in Course

Edge Case - Contradiction

(Same topping opposite signs)

What if one customer wants +1+1 +1+1 and another wants 1-1 1-1?

First clause (x1lorx1)(x_1 lor x_1) gives: NOT x1ox1x_1 o x_1. Second clause (lnotx1lorlnotx1)(lnot x_1 lor lnot x_1) gives: x1ox_1 o NOT x1x_1. These 22 edges form a cycle: x1ox_1 o NOT x1ox1x_1 o x_1. The SCC contains both x1x_1 and NOT x1x_1. You can see the instance is unsatisfiable. Print IMPOSSIBLE. When a variable and its negation share an SCC, no valid assignment exists.