DescriptionImplication graph.svg	An implication graph
Date	2 mai 2008
Source	Travail personnel
Auteur	David Eppstein
Autorisation (Réutilisation de ce fichier)	Public domainPublic domainfalsefalse Moi, propriétaire des droits d’auteur sur cette œuvre, la place dans le domaine public. Ceci s'applique dans le monde entier. Dans certains pays, ceci peut ne pas être possible ; dans ce cas : J’accorde à toute personne le droit d’utiliser cette œuvre dans n’importe quel but, sans aucune condition, sauf celles requises par la loi.

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.