Image:2SAT median graph.svg

From Wikipedia, the free encyclopedia

2SAT_median_graph.svg‎ (SVG file, nominally 747 × 468 pixels, file size: 5 KB)

Wikimedia Commons logo This is a file from the Wikimedia Commons. The description on its description page there is shown below.
Commons is a freely licensed media file repository. You can help.
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
(Reusing this image)
Public domain I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide.

In case this is not legally possible:
I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Afrikaans | Alemannisch | Aragonés | العربية | Asturianu | Български | Català | Česky | Cymraeg | Dansk | Deutsch | Eʋegbe | Ελληνικά | English | Español | Esperanto | Euskara | Estremeñu | فارسی | Français | Galego | 한국어 | हिन्दी | Hrvatski | Ido | Bahasa Indonesia | Íslenska | Italiano | עברית | Kurdî / كوردی | Latina | Lietuvių | Latviešu | Magyar | Македонски | Bahasa Melayu | Nederlands | ‪Norsk (bokmål)‬ | ‪Norsk (nynorsk)‬ | 日本語 | Polski | Português | Ripoarisch | Română | Русский | Shqip | Slovenčina | Slovenščina | Српски / Srpski | Svenska | ไทย | Tagalog | Türkçe | Українська | Tiếng Việt | Walon | ‪中文(简体)‬ | ‪中文(繁體)‬ | zh-yue-hant | +/-


[edit] Detailed description

This graph is formed from the 2-satisfiability instance

\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,

\scriptstyle x_0x_1x_2x_3x_4x_5x_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-satifiability 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/TimeDimensionsUserComment
current22:17, 2 May 2008747×468 (5 KB)David Eppstein ({{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)
The following pages on the English Wikipedia link to this file (pages on other projects are not listed):