3.7 Алгоритм прямого неявного перебора

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

1. окрасить v₁ в цвет 1;

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

Опишем последующие шаги алгоритма согласно монографии.

Пусть q - число цветов, требуемое для вышеупомянутой раскраски. Если существует раскраска, использующая только q-1 цветов, то все вершины, окрашенные в цвет q, должны быть перекрашены в цвет j<q. Пусть v_i* - первая вершина при заданном упорядочении, которая была окрашена в цвет q. Поскольку она была так окрашена потому, что не могла быть окрашена в цвет j<q, то ее можно перекрасить в цвет j. Итак, шаг возвращения из вершины v_i* можно осуществить следующим образом. Из смежных с v_i* вершин в множестве {x₁, x₂, ..., x_i*-1} найти последнюю (при заданном упорядочении), т.е. вершину с наибольшим индексом. Пусть это будет вершина x_k. Если x_k окрашена в цвет j_k, то x_k перекрашивается в другой допустимый цвет с наименьшим возможным "номером" j_k', таким, что j_k' >= j_k+1.

Если j_k'<q, то надо продолжать последовательно перекрашивать все вершины с x_k+1 до x_n, применяя указанное выше правило 2 и помня о том, что цвет q использовать нельзя.

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

Если j_k'=q или нет другого допустимого цвета j_k', то можно сразу же делать шаг возвращения из вершины x_k.

Алгоритм заканчивает работу, когда на шаге возвращения достигается вершина x₁.

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