3.4. Алгоритм прямого неявного перебора, использующий дерево поиска

Для определения хроматического числа графа может быть использован с поразительной эффективностью очень простой метод неявного перебора, не содержащий никаких хитростей [4, 9]. Метод состоит в следующем.

Предположим, что множество вершин как-то упорядочено и вершина этого множества. Тогда первоначальная допустимая раскраска может быть получена так:

(i) окрасить в цвет 1.

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

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

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

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

Если или нет другого допустимого цвета (см. ниже замечание то можно сразу же делать шаг возвращения из вершины Алгоритм заканчивает работу, когда на шаге возвращения достигается вершина

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

(а) При любом упорядочении вершин допустимые цвета для вершины удовлетворяют условию (если Это очевидно, так как вершине предшествуют (при данном упорядочении) только вершин и, следовательно, никакой цвет не использовался. Таким образом, для вершины допустимым является только цвет 1, для цвет 1 и цвет 2 (если смежна с то для допустим только цвет 2) и

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

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