🗊Презентация Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14)

Категория: Математика
Нажмите для полного просмотра!
Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №1Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №2Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №3Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №4Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №5Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №6Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №7Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №8Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №9Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №10Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №11Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №12Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №13Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №14Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №15Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №16Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №17Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №18Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №19Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №20Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №21Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №22Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №23Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №24Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №25Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №26Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №27Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №28Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №29Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №30
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14). Доклад-сообщение содержит 30 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №1
Описание слайда:

Слайд 2


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

Слайд 3


Корнем неориентированного дерева называют вершину с минимальным порядковым номером. Корнем неориентированного дерева называют вершину с минимальным порядковым номером. Если в дереве T корень задан (то есть оно изображено сверху вниз, и в нем есть самая верхняя вершина), то дерево T называют корневым. В неориентированном дереве, как и в произвольном графе, пара вершин соединяется ребром.
Описание слайда:
Корнем неориентированного дерева называют вершину с минимальным порядковым номером. Корнем неориентированного дерева называют вершину с минимальным порядковым номером. Если в дереве T корень задан (то есть оно изображено сверху вниз, и в нем есть самая верхняя вершина), то дерево T называют корневым. В неориентированном дереве, как и в произвольном графе, пара вершин соединяется ребром.

Слайд 4


Листьями неориентированного дерева (висячими вершинами) называются вершины, которым инцидентно лишь одно ребро. Листьями неориентированного дерева (висячими вершинами) называются вершины, которым инцидентно лишь одно ребро. Узлом (внутренней вершиной) произвольного дерева называют вершину, которая не является корнем, и не является листом.
Описание слайда:
Листьями неориентированного дерева (висячими вершинами) называются вершины, которым инцидентно лишь одно ребро. Листьями неориентированного дерева (висячими вершинами) называются вершины, которым инцидентно лишь одно ребро. Узлом (внутренней вершиной) произвольного дерева называют вершину, которая не является корнем, и не является листом.

Слайд 5


 Маршрут в любом дереве называют ветвью  Маршрут в любом дереве называют ветвью В ориентированном дереве, как и в графе, ребра называют дугами. Корнем ориентированного дерева называют вершину, полустепень захода которой равна нулю. Листьями ориентированного дерева (висячими вершинами) называются вершины, полустепень захода которых равна единице, полустепень исхода равна нулю.
Описание слайда:
 Маршрут в любом дереве называют ветвью  Маршрут в любом дереве называют ветвью В ориентированном дереве, как и в графе, ребра называют дугами. Корнем ориентированного дерева называют вершину, полустепень захода которой равна нулю. Листьями ориентированного дерева (висячими вершинами) называются вершины, полустепень захода которых равна единице, полустепень исхода равна нулю.

Слайд 6


Для графа G(v,e) эквивалентны следующие утверждения: Для графа G(v,e) эквивалентны следующие утверждения: 1) G – дерево; 2) G – связный граф, |e|=|v|–1, где e – количество ребер, v– количество вершин графа G. 3) G – ациклический граф, |e|=|v|–1; 4) G – граф, в котором две вершины соединяются единственной цепью; 5) G – ациклический граф, и добавление нового ребра приводит к появлению точно одного цикла.
Описание слайда:
Для графа G(v,e) эквивалентны следующие утверждения: Для графа G(v,e) эквивалентны следующие утверждения: 1) G – дерево; 2) G – связный граф, |e|=|v|–1, где e – количество ребер, v– количество вершин графа G. 3) G – ациклический граф, |e|=|v|–1; 4) G – граф, в котором две вершины соединяются единственной цепью; 5) G – ациклический граф, и добавление нового ребра приводит к появлению точно одного цикла.

Слайд 7


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

Слайд 8


Поддеревом дерева Т называют дерево Т1, которое содержит часть вершин дерева Т, причем корнем дерева Т1 может быть любая другая вершина дерева Т. Поддеревом дерева Т называют дерево Т1, которое содержит часть вершин дерева Т, причем корнем дерева Т1 может быть любая другая вершина дерева Т.
Описание слайда:
Поддеревом дерева Т называют дерево Т1, которое содержит часть вершин дерева Т, причем корнем дерева Т1 может быть любая другая вершина дерева Т. Поддеревом дерева Т называют дерево Т1, которое содержит часть вершин дерева Т, причем корнем дерева Т1 может быть любая другая вершина дерева Т.

Слайд 9


Корневое дерево называется n-арным, если каждая внутренняя вершина имеет не более n детей. Корневое дерево называется n-арным, если каждая внутренняя вершина имеет не более n детей. Порядком дерева называется максимальное количество потомков вершин данного дерева. Корневое дерево называется полным n-арным деревом, если каждая внутренняя вершина имеет ровно n детей. Корневое дерево называется бинарным деревом, если каждая внутренняя вершина имеет не более двух детей (n = 2).
Описание слайда:
Корневое дерево называется n-арным, если каждая внутренняя вершина имеет не более n детей. Корневое дерево называется n-арным, если каждая внутренняя вершина имеет не более n детей. Порядком дерева называется максимальное количество потомков вершин данного дерева. Корневое дерево называется полным n-арным деревом, если каждая внутренняя вершина имеет ровно n детей. Корневое дерево называется бинарным деревом, если каждая внутренняя вершина имеет не более двух детей (n = 2).

Слайд 10


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №10
Описание слайда:

Слайд 11


Пусть для некоторого множества М городов известна стоимость с(a, b) постройки дороги между любыми двумя городами a, b  M. Какова должна быть сеть дорог между городами, входящими в М, чтобы по ней можно было проехать из любого города aM в любой город bM и чтобы стоимость этой сети была минимальной? Пусть для некоторого множества М городов известна стоимость с(a, b) постройки дороги между любыми двумя городами a, b  M. Какова должна быть сеть дорог между городами, входящими в М, чтобы по ней можно было проехать из любого города aM в любой город bM и чтобы стоимость этой сети была минимальной?
Описание слайда:
Пусть для некоторого множества М городов известна стоимость с(a, b) постройки дороги между любыми двумя городами a, b  M. Какова должна быть сеть дорог между городами, входящими в М, чтобы по ней можно было проехать из любого города aM в любой город bM и чтобы стоимость этой сети была минимальной? Пусть для некоторого множества М городов известна стоимость с(a, b) постройки дороги между любыми двумя городами a, b  M. Какова должна быть сеть дорог между городами, входящими в М, чтобы по ней можно было проехать из любого города aM в любой город bM и чтобы стоимость этой сети была минимальной?

Слайд 12


Остовное дерево – дерево, которое содержит все вершины исходного графа. Остовное дерево – дерево, которое содержит все вершины исходного графа. Хорда остовного дерева Н графа G – это ребро графа G, не принадлежащее остовному дереву Н.
Описание слайда:
Остовное дерево – дерево, которое содержит все вершины исходного графа. Остовное дерево – дерево, которое содержит все вершины исходного графа. Хорда остовного дерева Н графа G – это ребро графа G, не принадлежащее остовному дереву Н.

Слайд 13


Граф G с весами на дугах называется взвешенным графом. Граф G с весами на дугах называется взвешенным графом. Весом подграфа из G называется сумма весов ребер подграфа.
Описание слайда:
Граф G с весами на дугах называется взвешенным графом. Граф G с весами на дугах называется взвешенным графом. Весом подграфа из G называется сумма весов ребер подграфа.

Слайд 14


Упорядочиваем ребра в порядке возрастания их весов. Упорядочиваем ребра в порядке возрастания их весов. Включаем в остовное дерево, ребра в порядке их возрастания. Если вновь включенное ребро образует цикл с ребрами, включенными до него, то пропускаем его. Дерево построено тогда, когда в него включено n-1 ребро.
Описание слайда:
Упорядочиваем ребра в порядке возрастания их весов. Упорядочиваем ребра в порядке возрастания их весов. Включаем в остовное дерево, ребра в порядке их возрастания. Если вновь включенное ребро образует цикл с ребрами, включенными до него, то пропускаем его. Дерево построено тогда, когда в него включено n-1 ребро.

Слайд 15


Построить дерево минимальной стоимости для заданного графа G. Построить дерево минимальной стоимости для заданного графа G.
Описание слайда:
Построить дерево минимальной стоимости для заданного графа G. Построить дерево минимальной стоимости для заданного графа G.

Слайд 16


1) Вводится последовательность Np = (1, 2,..., р), где p – количество вершин графа. 1) Вводится последовательность Np = (1, 2,..., р), где p – количество вершин графа. 2) Выбирается висячая вершина с наименьшим номером, эта вершина удаляется из последовательности Np=(1,2,...,р), а номер связанной с ней вершины записывается. 3) Затем этот процесс повторяется до тех пор, пока не получим последовательность а(Т)=(a1,а2,...,ар-2).
Описание слайда:
1) Вводится последовательность Np = (1, 2,..., р), где p – количество вершин графа. 1) Вводится последовательность Np = (1, 2,..., р), где p – количество вершин графа. 2) Выбирается висячая вершина с наименьшим номером, эта вершина удаляется из последовательности Np=(1,2,...,р), а номер связанной с ней вершины записывается. 3) Затем этот процесс повторяется до тех пор, пока не получим последовательность а(Т)=(a1,а2,...,ар-2).

Слайд 17


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №17
Описание слайда:

Слайд 18


Находим общее количество вершин (количество вершин в коде дерева + 2); Находим общее количество вершин (количество вершин в коде дерева + 2); Находим висячие вершины (т.е. которые не входят в код); Находим висячую вершину с минимальным номером и соединяем ее с первой неиспользованной вершиной в коде. Если выбранная вершина не встречается далее в последовательности кода, записываем ее вершину в последовательности листьев; Повторяем пункт 3), до использования всех листьев; Последнюю вершину кода соединяем с листом с максимальным номером.
Описание слайда:
Находим общее количество вершин (количество вершин в коде дерева + 2); Находим общее количество вершин (количество вершин в коде дерева + 2); Находим висячие вершины (т.е. которые не входят в код); Находим висячую вершину с минимальным номером и соединяем ее с первой неиспользованной вершиной в коде. Если выбранная вершина не встречается далее в последовательности кода, записываем ее вершину в последовательности листьев; Повторяем пункт 3), до использования всех листьев; Последнюю вершину кода соединяем с листом с максимальным номером.

Слайд 19


Дан код: 1, 1, 1, 5. Необходимо построить дерево. Дан код: 1, 1, 1, 5. Необходимо построить дерево. Решение. 1. Общее количество вершин: 2. Находим висячие вершины:
Описание слайда:
Дан код: 1, 1, 1, 5. Необходимо построить дерево. Дан код: 1, 1, 1, 5. Необходимо построить дерево. Решение. 1. Общее количество вершин: 2. Находим висячие вершины:

Слайд 20


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №20
Описание слайда:

Слайд 21


Бинарным (двоичным) деревом Т называется упорядоченное дерево, из каждой вершины которого может исходить не более двух дуг. Бинарным (двоичным) деревом Т называется упорядоченное дерево, из каждой вершины которого может исходить не более двух дуг.
Описание слайда:
Бинарным (двоичным) деревом Т называется упорядоченное дерево, из каждой вершины которого может исходить не более двух дуг. Бинарным (двоичным) деревом Т называется упорядоченное дерево, из каждой вершины которого может исходить не более двух дуг.

Слайд 22


Каждая вершина бинарного дерева может иметь либо двух сыновей – левого и правого, либо иметь только левого сына, либо только правого сына, либо не иметь ни одного сына. Каждая вершина бинарного дерева может иметь либо двух сыновей – левого и правого, либо иметь только левого сына, либо только правого сына, либо не иметь ни одного сына. Поддерево, корень которого является левым сыном вершины v, называется левым поддеревом вершины v. Поддерево, корень которого является правым сыном вершины v, называется правым поддеревом вершины v.
Описание слайда:
Каждая вершина бинарного дерева может иметь либо двух сыновей – левого и правого, либо иметь только левого сына, либо только правого сына, либо не иметь ни одного сына. Каждая вершина бинарного дерева может иметь либо двух сыновей – левого и правого, либо иметь только левого сына, либо только правого сына, либо не иметь ни одного сына. Поддерево, корень которого является левым сыном вершины v, называется левым поддеревом вершины v. Поддерево, корень которого является правым сыном вершины v, называется правым поддеревом вершины v.

Слайд 23


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №23
Описание слайда:

Слайд 24


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №24
Описание слайда:

Слайд 25


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №25
Описание слайда:

Слайд 26


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №26
Описание слайда:

Слайд 27


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №27
Описание слайда:

Слайд 28


Деревья. Эквивалентные и подобные бинарные деревья. (Лекции 13-14), слайд №28
Описание слайда:

Слайд 29


Два бинарных дерева называются подобными, если они имеют одинаковую структуру, то есть либо они пусты, либо содержат одинаковое число поддеревьев и их левое и правое поддеревья подобны. Два бинарных дерева называются подобными, если они имеют одинаковую структуру, то есть либо они пусты, либо содержат одинаковое число поддеревьев и их левое и правое поддеревья подобны.
Описание слайда:
Два бинарных дерева называются подобными, если они имеют одинаковую структуру, то есть либо они пусты, либо содержат одинаковое число поддеревьев и их левое и правое поддеревья подобны. Два бинарных дерева называются подобными, если они имеют одинаковую структуру, то есть либо они пусты, либо содержат одинаковое число поддеревьев и их левое и правое поддеревья подобны.

Слайд 30


Бинарные деревья эквивалентны, если они подобны и соответствующие узлы содержат одну и ту же информацию. Бинарные деревья эквивалентны, если они подобны и соответствующие узлы содержат одну и ту же информацию.
Описание слайда:
Бинарные деревья эквивалентны, если они подобны и соответствующие узлы содержат одну и ту же информацию. Бинарные деревья эквивалентны, если они подобны и соответствующие узлы содержат одну и ту же информацию.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию