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

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

1. Алгоритм сравнения.

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

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

1 - {2, 2, {0, 1}}, 2 - {1, 0, {0}}, 3 - {1, 1, {0}}, 4 - {0, 0, {0}}.

Вершинам дерева №2:

1 - {2, 2, {1, 0}}, 2 - {1, 1, {0}}, 3 - {1, 0, {0}}, 4 - {0, 0, {0}}.

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

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

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

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

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

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

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

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

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

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

Литература.

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