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

  • П.А. Павлов
Keywords: канонический код, каноническая нумерация, изоморфизм графов, автоморфизмы графов, nauty

Abstract

Проводится краткий обзор алгоритмов, среди которых лидирует алгоритм Брендана МакКея, реализованный им в библиотеке nauty. Излагаются главные принципы этого алгоритма: уточнение разбиений вершин и использование автоморфизмов для сокращения поиска. Приводится псевдокод всего алгоритма в упрощённом виде.
Published
2014-01-21
How to Cite
Павлов, П. (2014). Каноническая нумерация графов и библиотека nauty. Computer Tools in Education, (5). Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1192
Issue
No 5 (2009)
Section
Articles