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

Для определения хроматического числа графа может быть использован достаточно эффективно простой метод неявного перебора.

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

1. Окрасить x_i в цвет 1.

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

Данный алгоритм можно ускорить, используя следующие замечания:

1. При любом упорядочении вершин допустимые цвета j для вершины x_i удовлетворяют условию j≤i.

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