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