Я, владелец авторских прав на это произведение, передаю его в общественное достояние. Это разрешение действует по всему миру. В некоторых странах это не может быть возможно юридически, в таком случае: Я даю право кому угодно использовать данное произведение в любых целях без каких-либо условий, за исключением таких условий, которые требуются по закону.
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,
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.
Краткие подписи
Добавьте однострочное описание того, что собой представляет этот файл
{{Information |Description=A median graph representing the set of solutions to a 2-satisfiability instance |Source=self-made |Date=May 2, 2008 |Author= David Eppstein |Permission={{PD-s