Машиностроение
Приборостроение
Методическая периодика: проблемы и решения
Организация производства (промышленность)

Ключевые слова
Аннотации
Архив рубрик

регистрация
забыли пароль?

Другие журналы

электронный научно-технический журнал

ИНЖЕНЕРНЫЙ ВЕСТНИК

Издатель: Общероссийская общественная организация "Академия инженерных наук им. А.М. Прохорова".

СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ РАСКРАСКИ ГРАФА

Инженерный вестник # 02, февраль 2017
УДК: 519.174.7

Файл статьи:

Kobetskiy_р.7-15.pdf (840.53Кб)

авторы: Зинченко Л. А., Резчикова Е. В., Кобецкий В. А., Суров П. В.

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

Список литературы
[1]. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М: Наука, 1990. 384 с.
[2]. Кристофидес Н. Теория графов: Алгоритмический подход: пер. с англ. Э.В. Вершкова, И.В, Коновальцева / под ред. Г.П. Гаврилова. М: Мир, 1978. 432 с. [Nicos Christofides. Graph Theory: An Algorithmic Approach. New York: Academic Press, 1975] .
[3]. Оре О. Теория графов: пер. с англ. И.Н. Врублевской / под ред. Н.Н. Воробьева. М: Наука, 1968. 352 с. [Oysten Ore. Theory of Graphs. American Mathematical Society, 1962].
[4]. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ: пер. с англ. 2-е изд. М.: Вильямс, 2005. 1290 с. [Cormen, T.H., Leiserson C.E, Rivest R.L., Stein C. Introduction to Algorithms. 2nd. MIT Press and McGraw-Hill, 2001].
[5]. Сокол В.А. Электрохимическая технология микро- и наноэлектронных устройств // Доклады БГУИР. 2004. № 3. С. 18-26.
[6]. Abfalter I., Flamm C., Stadler P. Design of Multi-Stable Nucleic Acid Sequences // Proceedings of the German Conference on Bioinformatics (Neuherberg/Garching near Munich, Germany, October 12-14, 2003). Oxford University Press, 2004. Vol. 1. P. 1-7.