Презентация на тему Идентификация деревьев

проверки деревьев на изоморфизм
Алгоритм Эдмондса
Алгоритм сравнения.
Графическое представление работы двух

алгоритмов
Заключение

является связным и не имеет циклов

является одной из основных задач теории графов. Одна из

целей – выявить алгоритм, сложность которого не будет превышать степенную функцию, который бы определял, являются ли два конечных графа одинаковыми(в абстрактном смысле), то есть изоморфными

1,2,3,5;
3: 4,6,7;
7: 5,8,9;
1: 4;
2: 4;
3: 4;
6: 4;
8: 7;
9: 7;

Эдмондса, которая гласит, что два дерева являются изоморфными тогда

и только тогда, когда совпадают их центральные кортежи.

Итак, алгоритм состоит в следующем:
деревья кортежируются с помощью процедуры
если центральные кортежи совпадают, то деревья изоморфны. В противном случае, они не изоморфны.

суметь “увидеть” структуру деревьев и сравнивать именно её, а

не конкретные значения вершин.

Каждой вершине в соответствие ставится ряд чисел {x,y,{a1,a2,a3,…,an}}, где
x - уровень вершины по высоте;
y - ее “отцовый” уровень, т.е. длина максимальной линии потомков;
{a1,…,an} - ряд “отцовых” уровней её сыновей.
Важно учесть:
1. при сравнении этих массивов не важен порядковый номер элемента, т.е. элементу 2 одного массива может соответствовать элемент 3 второго массива;
2. не важен порядок элементов ряда «отцовых» уровней сыновей