DescrizioneImplication graph.svg	An implication graph
Data	2 maggio 2008
Fonte	Opera propria
Autore	David Eppstein
Licenza (Riusare questo file)	Public domainPublic domainfalsefalse Io, detentore del copyright su quest'opera, la rilascio nel pubblico dominio. Questa norma si applica in tutto il mondo. In alcuni paesi questo potrebbe non essere legalmente possibile. In tal caso: Garantisco a chiunque il diritto di utilizzare quest'opera per qualsiasi scopo, senza alcuna condizione, a meno che tali condizioni siano richieste dalla legge.

Detailed description

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.