ОБЗОР МЕТОДОВ И АЛГОРИТМОВ ПОИСКА ХРОМАТИЧЕСКОГО ЧИСЛА ГРАФА

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