В задаче РАСКРАСКА дан граф \(G=(V,E)\) и число \(k\). Требуется определить, существует ли правильная раскраска вершин в \(k\) цветов, то есть функция \(\varphi:V\to\{1,\ldots,k\}\), для которой концы каждого ребра имеют разные цвета. Задача принадлежит
В курсе NP-трудность доказывается сведением 3-SAT к COLORING. Для 3-КНФ от \(n\) переменных строится граф с \(3n+t\) вершинами, где \(t\) — число скобок, и проверяется раскрашиваемость в \(n+1\) цветов. Специальный цвет кодирует выбранные значения
Что важно запомнить
- Сертификат — раскраска вершин. Правильность проверяется по всем рёбрам за полиномиальное время.
- В кафедральном сведении из 3-SAT используется \(n+1\) цветов, а не фиксированные три
- Для каждой переменной создаются вершины \(x_i\), \(\neg x_i\) и опорная вершина \(v_i\). Для каждой скобки создаётся вершина \(C_j\).
- Вершины \(v_1,\ldots,v_n\) образуют \(K_n\). Дополнительный цвет становится «специальным» и кодирует выбор истинностных значений.
- Вершину скобки можно раскрасить без нового цвета ровно тогда, когда соответствующая скобка содержит истинный литерал.
Конструкция графа
Пусть \(K=C_1\wedge\cdots\wedge C_t\) — 3-КНФ от переменных \(x_1,\ldots,x_n\), \(n\ge4\). Строят вершины \(x_i,\neg x_i,v_i\) для каждого \(i\) и вершину \(C_j\) для каждой скобки. Всего получается \(3n+t\)
Рёбра задают так:
- все \(v_i\) попарно соединены;
- \(v_i\) соединена с \(x_j\) и \(\neg x_j\) при \(i\ne j\);
- \(x_i\) соединена с \(\neg x_i\);
- вершина \(C_j\) соединяется с вершиной литерала, если этот литерал не входит в скобку \(C_j\).
Полный граф на вершинах \(v_i\) требует \(n\) разных цветов. Каждая пара \(x_i,\neg x_i\) может использовать только цвет \(v_i\) и ещё один, специальный цвет, причём эти две вершины должны получить разные цвета. Поэтому специальный цвет выбирает один из двух противоположных литералов и тем самым кодирует присваивание
Почему раскраска эквивалентна выполнимости
Вершина \(C_j\) не может использовать специальный цвет. Чтобы раскрасить её одним из уже имеющихся \(n\) цветов, должен существовать литерал \(y\in C_j\), чей противоположный литерал получил специальный цвет. Это означает, что \(y\) истинен при закодированном присваивании. Следовательно, все вершины скобок раскрашиваются в \(n+1\) цветов ровно тогда, когда каждая скобка содержит истинный литерал, то есть КНФ
Граф строится за полиномиальное время. Поэтому \(3\text{-SAT}\prec COLORING\), а вместе с \(COLORING\in NP\) получаем NP-полноту.
Пример простыми словами
Полезный способ читать конструкцию: для каждой пары \(x_i,\neg x_i\) ровно одна вершина вынужденно получает специальный \((n+1)\)-й цвет, и этот выбор кодирует значение переменной. Вершина скобки \(C_j\) специальный цвет использовать не может; она получает один из цветов \(v_i\) только тогда, когда в \(C_j\) есть литерал, совместимый с закодированным присваиванием. Поэтому вершины всех скобок удаётся раскрасить тогда и только тогда, когда исходная 3-КНФ выполнима.
Частые ошибки
- Подменять кафедральное доказательство классическим сведением к 3-COLORING. В данном Source строится экземпляр с \(k=n+1\).
- Забывать, что вершина скобки соединяется именно с литералами, не входящими в эту скобку. Это обеспечивает нужное условие на доступный цвет.
- Считать, что специальный цвет сам обозначает «истина». В конструкции Source значение восстанавливается через то, какой из пары противоположных литералов получил специальный цвет.
