Вершины и рёбра графа могут быть снабжены дополнительными метками (цветами). В этом случае канонический код включает в себя цветовые идентификаторы.
Канонические коды графов позволяют избавиться от дорогостоящей процедуры проверки изоморфизма (graph isomorphism), и определять совпадение графов по сравнению строк.
Например, как найти дубликаты в множестве N графов? Вычислить N канонических кодов, отсортировать их и последовательно сравнить. Гораздо выгоднее, чем делать N*(N-1)/2 проверок изоморфизма. Можно сказать, что канонический код — это хеш-код без промахов.
Канонический код может выглядеть по-разному: как матрица смежности, развёрнутая в строку, или как маршрут обхода графа в ширину, или в глубину. Какое представление выбрать, не столь важно. Задача в любом случае сводится к вычислению канонической нумерации вершин (canonical numbering, canonical labeling). Каноническая нумерация — это нумерация (перестановка) вершин графа, гарантирующая, что изоморфные графы будут пронумерованы одинаково. Получив нужную перестановку, уже не составит труда построить канонический код, например, по обходу графа в глубину: начать обход с вершины под номером 1 и при ветвлении выбирать ту вершину, «канонический номер» которой меньше.
Наличие полиномиального алгоритма для задачи канонической нумерации означало бы, что задача изоморфизма графов полиномиально разрешима. На данный момент, для задачи изоморфизма графов полиномиального алгоритма не найдено, но и не доказана NP-полнота (в отличие от известной задачи изоморфизма подграфу, subgraph isomorphism). По некоторым признакам можно предполагать, что она не является NP-полной.
В ряде частных случаев существуют полиномиальные алгоритмы проверки изоморфизма и канонической нумерации. Мы рассмотрим простейший случай: когда граф является деревом.
В книге Ахо, Хопкрофта и Ульмана «Построение и анализ вычислительных алгоритмов» приводится алгоритм для определения изоморфизма двух деревьев (tree isomorphism), работающий за линейное время от количества вершин. На его основе нетрудно составить алгоритм канонической нумерации вершин дерева, работающий за то же линейное время.
Этап 1. Выделение корня
Отрубим от дерева все листья. Получится дерево меньшего размера. Будем повторять процедуру до тех пор, пока не останется одна вершина (center) или две вершины, соединённых ребром (bicenter).
Если осталась одна вершина, мы делаем её корнем и располагаем остальные вершины по уровням, считая от корня:
Если осталось ребро, мы располагаем остальные вершины по уровням, считая от этого ребра, обе вершины которого помещаются на первый уровень:
Мы разделили N вершин на K уровней так, что у каждой вершины на уровне k>1 есть «родитель» из уровня k-1. Вспомним ещё, что вершины и рёбра снабжены цветами. В наших обозначениях вершины будут красные и синие, а рёбра — чёрные и зелёные.
Этап 2. Поуровневая сортировка
Для алгоритма нужно задать условный порядок на цветах. Пусть красный цвет будет старше синего, а зелёный старше чёрного. Введём обобщённый код вершины, состоящий из цветового кода ребра, которое соединяет её с родителем, и из цветового кода самой вершины. Сгруппируем вершины нижнего уровня, имеющие одинаковый обобщённый код, и присвоим каждой группе ранг, соответствующий старшинству цветов. Цвет ребра имеет больший приоритет, чем цвет вершины. Ранг 0 считается самым старшим:
Составим обобщённые коды родителей этих вершин, которые расположены на предыдущем уровне. Кроме цветовых кодов ребра к родителю и самой вершины, включим в обобщённый код отсортированный список рангов её детей. Ранги детей имеют меньший приоритет, чем цветовые коды вершины и ребра:
Повторяем описанную процедуру:
и ещё раз:
Пока не дойдём до уровня 1. В нашем случае на первом уровне одна вершина, поэтому её ранг нулевой, в случае двух вершин на первом уровне нужно сравнить их обобщённые коды и присвоить им ранги 0 и 1 (или 0 и 0).
Этап 3. Нумерация
Начиная с уровня 1, присваиваем вершинам возрастающие номера в порядке возрастания их рангов. В случае совпадения рангов на уровне порядок присваивания номеров может быть любым, т.к. вершины с одинаковым рангом в некотором смысле идентичны. (Выражаясь математически, эти вершины лежат на одной орбите, т.е. существует автоморфизм графа, переводящий одну вершину в другую.)
Построение канонического кода
Как было сказано, строить канонический код можно многими способами. Приведём пример канонического кода, построенного при обходе дерева в глубину:
Для построения такого кода не нужен даже третий этап предыдущего алгоритма (нумерация). Мы начинаем обход с корня и для каждой посещённой вершины обходим её детей в порядке старшинства. Для определения старшинства детей хватит «внутриуровневых» кодов, полученных на этапе 2.
Анализ сложности
Этап 1, очевидно, требует O(N) операций. Нетрудно также понять, что на этапе 2 мы, двигаясь от последнего уровня к первому, проходим все вершины по одному разу. Затруднения может вызвать только процесс «ранжирования» вершин на уровне, но при использовании поразрядной сортировки он занимает время, пропорциональное количеству вершин, и суммарно по уровням получается тоже O(N) операций. Этап 3 и построение самого кода также занимают линейное время.
Каноническая нумерация в общем случае
Австралийский профессор Brendan McKay написал библиотеку на C под названием nauty. Она предназначена для поиска групп автоморфизмов произвольных графов; одним из её «побочных» результатов является каноническая нумерация вершин.
Nauty работает очень быстро. Цвета рёбер она не поддерживает, но при необходимости всегда можно добавить в граф псевдо-вершины таким образом, что каноническая нумерация получившегося графа без учёта цветов рёбер будет являться канонической для исходного графа.
