ПОСЛЕДОВАТЕЛЬНОСТИ СРАВНЕНИЯ ИНВАРИАНТОВ ГРАФОВ В ЗАДАЧЕ ПРОВЕРКИ ИЗОМОРФИЗМА

  • Елена Фаридовна Сайфуллина Тольяттинский государственный университет
Ключевые слова: графы, изоморфизм, инварианты, репрезентативность, функции риска, случайная генерация

Аннотация

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

Литература

1. Лагутин М. Наглядная математическая статистика. – М.: БИНОМ, 2009.
2. Мельников Б. Подклассы класса контекстно-свободных языков. – М.: МГУ, 1995.
3. Мельников Б. Эвристики в программировании недетерминированных игр. – Известия РАН. Программирование, 2001. – № 5. – С.63–80.
4. Мельников Б., Пивнева С., Рогова О. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов. – Стохастическая оптимизация в информатике, 2010. – № 6. – С.74–82.
5. Оре О. Графы и их применение. – М.: URSS, 2006.
6. Харари Ф., Палмер Э. Перечисление графов. – М.: Мир, 1977.
7. Blitzstein J., Diaconis P. A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees. – http://www-stat.stanford.edu/~cgates/PERSI/papers/degrees.pdf
8. Corneil D., Gotlieb C. An Efficient Algorithm for Graph Isomorphism. – J. of the Association for Computing Machinery. – 1970. – Vol.17, No.1, P.P.51–64.
9. Melnikov B. Discrete optimization problems – some new heuristic approaches. – Proceedings of the 8th Int. Conf. on High-Performance Computing in Asia-Pacific Region, IEEE Computer Society Washington, 2005, 73–80.
Выпуск
Раздел
Естественные науки