Алгоритм Чейтина-Бриггса

Некоторые связанные понятия

Хроматическое число — наименьшее число красок, в которое может быть раскрашен граф.

Задача о раскраске графа. Раскрасить вершины графа в наименьшее число красок так, чтобы никакие смежные вершины не были покрашены в один цвет.

Алгоритм

Это древовидный алгоритм для задачи о раскраске графа.

Он имеет несколько пунктов. <xh4> 1. Проверка полноты графа </xh4>

Если граф полный
    хроматическое число графа = число вершин
Если граф имеет полный подграф
    хроматическое число графа >= число вершин полного подграфа

<xh4> 2. Выбрасывание вершин </xh4> Обозначим через p(x) степень вершины x.

Если хотим проверить, что m красок хватит для раскраски графа, можем воспользоваться следующим алгоритмом:

1. Если в графе есть вершина x | p(x) < m
       выбросить ее из графа вместе со смежными ребрами
       (если m красок хватит для раскраски полученного графа, то и для исходного хватит)
   иначе 
       применить какой-нибудь из известных алгоритмов для оставшегося графа
2. Перейти к шагу 1