Меню Описание Сложность Листинг Пример
 

Алгоритм раскраски графа

Алгоритм раскраски графа позволяет находить (точное или приближенное) значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин.

Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G. Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.

Рассмотрим последовательный метод, основанный на упорядочивании множества вершин.

Формальное описание     [вверх]

Colourize(G)
1. Упорядочить вершины по невозрастанию степени.
2. Окрасить первую вершину в цвет 1.
3. Выбрать цвет окраски 1.
4. Пока не окрашены все вершины, повторять п.4.1.-4.2.:
   4.1. Окрасить в выбранный цвет всякую вершину, которая не смежна 
        с другой, уже окрашенной в этот цвет.
   4.2. Выбрать следущий цвет.

В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней. Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.

Приведенный выше алгоритм можно модифицировать. Для этого после каждого шага нужно упорядочивать неокрашенные вершины. Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин по невозрастанию их относительных степеней. Под относительными степенями понимаются степени соответствующих вершин в неокрашенном подграфе исходного графа.

В данной модификации предполагалось, что если две вершины имеют одинаковые степени, то порядок таких вершин случаен. Такие вершины можно также упорядочить, но уже по двухшаговым степеням. Двухшаговую степень определим как сумму относительных степеней инцидентных вершин. Аналогично можно поступать и далее.

Оценка сложности     [вверх]

Не учитывая время, затраченное на сортировку вершин в порядке невозрастания степеней, необходимо сделать цикл по всем вершинам графа. Для каждой необходимо найти минимальный цвет, что в худшем случае может занять o(V2) для случая с полным графом. Значит, общее время составит o(V3) в худшем случае.

Пример     [вверх]

Визуализатор алгоритма:

Примеры раскрасок графов


[вверх]

 
 
Хостинг от uCoz