File:2SAT median graph.svg
Исходный файл (SVG-файл, номинально 747 × 468 пкс, размер файла: 5 КБ)
Краткие подписи
Описание2SAT median graph.svg | A median graph representing the set of solutions to a 2-satisfiability instance | |||
Дата | ||||
Источник | Собственная работа | |||
Автор | David Eppstein | |||
Права (Повторное использование этого файла) |
|
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.
История файла
Нажмите на дату/время, чтобы увидеть версию файла от того времени.
Дата/время | Миниатюра | Размеры | Участник | Примечание | |
---|---|---|---|---|---|
текущий | 22:17, 2 мая 2008 | 747 × 468 (5 КБ) | 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 |
Вы не можете перезаписать этот файл.
Использование файла
Следующая страница использует этот файл:
Глобальное использование файла
Данный файл используется в следующих вики:
- Использование в en.wikipedia.org
- Использование в it.wikipedia.org
- Использование в ru.wikipedia.org
- Использование в uk.wikipedia.org