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

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

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

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

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

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