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

Алгоритм строит допустимую раскраску, применяя …………: начинать раскраску следует с вершин наибольшей степени, поскольку , если их раскрашивать в конце процесса, то более вероятно, что для них не найдётся свободного цвета и придется задействовать ещё 1 цвет.

Вход: граф G

Выход: раскраска графа –массив С:

……..of 1….P

Sort (V) (упорядочить вершины по возрастанию степени)

С:=1( первый цвет)

For do

Cвсе не раскрашены

End for

White Vdo

For do

For

If C(U)= C then

Next for V (вершину V нельзя окрасить в цвет С)

End if

End for

C…… вершину V в цвет С

V: = (удалям её из раскрашивания)

С: = С+1 (следующий цвет)