Descripción2SAT median graph.svg	A median graph representing the set of solutions to a 2-satisfiability instance
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 x_{5})\land (x_{1}\lor x_{5})\land (x_{2}\lor x_{5})\land (x_{3}\lor x_{6})\land (x_{4}\lor x_{6})\land (x_{5}\lor x_{6})}$

by creating a vertex for each satisfying truth assignment to the formula and an edge between any two assignments that differ in the value of a single variable. The vertices in the drawing are labeled by the sequence of variable values,

${\displaystyle \scriptstyle x_{0}x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}.}$

In general, any 2-satisfiability instance has a set of solutions with the structure of a median graph, in which the median of any three solutions is formed by taking a majority vote separately for each variable's value. However, for some 2-satisfiability problems, the edges in this median graph may connect pairs of solutions that differ by simultanously flipping several variables that are forced by the instance to all be equal or unequal.