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

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

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл No. ФС77-51036. ISSN 2307-0595

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

Инженерный вестник # 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.



Тематические рубрики:
Поделиться:
 
ПОИСК
 
elibrary crossref neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (499) 263-69-71
  RSS
© 2003-2017 «Инженерный вестник» Тел.: +7 (499) 263-69-71