Расширение предварительной окраски - Precoloring extension
В теория графов, расширение предварительной окраски проблема расширения раскраска графика подмножества вершин графа с заданным набором цветов к раскраске всего графа, которая не присваивает одинаковый цвет любым двум смежным вершинам.
Сложность
Расширение предварительной раскраски имеет обычную проблему раскраски графа как частный случай, когда первоначально раскрашенное подмножество вершин пусто; следовательно, это НП-полный Однако он также является NP-полным для некоторых других классов графов, на которых обычная задача раскраски графов проще. Например, он NP-полный на графики ладьи, для чего соответствует задаче заполнения частично заполненного Латинский квадрат.[1]
Проблема может быть решена в полиномиальное время для графов ограниченных ширина дерева, но показатель степени полинома зависит от ширины дерева.[2][3]Это может быть решено за линейное время для экземпляров расширения предварительного раскрашивания, в которых ограничены как количество цветов, так и ширина дерева.[2]
Связанные проблемы
Расширение Precoloring можно рассматривать как частный случай раскраска списка, проблема раскраски графа, в котором не были раскрашены вершины, но каждой вершине назначен список доступных цветов. Чтобы преобразовать задачу расширения предварительного окрашивания в задачу раскраски списка, назначьте каждой неокрашенной вершине в задаче расширения предварительного окрашивания список цвета, которые еще не использовались его первоначально окрашенными соседями, а затем удалите цветные вершины из графа.
Судоку головоломки могут быть смоделированы математически как примеры задачи расширения предварительного окрашивания на Судоку графики.[4][5]
Рекомендации
- ^ Колборн, Чарльз Дж. (1984), "Сложность завершения частичных латинских квадратов", Дискретная прикладная математика, 8 (1): 25–30, Дои:10.1016 / 0166-218X (84) 90075-1, МИСТЕР 0739595.
- ^ а б Янсен, Клаус; Шеффлер, Петра (1997), "Обобщенная раскраска древовидных графов", Дискретная прикладная математика, 75 (2): 135–155, Дои:10.1016 / S0166-218X (96) 00085-6, МИСТЕР 1451958
- ^ Товарищи, Майкл Р.; Фомин, Федор В .; Локштанов Даниил; Розамонд, Фрэнсис; Саураб, Сакет; Шейдер, Стефан; Томассен, Карстен (2011), «О сложности некоторых красочных задач, параметризованных шириной дерева», Информация и вычисления, 209 (2): 143–153, Дои:10.1016 / j.ic.2010.11.026, МИСТЕР 2790022
- ^ Герцберг, Агнес М.; Мурти, М. Рам (2007), «Квадраты судоку и хроматические многочлены», Уведомления Американского математического общества, 54 (6): 708–717, МИСТЕР 2327972
- ^ Розенхаус, Джейсон; Таалман, Лаура (2011), Серьезно относиться к судоку: математика, лежащая в основе самой популярной в мире головоломки с карандашом, Oxford University Press, стр. 130
внешняя ссылка
- Библиография по расширению предварительной окраски, Даниэль Маркс