File:Implication graph.svg

From Wikipedia, the free encyclopedia

File
File history
File links

Implication_graph.svg‎ (SVG file, nominally 612 × 504 pixels, file size: 10 KB)

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

Date

2 May 2008(2008-05-02)

Source

Own work

Author

David Eppstein

Permission
(Reusing this image)

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.

[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 \lnot x_5)\land (x_1\lor\lnot x_5)\land (x_2\lor\lnot 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.

(latest | earliest) View (newer 50) (older 50) (20 | 50 | 100 | 250 | 500)

	Date/Time	Thumbnail	Dimensions	User	Comment
current	19:41, 29 November 2008		612×504 (10 KB)	David Eppstein	(Fix ~x6 vertex in new drawing)
	19:34, 29 November 2008		612×504 (10 KB)	David Eppstein	(Replace with new drawing to match modifications to 2SAT article)
	23:04, 3 August 2008		612×323 (10 KB)	David Eppstein	(Replace vertex names to match usage in articles)
	22:21, 2 May 2008		612×323 (10 KB)	David Eppstein	(Fix subscript)
	22:17, 2 May 2008		612×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)