Каноническая нумерация графов и библиотека nauty
Ключевые слова:
канонический код, каноническая нумерация, изоморфизм графов, автоморфизмы графов, nautyАннотация
Проводится краткий обзор алгоритмов, среди которых лидирует алгоритм Брендана МакКея, реализованный им в библиотеке nauty. Излагаются главные принципы этого алгоритма: уточнение разбиений вершин и использование автоморфизмов для сокращения поиска. Приводится псевдокод всего алгоритма в упрощённом виде.Загрузки
Опубликован
21.01.2014
Выпуск
Раздел
Новая статья
Лицензия
Материал публикуется под лицензией:
Как цитировать
[1]
«Каноническая нумерация графов и библиотека nauty», Компьютерные инструменты в образовании, вып. 5, янв. 2014, просмотрено: июл. 24, 2026. доступно на: http://cte.eltech.ru/ojs/index.php/kio/article/view/1192
