Идентификация деревьев презентация

Идентификация деревьев Выполнили студенты 2 курса Высшей Школы ИТИС группы 11-401 Бобринская Екатерина, Анисимова Юлия, Татарских Роман

Содержание Какой граф является деревом? Постановка задачи Представление деревьев По корневому признаку Алгоритмы проверки деревьев на изоморфизм Алгоритм Эдмондса Алгоритм сравнения. Графическое представление работы двух алгоритмов Заключение

Какой граф является деревом? Дерево представляет собой граф, который является связным и не имеет циклов

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

Представление деревьев В виде матрицы смежности

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

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

Графическое представление работы двух алгоритмов

Заключение Из данных, приведенных на графике можно сделать вывод, что по времени работы алгоритм сравнения значительно опережает алгоритм Эдмондса. Однако на небольшом числе вершин графа (до 600-700) алгоритмы работают примерно одинаково. Это можно объяснить погрешностью, вызванной различными системными процессами.