Алгоритм Чейтина-Бриггса — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) (Новая страница: «Категория:Алгоритмы и анализ сложности Категория:Учебные курсы ИТ») |
Juliet (обсуждение | вклад) |
||
| (не показана 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 Эти вершины покрашены в разные цвета. Можем считать, что между ними есть ребро, т.е. добавили ребро. Строим дерево вариантов дальше. Множество раскрасок этого графа совпадает со множеством раскрасок исходного, в которых данные вершины покрашены в разные цвета.
