4. Приближенные алгоритмы раскрашивания

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

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

В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней.

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

Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин

после окраски каждой очередной вершины: оставшиеся неокрашенные вершины записываются в порядке невозрастания их «относительных» степеней, т. е. степеней в таком графе, который получается из данного после удаления окрашенных вершин (вместе с ребрами, инцидентными удаленным вершинам).

В этой процедуре молчаливо предполагалось, что если две вершины имеют одинаковые степени, то их взаимное положение в списке случайно. В таких ситуациях уточнение в размещении вершин можно осуществлять с помощью двухшаговых степеней вершин имеющих одинаковые степени (одинаковые -шаговые степени), где определяется как число маршрутов длины 2, исходящих из Эти вершины могут быть размещены тогда в соответствии с величинами степеней Если все-таки найдутся вершины, у которых совпадают и степени и степени то можно вычислить трехшаговые степени (определяемые аналогичным образом) и разместить вершины с учетом степеней

Можно действовать иначе: размещать вершины сразу в соответствии с их степенями или степенями и применять тот же самый последовательный метод раскраски [24]. Таким образом, описанный выше метод раскрашивания очерчивает целый класс последовательных методов, каждый из которых связан с определенным способом упорядочивания вершин, либо статическим, т. е. фиксированным сразу для всей процедуры, либо динамическим, т. е. изменяющимся в процессе раскраски. Способ упорядочивания может базироваться на многих возможных критериях, зависящих от степеней вершин или от каких-либо других родственных характеристик. Результаты вычислений и сравнение последовательных методов раскрашивания для графов, выбранных случайным образом, приведены в работах Матулы, Марбле и Исааксона [16] и Вильямса [24]. Границы применимости этих эвристических методов демонстрируются у Митчема [17], показавшего, что можно построить графы, для которых любой из эвристических методов дает произвольно плохие оценки хроматического числа.