Graph Theory37 sections · 1633 units
Open in Course

Section Recap

(What you learned)

You learned how to convert 22-SAT logic formulas into implication graphs. Each clause "a OR b" becomes two edges: NOT a → b and NOT b → a. You learned the satisfiability condition: no variable and its negation can share an SCC. If they do, the formula is unsatisfiable because assigning a value to the variable forces both it and its negation to be true.

You learned to construct valid assignments using SCC topological order. Choose true for the literal in the later SCC. This gives you a complete linear-time algorithm for 22-SAT. You practiced on Giant Pizza and scheduling problems.