Другие журналы
|
Суров Павел Владимирович
СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ РАСКРАСКИ ГРАФА
Инженерный вестник # 02, февраль 2017 УДК: 519.174.7 Статья посвящена сравнительному анализу алгоритмов, находящих хроматическое число произвольного графа. Существует большое количество алгоритмов решения задачи нахождения минимальной раскраски графа. Эта задача имеет высокую вычислительную сложность, и точным методам решения часто предпочитают более быстрые приближенные методы. В статье приведены сравнительные исследования двух наиболее распространённых алгоритмов раскраски графа: алгоритма полного перебора – точный метод, и алгоритма неявного перебора – приближённый метод. Для реализации исследуемых алгоритмов была написана программа на языке С. В ходе исследований были определены: скорость алгоритмов и относительная точность неявного перебора. Также в работе представлены примеры применения алгоритмов при решении ряда практических задач.
|
|
||||||||||||||||||||||||||||||||
|