Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Vertex-3-Coloring
Материал из DISCOPAL
< Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC | Полнота
Версия от 02:47, 3 марта 2022; StasFomin (обсуждение | вклад)
- Заголовок
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Vertex-3-Coloring
- Автор
- Стас Фомин
- Нижний колонтитул
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Полнота/Vertex-3-Coloring
- Дополнительный нижний колонтитул
- Стас Фомин, 06:39, 3 марта 2022
Содержание
Постановка.
Vertex Coloring.
Задача о раскраске вершин графа. Можно ли вершины неориентированного графа раскрасить в k цветов, так, чтобы соседние вершины имели разные цвета?
Vertex-3-Coloring.
Частный случай Vertex coloring для 3х цветов.
NP? .…
- ?
- Что будет сертификатом?
NP!.
Cертификат → собственно раскраска.
Кого сводим к ней?.…
- 3SAT
- m дизъюнкций
- n переменных.
Строим граф. …
- Три вершины → метки 0, 1, 2.
- Для каждого литерала по вершине → 2n.
- Для каждой дизъюнкции → 7 вершин → 7m.
- 3 + 2n + 7m вершин.
- a) → вершины 0, 1 и 2 соединены между собой ребрами.
- б) показаны еще n треугольников в этом графе.
- в) показывает, как соединены ребрами вершины, соответствующие каждой дизъюнкции. На этом рисунке l1,l2,l3 обозначают литералы, входящие в дизъюнкцию.
.…
Число раскрасок в 3 цвета кратно 6: перестановка цветов сохраняет правильную раскраску.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.