Как проверить изоморфизм деревьев

Параметр $g$ функции treeCenters() представляет собой неориентированный граф.

Переменная $n$ представляет количество узлов в нашем дереве. Мы определили два массива, степень и листья. Первый имеет размер $n$ и хранит степень каждого узла в дереве, последний хранит самый последний слой конечных узлов.

Затем мы входим в цикл, где мы вычисляем степень каждого узла графа, также мы проверяем, рассматривается ли дерево с одним узлом или же листовой узел. Если какое-либо из этих условий выполняется, мы добавляем запись в массив листьев и помечаем ее значение в degrees array как 0, чтобы не посещать узел вновь.

Переменная $count$ будет отслеживать количество узлов, которые мы обработали на текущей итерации. Затем мы постоянно проверяем наличие листьев и удаляем их из поиска.

Сериализованное представление дерево будет получено путем перевода его в уникальную кодировку, которая представляет собой последовательность открывающих и закрываюх скобок, например "(()()()(()))".

Формальное описание работы:

• Присвоить всем листьям метку "()"
• Для каждого родителя объединить метки его детей и заключить в новую пару скобок.

function encode(node): if node == null: return "" labels = [] for child in node.children(): labels.add(encode(child)) # lexographic sort sort(labels) result = "" for label in labels: result += label return "(" + result + ")" 

Из основной программы в функцию передается центр дерева. Способ кодирования дерева с 2-мя центрами будет рассмотрен в след. главе.

Таким образом, если результат кодировки двух деревьев одинаков - деревья изоморфны.

Проверка на изоморфизм при наличии двух центров

Отличие в кодировании дерева с 2-мя центрами заключается в том, что обозреваемое дерево разбивается на 2 поддерева, корнями которых являются оба центра. Все, что остается сделать в этом случае, это сравнить результат работы алгоритма для каждого из поддеревьев первого дерева со вторым.

Псевдокод выглядит следующим образом:

function is_isomorphic(tree a, tree b): a_centers = find_centers(a) b_centers = find_centers(b) a_encoded = [encode(a, a_centers[0]), encode(a, a_centers[0])] b_encoded = [encode(b, b_centers[0]), encode(b, b_centers[0])] sort(a_encoded) sort(b_encoded) return a_encoded.ToString == b_encoded.ToString 

Как видно из примера, алгоритм последовательно кодирует каждый центр каждого дерева, затем лексикографически сортирует результаты. Одинаковые кодировки соответствуют изоморфным деревьям.

Исходный код можно найти здесь. Структура проекта подразумевает деление на следующие модули:

• исходный код алгоритма
• система с ручными тестами
• генератор
• тестировщик скорости

Модули реализованы в виде подпроектов и расположены в соответствующих директориях.

Основная функция: is_isomorphic(tree1, tree2) - возвращает 0 или 1, в зависимости от результата. Вспомогательные функции:

struct node: id node parent children[] 

Тестирование было разделено на 2 этапа: ручное и с использованием генератора.

void fifteen_node() < std::vectortree1 = ; std::vector tree2 = ; assert(is_isomorphic(tree1, tree2)); cout

Тестирование с использованием генератора

Принцип работы генератора

Генератор работает по тривиальной модели, за счет спаривания случайной вершины с текущей, во время итерации по узлам

 generate_tree(int vertex_count) < tree(vertex_count, -1); for (int i = 1; i < tree.size(); i++) < int vertex = rand(0, i - 1); tree[i] = vertex; >return tree; > 

Функция принимает в себя значение типа int - количество узлов в дереве. Далее в цикле от 1 до vertex_count функция случайным образом выбирает вершину [0, i - 1] и создает ребро между ними. Ассимптотика генерации составляет O(n).

Для анализа скорости работы алгоритма был создан специальный модуль - speed_test . Модуль включает в себя функцию, которая генерирует 2 случайных дерева в диапазоне от 1000 до 1000000 шагом в 10000. При этом замерияется скорость работы функции is_isomorphic в миллисекундах, без учета скорости генерации самих деревьев. Полученные данные были занесены в Excel, был составлен график:

Из графика видно, что функция растет линейно, что соотвтсвует желаемой ассимптотике в O(n*log(n))

Была проведена работа по разработке системы, обеспечивающей реализацию, тестирование и анализ производительности алгоритма AHU для идентификации изоморфных деревьев. Была достигнута корректность работы, а также ассимптотика, близкая к O(n*log(n))

Источник

Как проверить изоморфизм деревьев

Изоморфизм - логико-математическое понятие, выражающее одинаковость строения (структуры) систем (процессов, конструкций). Деревья считаются изоморфными в том случае, если они имеют одинаковую структуру, но различный внешний вид.

На рисунке 1 отчетливо видно, что оба дерева имеют одинаковую структуру, но различный внешний вид. Соответствие вершин таково: 1-1, 2-3, 3-2, 4-4.

Задача алгоритма сравнения состоит в том, чтобы суметь "увидеть" структуру деревьев и сравнивать именно её, а не конкретные значения вершин.

Каждой вершине в соответствие ставится ряд чисел >, где

x - уровень вершины по высоте;

y - ее "отцовый" уровень, т.е. длина максимальной линии потомков;

- ряд "отцовых" уровней её сыновей. (*)

В нашем примере вершинам дерева №1 соответствуют такие числа:

Таким образом, были получены два массива записей, и можно утверждать, что если между элементами этих двух массивов можно установить взаимно-однозначное соответствие, то деревья, описываемые этими массивами, изоморфны. При этом важно учесть:

1. при сравнении этих массивов не важен порядковый номер элемента, т.е. элементу 2 одного массива может соответствовать элемент 3 второго массива;
2. не важен порядок элементов ряда "отцовых" уровней сыновей (*)

Т.е. учитывая вышеприведенные условия сравнения можно сказать, что элемент 2 - > соответствует элементу 3->, а элемент 1 - > - элементу 1 - >.

2. Алгоритм переопределения вершин.

Недостатком алгоритма сравнения, является невозможность его применения для изоморфных деревьев с различными корневыми вершинами. Например, на рисунке 2 изображены изоморфные деревья, но один только алгоритм сравнения не сможет распознать их изоморфность. Решением этой проблемы является трансформация деревьев к общему виду следующим методом.

У первого дерева находим концевую вершину (ту, у которой нет сыновей), и делаем её корневой, т.е. дерево как бы вытягивается наверх за одну из вершин (см. рис. 3). Такой "вытяжки" можно достичь путем замены имени отца вершины именем одного из ее сыновей, и наоборот имени этого сына именем ее отца. Полученное дерево мы принимаем за эталонное.

После, основываясь на том свойстве, что концевая вершина в одном из изоморфных деревьев соответствует концевой вершине во втором дереве, мы выбираем все концевые вершины из второго дерева, поочередно делаем их корневыми и каждый раз сравниваем "вытянутое" дерево с эталонным с помощью вышеописанного алгоритма сравнения.

Если алгоритм сравнения хотя бы один раз дал положительный результат, то деревья изоморфны.

Сложностью такого алгоритма проверки изоморфизма является величина порядка N2, где N - количество вершин в любом из сравниваемых деревьев.

Алгоритмы непосредственно в виде программы или блок-схемы слишком громоздки, и поэтому здесь не приводятся, но желающие могут скачать исходные тексты программы.(13Kb)

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

Источник