12.3.1. Точный алгоритм раскрашивания

Рассмотрим следующую схему рекурсивной процедуры Р:

Выбрать в графе G некоторое максимальное независимое множество вершин S.

Покрасить вершины множества S в очередной цвет.

Применить процедуру Р к графу G - S.

Вход: граф G(V, E), номер свободного цвета г.

Выход: раскраска, заданная массивом C[V], - номера цветов, приписанные вершинам.

if V = 0 then

return { раскраска закончена }

end if

S: = Selectmax(G) {S — максимальное независимое множество }

C[S]: = г { раскрашиваем вершины множества S в цвет г }

P(G — S, г + 1) { рекурсивный вызов }

ЗАМЕЧАНИЕ

Функция Selectmax может быть реализована, например, алгоритмом 11.2.4.

ТЕОРЕМА Если граф G k-раскрашиваемый, то существует такая последова­тельность выборов множества S на шаге 1 процедуры Р, что применение проце­дуры Р к графу G построит не более чем k-раскраску графа G.

доказательство

Пусть имеется некоторая fc-раскраска графа G(V,E). Перестроим ее в не более чем /с-раскраску, которая может быть получена процедурой Р. Пусть Vi с V • множество вершин в данной fc-раскраске, покрашенных в цвет 1. Множество Vj - независимое, но, может быть, не максимальное. Рассмотрим множество VJ/, та­ кое что Vi U V\ — максимальное независимое множество (может оказаться, что V\ = 0). Вершины из V/ не смежны с У_ь значит, вершины из У/ можно перекра­ сить в цвет 1. Пусть далее У₂ С V"\(V"i U Vi') — множество вершин, покрашенных в цвет 2. Аналогично рассмотрим множество У₂', такое что V₂ U У₂' — максималь­ ное независимое в G\(ViUVi')i покрасим вершины Vjj'U.Vj' в цвет 2 и т. д. Всего в исходной раскраске было k независимых множеств. При перекраске их число не возрастет (но может уменьшиться, если x(G) < k). На каждом шаге алгоритма рассматривается одно из множеств, следовательно, процесс закончится. D