Летние международные олимпиады для 1-11 классов Участвовать→
Конкурс разработок «Пять с плюсом» июнь 2021
Добавляйте свои материалы в библиотеку и получайте ценные подарки
Конкурс проводится с 1 июня по 30 июня

Конспект лекции по теме "Ориентированные деревья"

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

Тема: Ориентированные деревья

 

Деревья являются простейшим классом графов, для которых выполняются все свойства графов, в том числе и специфические для определѐнных видов.

Опр.: Граф без циклов называется ациклическим или лесом.

Опр.: Связный ациклический граф называется деревом.

image 

Опр.: Граф, для которого выполняется соотношение р = в – 1, где р – число рѐбер, в – число вершин, называется древовидным.

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

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

1.      G – любое дерево, т.е. связный граф без циклов.

2.      Любые две вершины соединены в G единственной простой цепью.

3.      G – связный граф и любое ребро есть мост. 

4.      G – связный и древовидный.

5.      G – ациклический и древовидный.

6.      g – ациклический и субциклический.

7.      g – связный, субциклический и неполный.

8.      g – древовидный и субциклический.

Замечание: В любом дереве найдѐтся по крайней мере 2 висячие вершины. Ориентированные деревья (ордеревья)

Ордерево является структурой иерархических отношений и используется в программировании и математике.

Опр.: Ориентированным деревом (ордеревом или корневым дерево) называется ориентированный граф со следующими свойствами:

1.      Существует единственный узел, число входящих дуг которого равно 0. узел – корень дерева.

1

2.      Число дуг, входящих в другие узлы равно 1.

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

Пример:

image                                                                       image                                                   

 

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

1.      р = в – 1

2.      Если в ордереве отменить ориентацию рѐбер, то получится свободное дерево.

3.      В ордереве нет контуров.

4.      Для каждого узла единственный существующий путь, ведущий в этот узел.

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

(это ордерево называется поддеревом узла ).

6.      Если в свободном дереве любую вершину назначить корнем, то получится ордерево.

Опр.: Множество узлов Т1,…, Тк (исключающих корень) ордерева называются поддеревьями. Опр.: Если относительный порядок поддеревьев Т1,…, Тк фиксирован, то ордерево называется упорядоченным.

Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить.

Опр.: Ордерево называется выровненным, если все узлы, степень которых < 2, располагаются на одном или двух последних уровнях. 

image

Невыровненный                                           Выровненный              

Опр.: Концевая вершина ордерева называется листом.

Опр.: Путь из корня в лист называется ветвью.

Опр.: Длина наибольшей ветви называется высотой дерева.

Опр.: Расстояние от корня до узла называется уровнем. (Корень имеет уровень 0).

Опр.: Узлы, находящиеся на одном уровне называются ярусом дерева.

Опр.: Узлы, достижимые из корня называются потомками.

Если есть дуга, соединяющая узлы в1 и в2, то в1 – отец, а в2 – сын.

Сыновья одного отца – братья.

 

2

Информация о публикации
Загружено: 26 марта
Просмотров: 82
Скачиваний: 0
Фоминых Ирина Владимировна
Прочее, СУЗ, Уроки

Проверьте знания своих учеников интересными заданиями

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

Скачать материал