Кобецкий Владимир Андреевич

Статья посвящена сравнительному анализу алгоритмов, находящих хроматическое число произвольного графа. Существует большое количество алгоритмов решения задачи нахождения минимальной раскраски графа. Эта задача имеет высокую вычислительную сложность, и точным методам решения часто предпочитают более быстрые приближенные методы. В статье приведены сравнительные исследования двух наиболее распространённых алгоритмов раскраски графа: алгоритма полного перебора – точный метод, и алгоритма неявного перебора – приближённый метод. Для реализации исследуемых алгоритмов была написана программа на языке С. В ходе исследований были определены: скорость алгоритмов и относительная точность неявного перебора. Также в работе представлены примеры применения алгоритмов при решении ряда практических задач.