File:2SAT median graph.svg

From Wikimedia Commons, the free media repository

Jump to: navigation, search

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

Description

A median graph representing the set of solutions to a 2-satisfiability instance
Date

2 May 2008(2008-05-02)
Source

Own work
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 | Azərbaycan | Беларуская (тарашкевіца) | Български | Català | Cebuano | Soranî / کوردی | Česky | Cymraeg | Dansk | Deutsch | Ελληνικά | English | Esperanto | Español | Eesti | Euskara | Estremeñu | فارسی | Suomi | Français | Galego | עברית | हिन्दी | Hrvatski | Magyar | Հայերեն | Bahasa Indonesia | Ido | Íslenska | Italiano | 日本語 | ქართული | ភាសាខ្មែរ | 한국어 | Ripoarisch | Kurdî / كوردی | Latina | Lietuvių | Latviešu | 文言 | Македонски | Bahasa Melayu | Plattdüütsch | Nederlands | ‪Norsk (nynorsk)‬ | ‪Norsk (bokmål)‬ | Polski | Português | Română | Русский | Slovenčina | Slovenščina | Shqip | Српски / Srpski | Svenska | ไทย | Tagalog | Türkçe | Українська | Vèneto | Tiếng Việt | Walon | 吴语 | 中文 | ‪中文(简体)‬ | ‪中文(繁體)‬ | 粵語 | +/−

[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/TimeThumbnailDimensionsUserComment
current22:17, 2 May 2008Thumbnail for version as of 22:17, 2 May 2008747×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)

The following page on Wikimedia Commons links to this file. Some pages on other Wikimedia projects may also link to it.

Global file usage

The following other wikis use this file:

Retrieved from "http://commons.wikimedia.org/wiki/File:2SAT_median_graph.svg"