ОписаниеImplication graph.svg	An implication graph
Дата	2 мая 2008
Источник	Собственная работа
Автор	David Eppstein
Права (Повторное использование этого файла)	Public domainPublic domainfalsefalse Я, владелец авторских прав на это произведение, передаю его в общественное достояние. Это разрешение действует по всему миру. В некоторых странах это не может быть возможно юридически, в таком случае: Я даю право кому угодно использовать данное произведение в любых целях без каких-либо условий, за исключением таких условий, которые требуются по закону.

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.