Канонический код дерева (Computer Tools in Education, 2014)
Канонический код – это способ записи графа, инвариантный относительно изоморфизма. В статье вкратце объясняется значимость канонических кодов и показывается связь задачи вычисления канонического кода с другими задачами, известными из курса теории алгоритмов. Приводится алгоритм вычисления канонического кода для дерева с помеченными вершинами и рёбрами, который работает за линейное время от размера дерева. Алгоритм основан на известном алгоритме проверки изоморфизма двух деревьев.
Keywords: канонический код; каноническая нумерация; изоморфизм графов; изоморфизм деревьев