File:2SAT median graph.svg
![File:2SAT median graph.svg](https://upload.wikimedia.org/wikipedia/commons/thumb/d/df/2SAT_median_graph.svg/747px-2SAT_median_graph.svg.png?20080502221718)
Original file (SVG file, nominally 747 × 468 pixels, file size: 5 KB)
Captions
Captions
Description2SAT median graph.svg | A median graph representing the set of solutions to a 2-satisfiability instance | |||
Date | ||||
Source | Own work | |||
Author | David Eppstein | |||
Permission (Reusing this file) |
|
Detailed description
[edit]This graph is formed from the 2-satisfiability instance
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.
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 22:17, 2 May 2008 | ![]() | 747 × 468 (5 KB) | David Eppstein (talk | contribs) | {{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 |
You cannot overwrite this file.
File usage on Commons
The following page uses this file:
File usage on other wikis
The following other wikis use this file:
- Usage on en.wikipedia.org
- Usage on it.wikipedia.org
- Usage on ru.wikipedia.org
- Usage on uk.wikipedia.org