|
|
| (не показаны 3 промежуточные версии этого же участника) |
| Строка 2: |
Строка 2: |
| | число выполняющих наборов переменных для 3SAT задачи, равнялось бы шестикратному количеству раскрасок в три цвета. | | число выполняющих наборов переменных для 3SAT задачи, равнялось бы шестикратному количеству раскрасок в три цвета. |
| | | | |
| − | [[Category:На проверку]]
| |
| | | | |
| − | ==Стенин Сергей группа 974==
| + | <!--Вообще-то, решения уже есть--> |
| | | | |
| − | <m>
| + | [[Категория:Проблемные задачи]] |
| − | | + | |
| − | 1. Число раскрасок в 3 цвета кратно шести, так как перестановка цветов в правильной раскраске по-прежнему является правильной раскраской, а всего таких перестановок $3! = 6$.
| + | |
| − | | + | |
| − | 2. Пусть нам дана КНФ из $m$ дизъюнкций с $n$ переменными. Построим граф, соответствующий этой КНФ, следующим образом. Число вершин в нем будет равно $|V| = 7m + 2n + 3$. Для описания того, как граф устроен, пометим часть вершин. Три вершины пометим числами $0,1,2$. Каждым литералом ($x_i$ и $\overline{x_i}$) пометим еще по одной вершине. Остальные $7m$ вершин разобьем на группы по 7 штук, одна группа будет соответствовать одной дизъюнкции.
| + | |
| − | | + | |
| − | 3. Теперь расставим в графе ребра. Вершины $0,1,2$ соединим между собой ребрами. Для каждой $x_i$ соединим $x_i$, $\overline{x_i}$ и вершину $2$ в треугольник.
| + | |
| − | | + | |
| − | </m>
| + | |
| − | | + | |
| − | [[Файл:2014-11-23 20-59-35 Скриншот экрана.png|обрамить|центр|Добавление ребер в граф]] | + | |
| − | | + | |
| − | <m>
| + | |
| − | | + | |
| − | Для каждого дизъюнкта для литералов $l_1, l_2, l_3$, входящих в этот дизъюнкт, добавим к вершинам, соответствующим текущему дизъюнкту, ребра так, как показано на рисунке в. При этом некоторые ребра мы перечислили по нескольку раз.
| + | |
| − | | + | |
| − | Очевидно, что описанное построение можно выполнить за полиномиальное время от $n$ и $m$. Теперь надо доказать корректность.
| + | |
| − | | + | |
| − | 4. Рассмотрим правильные покраски в 3 цвета для полученного графа. Будем считать, что мы из шести возможных перестановок трех цветов зафиксировали какую-то одну. Поэтому без ограничения общности, пусть вершины $0,1,2$ покрашены в цвета $0,1,2$. Тогда вершины $x_i$ и $\overline{x_i}$ покрашены в цвета $0$ и $1$, причем в разные. Для графа на рисунке (в) прямым перебором проверяется, что выполнено следующее свойство. Если покрасить вершины, соответствующие литералам в дизъюнкции в цвет $0$ или $1$, а отрицания литералов - в противоположные цвета, то есть в $1$ или $0$, то правильная раскраска графа в три цвета существует и единственна тогда и только тогда, когда хотя бы одно из значений литералов отлично от нуля.
| + | |
| − | | + | |
| − | Таки образом, показано, что правильные раскраски графа в три цвета так, что вершинам $0,1,2$ соответствуют цвета $0,1,2$, находятся во взаимно однозначном соответствии с выполняющими наборами 3-КНФ, при этом, в силу наличия шести перестановок трех цветов, число выполняющих наборов для 3-КНФ равно шестикратному количеству раскрасок в три цвета.
| + | |
| − | | + | |
| − | </m>
| + | |