Каноническая нумерация графов и библиотека nauty

Авторы

  • П.А. Павлов

Ключевые слова:

канонический код, каноническая нумерация, изоморфизм графов, автоморфизмы графов, nauty

Аннотация

Проводится краткий обзор алгоритмов, среди которых лидирует алгоритм Брендана МакКея, реализованный им в библиотеке nauty. Излагаются главные принципы этого алгоритма: уточнение разбиений вершин и использование автоморфизмов для сокращения поиска. Приводится псевдокод всего алгоритма в упрощённом виде.

Загрузки

Опубликован

31.10.2009

Выпуск

№ 5 (2009)

Раздел

Информатика

Лицензия

Авторский договор

Как цитировать

[1]
«Каноническая нумерация графов и библиотека nauty», Comput. Tools Educ., вып. 5, окт. 2009, просмотрено: окт. 24, 2026. доступно на: http://cte.eltech.ru/ojs/index.php/kio/article/view/1192