Алгоритм Чейтина-Бриггса — различия между версиями

Текущая версия на 21:42, 28 января 2011

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

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

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

Алгоритм

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

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

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

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

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

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

<xh4> 3. Поиск раскраски </xh4> Это древовидный алгоритм. Работаем с бинарным деревом.

Возьмем две не смежные вершины.
ветка_1
  Эти вершины покрашены в один цвет
  Тогда будем строить дерево вариантов от текущего узла дальше.
ветка_2
  Эти вершины покрашены в разные цвета.
  Можем считать, что между ними есть ребро, т.е. добавили ребро.
  Строим дерево вариантов дальше.
  Множество раскрасок этого графа совпадает со множеством раскрасок исходного, в которых данные вершины покрашены в разные цвета.