DescripciónImplication graph.svg	An implication graph
Fecha	2 de mayo de 2008
Fuente	Trabajo propio
Autor	David Eppstein
Permiso (Reutilización de este archivo)	Public domainPublic domainfalsefalse Yo, el titular de los derechos de autor de esta obra, lo libero al dominio público. Esto aplica en todo el mundo. En algunos países esto puede no ser legalmente factible; si ello ocurriese: Concedo a cualquier persona el derecho de usar este trabajo para cualquier propósito, sin ningún tipo de condición al menos que éstas sean requeridas por la ley.

This graph is formed from the 2-satisfiability instance

${\displaystyle \scriptstyle (x_{0}\lor x_{2})\land (x_{0}\lor \lnot x_{3})\land (x_{1}\lor \lnot x_{3})\land (x_{1}\lor \lnot x_{4})\land (x_{2}\lor \lnot x_{4})\land {} \atop \scriptstyle \quad (x_{0}\lor \lnot x_{5})\land (x_{1}\lor \lnot x_{5})\land (x_{2}\lor \lnot x_{5})\land (x_{3}\lor x_{6})\land (x_{4}\lor x_{6})\land (x_{5}\lor x_{6})}$

by replacing each disjunction by the two implications to which it is equivalent, e.g.,

${\displaystyle \scriptstyle (x_{0}\lor \lnot x_{3})\equiv (\lnot x_{0}\Rightarrow \lnot x_{3})\equiv (x_{3}\Rightarrow x_{0}),}$

and then representing the implications graphically as directed edges in a graph.

The solution set for the same example instance is depicted in Image:2SAT median graph.svg.