logo
лекции по МОТС / ДИСКРЕТНАЯ МАТЕМАТИКА Графы

12.3.3. Улучшенный алгоритм последовательного раскрашивания

Следующий алгоритм также строит допустимую раскраску, применяя такую эв­ристику: начинать раскрашивать следует с вершины наибольшей степени, по­скольку, если их раскрашивать в конце процесса, то более вероятно, что для них не найдется свободного цвета и придется задействовать еще один цвет.

Алгоритм 12.2. Улучшенный алгоритм последовательного раскрашивания Вход: граф G.

Выход: раскраска графа — массив С : array [i..p] of 1..p. Sort(v) { упорядочить вершины по невозрастанию степени } с: = 1 { первый цвет } for и 6 V do

C[v]: = 0 { все не раскрашены } end for

while V ф 0 do for v e V do for и е r+(v) do if C[u] = с then

next for v { вершину v нельзя покрасить в цвет с } end if end for

C[v] : = c { красим вершину v в цвет с } V : = V\ {v} { и удаляем ее из рассмотрения } end for

с: = с + 1 { следующий цвет } end while

обоснование

Заметим, что данный алгоритм отличается от предыдущего тем, что основной цикл идет не по вершинам, а по цветам: сначала все что можно красим в цвет 1, затем в оставшемся красим все что можно в цвет 2 и т. д. В остальном алго­ ритмы аналогичны, и данный алгоритм заканчивает свою работу построением допустимой раскраски по тем же причинам, что и предыдущий.

Комментарии

Центральный результат этой главы — теорема о пяти красках — изложен по книге [23]. Алгоритмы раскрашивания изложены по книге [11], в которой мож­но найти их более детальное и подробное обсуждение. Различные применения задачи о раскраске графов в программировании и смежные вопросы освещены в [5].

Упражнения

12.1. Доказать, что

12.2. Доказать, что если в планарном графе каждая грань есть Сп, то

= "(Р - 2) п-2

12.3. Построить примеры графов, для которых алгоритмы последовательного раскрашивания строят не минимальную раскраску.