Перебор с возвратом (backtracking) и отсечениями.

Целью курсовой работы является разработка программы визуализатора алгоритма поиска с возвратом и отсечениями примененного к задаче раскраски графа.

Алгоритм полного перебора для случая k-раскраски рассматривает все kn комбинаций расстановки цветов в графе с n вершинами и проверяет их на корректность. Чтобы вычислить хроматическое число и хроматический полином, данный алгоритм рассматривает каждое k от 1 до n. Такой алгоритм на практике может быть применим только для небольших графов.
Существуют гораздо более эффективные алгоритмы решения поставленной задачи для различных типов графов.
Для двудольного графа задача раскраски вычисляется за линейное время с помощью поиска в ширину. В случае совершенных графов, хроматическое число и соответствующая ему раскраска может быть найдена за полиномиальное время при использовании полуопределённого программирования. Точные формулы для нахождения хроматического числа известны для многих классов графов (леса, циклы, колеса, хордальные графы) и так же могут быть вычислены за полиномиальное время.
Жадный алгоритм упорядочивает вершины и последовательно присваивает вершине vi наименьший доступный цвет, не использовавшийся для окраски соседей, либо добавляет новый. Качество полученной раскраски зависит от выбранного порядка. Всегда существует такой порядок, который приводит жадный алгоритм к оптимальному числу красок. С другой стороны, жадный алгоритм может быть сколь угодно плохим.

В процессе выполнения курсовой работы был изучен алгоритма поиска с возвратами и написана программа пошаговой визуализации применения этого алгоритма к задаче раскраски графа.
В курсовой работе рассмотрены теоритические вопросы, касающиеся алгоритма поиска с возвратами (исторический обзор, особенности алгоритма, вопросы эффективности и применимости алгоритма) и задачи раскраски графа (постановка задачи, подходы к решению).
Разработанное приложение реализовано для следующей постановки задачи: найти все возможные раскраски графа заданным количеством цветов, таких чтобы соседние вершины были разного цвета. В программе предусмотрены функции пошагового просмотра результатов работы алгоритма в ручном или автоматическом режиме и загрузка тестового графа из файла.