Graph Theory37 sections · 1633 units
Open in Course

Implication Graphs

(Clauses become edges)

The trick: convert OR clauses into implications. An implication says "if this is true, then that must be true." it is a forced relationship. Build a directed graph where nodes are variables and their negations. Each clause becomes two edges showing implications between nodes.

This graph reveals which assignments are forced by others. If you set one variable, the edges show you what else must be true. SCCs in this graph determine satisfiability.