Image:Implication graph.svg

From Wikipedia, the free encyclopedia

Implication_graph.svg‎ (SVG file, nominally 612 × 323 pixels, file size: 10 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

An implication graph
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 replacing each disjunction by the two implications to which it is equivalent, e.g.,

\scriptstyle(x_0\lor\lnot x_3) \equiv (\lnot x_0\Rightarrow\lnot x_3) \equiv (x_3\Rightarrow x_0),

and then representing the implications graphically as directed edges in a graph.

The solution set for the same example instance is depicted in Image:2SAT median graph.svg.

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeDimensionsUserComment
current22:21, 2 May 2008612×323 (10 KB)David Eppstein (Fix subscript)
22:17, 2 May 2008612×323 (10 KB)David Eppstein ({{Information |Description=An implication graph |Source=self-made |Date=May 2, 2008 |Author= David Eppstein |Permission={{PD-self}} |other_versions= }} Category:Graphs (graph theory) [[Category:Files b)
The following pages on the English Wikipedia link to this file (pages on other projects are not listed):