Расширение предварительной окраски - Precoloring extension

В теория графов, расширение предварительной окраски проблема расширения раскраска графика подмножества вершин графа с заданным набором цветов к раскраске всего графа, которая не присваивает одинаковый цвет любым двум смежным вершинам.

Сложность

Расширение предварительной раскраски имеет обычную проблему раскраски графа как частный случай, когда первоначально раскрашенное подмножество вершин пусто; следовательно, это НП-полный Однако он также является NP-полным для некоторых других классов графов, на которых обычная задача раскраски графов проще. Например, он NP-полный на графики ладьи, для чего соответствует задаче заполнения частично заполненного Латинский квадрат.[1]

Проблема может быть решена в полиномиальное время для графов ограниченных ширина дерева, но показатель степени полинома зависит от ширины дерева.[2][3]Это может быть решено за линейное время для экземпляров расширения предварительного раскрашивания, в которых ограничены как количество цветов, так и ширина дерева.[2]

Связанные проблемы

Расширение Precoloring можно рассматривать как частный случай раскраска списка, проблема раскраски графа, в котором не были раскрашены вершины, но каждой вершине назначен список доступных цветов. Чтобы преобразовать задачу расширения предварительного окрашивания в задачу раскраски списка, назначьте каждой неокрашенной вершине в задаче расширения предварительного окрашивания список цвета, которые еще не использовались его первоначально окрашенными соседями, а затем удалите цветные вершины из графа.

Судоку головоломки могут быть смоделированы математически как примеры задачи расширения предварительного окрашивания на Судоку графики.[4][5]

Рекомендации

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

внешняя ссылка