Jump to content

File:2SAT median graph.svg

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file (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
Source Own work
Author David Eppstein
Permission
(Reusing this file)
Public domain I, the copyright holder of this work, release this work into the public domain. This applies worldwide.
In some countries this may not be legally possible; if so:
I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

Detailed description

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.

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

2 May 2008

image/svg+xml

a77ea8773bcf16598d9a48aebad40f3d35e658e7

4,693 byte

468 pixel

747 pixel

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{{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 2 pages use this file:

Global file usage

The following other wikis use this file: