🗊Презентация Деревья. Дерево - граф без циклов

Деревья

Дерево - граф без циклов. Лес – граф, компоненты которого являются деревьями. Дерево можно использовать для демонстрации результатов трехкратного подбрасывания монеты.

Не является деревом (содержит цикл): Лес:

Ориентированное дерево Т – свободный от петель ориентированный граф, соотнесенный граф которого является деревом. Если существует путь от вершины a к вершине b, то он единственный. Если в ориентированном дереве имеется ребро (a, b), тогда не существует ребро (b, a), в противном случае путь aba был бы циклом, путь из a и b не был бы единственным. Множество Е, которое для дерева представляет собой как конечное множество ребер так и отношение, обладает таким свойством, что если (a, b) Е, то (b, a)  Е. Такое отошение называется асимметричным.

Если неориентированное дерево имеет хотя бы одно ребро, оно имеет хотя бы две вершины со степенью 1. Вершины степени 1 называются листьями (начинается в вершине a и заканчивается в вершине b). Другие вершины называются внутренними вершинами. Максимальными путь не обязательно совпадает с самым длинным путем в дереве. Пример. Путь v0 v2 v5 является максимальным путем. Вершины v3 , v4 , v5 , v7 являются листьями.

Теорема. Для любых двух вершин a и b дерева Т существует единственный путь из a и b. Доказательство. Предположим, что для некоторых вершин a и b дерева Т путь из a в b не является единственным, тогда Т не является деревом: Допустим существуют два различных пути v0v1v2 … vn длины n и v`0v`1v`2 … v`n длины m, где a = v0 и vn = v`m . В каждом пути должна существовать первая вершина, начиная с которой соответствующие вершины не совпадают, например vi  v`I и в каждом из путей должна существовать точка, начиная с которой вершины опять одни и те же vj = v`k . Тогда vi – 1 vi v i + 1 vj v`k – 1 v`k – 2 v`i v`i – 1 является циклом  граф Т не является деревом. Противоречие доказывает теорему. Верна также обратная теорема.

Если для любых двух вершин графа G существует единственный путь из вершины a в вершину b, тогда G – дерево. Доказательство: Предположим G не является деревом. Тогда либо G не является связным, либо содержит цикл. Если граф G не связный, то существуют вершины a, b  G, для которых не существует пути из a в b. Если G содержит цикл v0v1v2 … vk – 1 vk , то v1v2 … vk – 1 vk v0 и v2v1v0 являются путями из v2 в v0 . Полагая a = v2 и b = v0  путь между вершинами a и b не является единственным. Противоречие доказывает теорему.

Пусть дерево представляет физический объект, подвижный в вершинах. Подвешенное дерево за одну из вершин, остальная часть повиснет ниже

Подвешенное за вершину v3 Подвешенное за вершину v4

Вершина в самой верхней части каждого изображения называется корнем дерева. Если корень дерева определен, дерево называется корневым деревом. При необходимости можно заменить корневое дерево Т на ориентированное Т`, дерево будет заменено деревом

Такое дерево называется корневым ориентированным деревом. Т` - порожденным деревом Т. Если корень выбран, уровень вершины v определяется длиной единственного пути из корня в вершину v. Высотой дерева называется длина самого длинного пути от корня дерева до листа. Если рассматривается корневое ориентированное дерево Т `, порожденное данным корневым деревом Т, тогда вершина u называется родителем вершины v , а v называется сыном вершины u , если существует ориентированное ребро из u и v. Если u - родитель v и v`, тогда v и v` называются братьями. Если существует ориентированный путь из вершины u в вершину v, тогда u называется предком вершины v, а v называется потомком вершины u.

Если наибольшая из степеней выхода для вершин дерева равна m, тогда дерево называется m –арным деревом. В частном случае (m = 2) дерево называется бинарным деревом. В каждом бинарном дереве каждый сын родителя обозначается как левый сын или как правый сын ( но не одновременно).

Граф – бинарное дерево. Уровень вершины v6 равен 2, уровень вершины v8 равен 3. Высота дерева равна 3 и не существует более длинного пути от корня к листу. Вершина v1 является родителем для v3 и v4. Вершина v3 и v4, v1 и v2, v5 и v6, v7 и v8, - братья. Вершина v8 – левый сын вершины v3, v4 – левый сын вершины v1.

Теорема. Если у дерева Т имеется е ребер и v вершин, тогда v = e + 1. Доказательство: Рассмотрим ориентированное дерево Т`, порожденное деревом Т. У каждого ребра Т одна и только одна конечная вершина.  Число ребер и вершин одно и то же, исключая коневую вершину. Если учесть ориентированную вершину  вершин на одну больше, чем ребер. Ч.т.д.

Теорема. Если G содержит цикл, если ребро {vi , vj } входит в цикл  два пути из vi в vj . Т.е. ребро {vi , vj } можно из цикла удалить, а путь из вершины vi в vj будет существовать. Пусть a и b - любые точки в G. G - связный граф  существует путь из a в b . Если ребро {vi , vj } удалено  существует путь из a в b , ребро {vi , vj } можно заменить альтернативным путем из vi в vj . Продолжают, пока все циклы не будут удалены. Получают связный граф G` без циклов. G` - дерево, число вершин v = e` + 1, e` - число ребер графа. G`. Ни одна вершина не выла удалена. Удалено n ребер, тогда e = e` + n. v = e + 1 и v = e` + 1  e = e` и n = 0.  ни одно ребро не было удалено.  G - дерево.

Дерево G`, построенное из G в процессе доказательства остается, называется остовным (каркасным) деревом графа G. Дерево Т называется остовным деревом графа G, если Т – подграф графа G и каждая вершина в G является вершиной в Т. Теорема. У каждого связного графа существует подграф, который является остовным деревом.

Свойства деревьев

Теорема. Следующие утверждения эквивалентны А) Граф G - дерево. Б) Граф G – связный и v = e + 1, v – количество вершин, e – количество ребер графа G. В) Для каждой пары различных вершин a и b существует единственный путь из a в b . Г) Граф G – ацикличный (не имеет циклов) и v = e + 1.

Определения. Ориентированное Т-дерево это ориентированный граф без петель, соотнесенный граф которого является деревом, так что если существует путь из вершины а в вершину b, то он единственный. Ориентированное дерево Т является корневым ориентированным деревом, если существует единственная вершина v0 такая, что существует путь из вершины v0 в каждую другую вершину дерева Т.

Теорема. Для ориентированного дерева G следующие утверждения эквивалентны. А) G – корневое ориентированное дерево. Б) G имеет единственный такой элемент v0 , что для любой вершины а графа G существует единственный ориентированный путь из v0 в а. В) Соотнесенный граф графа G связен, и G содержит единственный элемент v ' такой, что для любой другой вершины а графа G существует единственный путь из v0 в а.

Рассматриваются только корневые ориентированные деревья. Определения. В ориентированном дереве уровень вершины v - это длина пути от корня до вершины v. Высота ориентированного дерева - это длина самого длинного пути от корня до листа. m –арным ориентированным деревом называется такое дерево, в котором родитель имеет не более m сыновей. Полным m –арным ориентированным деревом называется такое ориентированное дерево, в котором каждый родитель имеет в точности m сыновей. m –арным ориентированным деревом высоты h называется сбалансированным (полным, или почти полным), если уровень каждого листа равен h или h – 1.

Теорема. Если полное m –арное ориентированное дерево имеет n вершин и i внутренних вершин, то n = m i + 1. i = (n – 1)/ m Теорема. Если полное m –арное ориентированное дерево имеет n вершин, i внутренних вершин и l листьев, то l = (m – 1) i +1. i = (l – 1)/(m – 1) Теорема. Полное m –арное ориентированное дерево высоты h имеет (mh+1 - 1)/ (m -1) вершин и mh листьев. В частности, полное бинарное ориентированное дерево высоты h имеет 2h+1 - 1 вершин и 2h листьев.

Теорема. а) Если полное m –арное дерево высоты h имеет l листьев, то h = logm(l). б) Если m –арное дерево имеет l листьев, то h  logm(l). в) Если полное бинарное дерево высоты h имеет v вершин, то h = log2(v + 1 ) - 1. г) Если бинарное дерево высоты h имеет v вершин, то h  log2(v + 1 ) - 1.

Определение. Функция f из графа G(V,E) в граф G'(V ',E ' ) называется гомоморфизмом из G в G ', обозначается f : G  G ', если она обладает следующими свойствами : а) Если e  E, то f (e)  E' ( f(E )  E '). б) Если v  V, то f (v)  V' ( f(V )  V '). в) Если вершины u и v инцидентны ребру e в G , то f(u) и f(v) инцидентны ребру f(e) в G '.

Определение. а) Если e  E, то f(e)  E ' (f(E)  E ' ). б) Если v  V, то f(v)  V ' (f(V)  V ' ). в) Если вершины u и v инцидентны ребру e в G, то f(u) и f(v) инцидентны ребру f(e) в G '. Определение. Гомоморфизм f : G  G' является изоморфизмом, если f : V  V ' и f : E  E ' являются взаимно однозначными соответствиями. Если f : G  G' изоморфизм, то G и G' изоморфны.

Определение. Два корневых бинарных дерева T(E,V) и T '(E ', V ') изоморфны, если существует изоморфизм f из Т в Т ' такой, что а) vi - левый сын вершины vj тогда и только тогда, когда f (vi) - левый сын вершины f (vj). б) vi - правый сын вершины vj тогда и только тогда, когда f (vi) - правый сын вершины f (vj). в) f отображает корень r дерева Т в корень r ' дерева Т '. Теорема. Число неизоморфных корневых бинарных деревьев с n вершинами равна числу Каталана Cn.

Доказательство: Пусть In – число изоморфных корневых бинарных деревьев с n вершинами. Если n=0, дерево пустое и I0 = 1. Если n=1, одна вершина, одно дерево и I1 = 1. Если n=2, два корневых бинарных дерева. Если n=3, пять корневых бинарных дерева.

Если n >3, выбираем k, что 1  k  n. Пусть Tn обозначает дерево с n вершинами и пусть Tn,k - дерево с n вершинами, определенное следующим образом. Одна вершина является конем, пусть имеется правое поддерево Tn-1 c k – 1 вершиной и левое поддерево Tn -k с n – k вершинами.

По определению число способов, которыми можно построить дерево Tk – 1 , а число способов, которыми можно построить дерево T n- k , равно I n – k . Т.е. число способов построения Tn, k равно Ik – 1 I n – k. Суммируя по k , получается число всевозможных способов построения дерева Tn . Это совпадает с определением числа Каталана Cn .

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

Алгоритм вставки имени в дерево поиска, за исключением размещения имени в корне дерева. Применим для любого упорядочения.

Алгоритм поиска имени в дереве списка.

Пример удаления вершины из дерева.

Пример. Дерево: Если удалить вершину х Если удалить вершину k

Пример (продолжение). Если удалить вершину h, нужно спуститься к правому сыну p, затем к левому сыну k. k не имеет левого сына, это искомый элемент для замены. Меняем h на k и делаем l левым сыном р.

Пример (продолжение). Если удалить вершину p , следует идти вправо к вершине w, затем влево к s, затем влево к q. q не имеет левого сына. Меняем p на q и делаем r левым сыном вершины s.

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

Определение. Однозначно декорируемый код для языка как множество, что каждая строка в языке может быть задана однозначно как конкатенация элементов. В этом случае строки из единиц и нулей, представляющие элементы из А, будут кодом. Эти строки образуют однозначно декодируемый код. Разделяя строки на элементы, представляющие А, знаем, что представление однозначно. Декодированные слова будут правильные. Код С префиксный, если он обладает свойством, что никакой элемент кода не может быть начальной строкой другого элемента кода. Конкатена́ция (сцепле́ние) — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир».

Пример. Дерево с листьями Пути к листам v1, v2, v3, v4, v5, v6 обозначают 00, 010, 011, 10, 110, 111. Строку, соответствующую данному листу, называют путевым кодом.

Теорема. В любом бинарном дереве путевые коды для листьев дерева являются префиксным кодом. Чем меньше вес дерева, тем в большей степени достигнута цель. Чтобы найти наилучший код для минимизации данных, необходимо найти код с минимальным весом. Процесс построения такого дерева называется алгоритмом Хаффмана. Код, приписываемый символам согласно их путевому коду, называется кодом Хаффмана.

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

Пример (продолжение). li и fi - уровень и частота заданного элемента. Упорядочим частоты списке частот (5, 10, 13, 17, 25, 30). Деревья: Списки частот: (13, 15, 17, 25, 30) (17, 25, 28, 20) (28, 30, 42) (42, 58)

Пример (продолжение). Объединяем два дерева и формируем исходное дерево

Лемма. Для заданного множества из n символов и их частот существует бинарное дерево минимального веса с символами в качестве листьев. Доказательство: Существует только четное число бинарных деревьев с n листьями. Для каждого и выберем дерево, которое обеспечивает наименьшее значение. Ч.т.д. Лемма. В дереве с минимальным весом на максимальном уровне листья присутствуют в парах, т.е. всюду, где есть сын, имеется и правый и левый сын и наоборот.

Лемма. В дереве с минимальным весом два символа с минимальными частотами расположены на максимальном уровне. Лемма. Существует дерево с минимальным весом, в котором два символа с наименьшими частотами имеют одного родителя. Теорема. Для заданного множества символов с соответствующими частотами дерево Хаффмана является деревом с минимальным весом.

Обход бинарных деревьев. Рассмотрим способ обхода бинарного дерева Используем команду обработать (n), где n – узел. Обход дерева в центрированном порядке. Обращаем процесс, использованный при создании дерева. Если дерево: - бинарная операция над выражениями E1 и Е2, обрабатываем (печатаем) это как Получается выражение в инфиксной записи.

Алгоритм обхода дерева в центрированном порядке (ОПД). лс (v) – левый сын вершины v . пс (v) – правый сын вершины v .

!!