хроматическое число графа

Ответ от Alexey Khoroshev[гуру]
Хроматический полином графа G – функция от числа цветов λ, использованных для раскраски
G. Значение хроматического полинома есть число возможных способов окраски G в λ цветов.
Херцберг (Herzberg) и Мёрти (Murty) доказали следующую важную теорему:
Теорема 3. Пусть G – конечный граф с v вершинами, C – частичная окраска его t вершин do
цветами, pG,C(λ) – количество возможностей полного (продолжающего C) окрашивания графа G с
использованием λ цветов. Тогда pG,C(λ) – многочлен (от λ) с целыми коэффициентами степени v-t
для λ≥ do.
Значение pG,C(9) должно быть равно 1, чтобы решение задачи (раскраска графа) было
единственным.
Примечание 8. Херцберг (Herzberg) и Мёрти (Murty) доказали, что для
единственности продолжения раскраски (решения) С необходимо, чтобы исходная задача судоку,
имела по меньшей мере 8 цветов (чисел) , то есть do ≥ 8.
Вычисление целых коэффициентов pG,C(9) может быть выполнено легко посредством анализа
индуктивного доказательства Теоремы 3
Доказательство по индукции основано на алгоритме частичного удаления (deletion-contraction).
Задача судоку в контексте математики может быть определена как проблема окраски вершин в
теории графов. Действительно, достаточно просто заменить множество [1..9] в задаче судоку
окраской в 9 различных цветов, и назвать доску судоку графом, а клетки – вершинами.
Следует оговорить надлежащим образом раскраску графа. Каждый из девяти цветов должен
появиться в каждых строке, столбце, боксе. Такого рода раскраска графа G называется его чистым
раскрашиванием. Минимальное количество цветов, потребных для чистого раскрашивания графа
G, называется хроматическим числом G. Для графа, связанного с судоку, разумеется,
хроматическое число равно 9.
Источник: