Алгоритм последовательной раскраски

Алгоритм последовательной раскраски графа в минимальное число цветов имеет следующий вид.

1. Упорядочить вершины графа в порядке не возрастания степеней.

2. Положить i=0.

3. Положить i=i+1.

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

5. Если все вершины графа окрашены, то перейти к п.6, иначе - к п.3.

6. Конец алгоритма.

Пример. Применим последовательный алгоритм для раскраски графа G, изображенного на рис. 7.1. Упорядочим его вершины от 1 до n.

G

Рис. 7.1. Граф G

В массиве А (рис. 7.2а) содержатся степени вершин графа G. Индекс массива соответствует номеру вершины.

В массиве В (рис. 7.2б) содержатся номера вершин графа G, упорядоченные по не возрастанию степеней.

Вершины массива В, раскрашенные 1-ой краской, отмечены в массиве С на рис. 7.2в.

Вершины массива В, раскрашенные 1-ой и 2-ой красками, находятся в массиве С на рис. 7.2г.

На рис.7.2д. в массиве С показана полная раскраска графа G.

степени вершин 4

а) массив степеней графа G

В

1 2 3 4 5 6 7 8 9

б) упорядочение вершин графа G по

не возрастанию степеней

С 1 2 3 4 5 6 7 8 9

в) раскраска вершин графа G

1-ой краской

С 1 2 3 4 5 6 7 8 9

г) раскраска вершин графа G

1-ой и 2-ой красками

С 1 2 3 4 5 6 7 8 9

д) полная раскраска вершин

графа G в три цвета

Рис. 7.2. Раскраска графа G последовательным алгоритмом

Легко видеть, что в данном алгоритме выполняются все вышеперечисленные правила. Основное из них заключается в том, что если вершина окрашена, то она уже не перекрашивается в другой цвет.