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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
 
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
 +
== Некоторые связанные понятия ==
 +
'''Хроматическое число''' — наименьшее число красок, в которое может быть раскрашен граф.
 +
 +
'''Задача о раскраске графа'''. Раскрасить вершины графа в наименьшее число красок так, чтобы никакие смежные вершины не были покрашены в один цвет.
 +
 +
== Алгоритм ==
 +
Это древовидный алгоритм для '''задачи о раскраске графа'''.
 +
 +
Он имеет несколько пунктов.
 +
<xh4> 1. Проверка полноты графа </xh4>
 +
Если граф полный
 +
    хроматическое число графа = число вершин
 +
Если граф имеет полный подграф
 +
    хроматическое число графа >= число вершин полного подграфа
 +
 +
<xh4> 2. Выбрасывание вершин </xh4>
 +
Обозначим через <tt>''p''(x)</tt> степень вершины <tt>x</tt>.
 +
 +
Если хотим проверить, что <tt>m</tt> красок хватит для раскраски графа, можем воспользоваться следующим алгоритмом:
 +
1. Если в графе есть вершина x | ''p''(x) < m
 +
        выбросить ее из графа вместе со смежными ребрами
 +
        (если m красок хватит для раскраски полученного графа, то и для исходного хватит)
 +
    иначе
 +
        применить какой-нибудь из известных алгоритмов для оставшегося графа
 +
2. Перейти к шагу 1
 +
 +
<xh4> 3. Поиск раскраски </xh4>
 +
Это древовидный алгоритм. Работаем с бинарным деревом.
 +
Возьмем две не смежные вершины.
 +
''ветка_1''
 +
  Эти вершины покрашены в один цвет
 +
  Тогда будем строить дерево вариантов от текущего узла дальше.
 +
''ветка_2''
 +
  Эти вершины покрашены в разные цвета.
 +
  Можем считать, что между ними есть ребро, т.е. добавили ребро.
 +
  Строим дерево вариантов дальше.
 +
  Множество раскрасок этого графа совпадает со множеством раскрасок исходного, в которых данные вершины покрашены в разные цвета.
 +
 
[[Категория:Алгоритмы и анализ сложности]]
 
[[Категория:Алгоритмы и анализ сложности]]
 
[[Категория:Учебные курсы ИТ]]
 
[[Категория:Учебные курсы ИТ]]

Текущая версия на 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
  Эти вершины покрашены в разные цвета.
  Можем считать, что между ними есть ребро, т.е. добавили ребро.
  Строим дерево вариантов дальше.
  Множество раскрасок этого графа совпадает со множеством раскрасок исходного, в которых данные вершины покрашены в разные цвета.