Модель данных и их использование. Язык моделирования uml, для выражения и документирования соответствующей модели данных для задачи вычислительной техники

О самом большом дереве, о самой короткой и самой длинной дороге, сетевом планировании, потоках видов коммуникаций.

Выполнил студент группы 618-21

План.

• 1. Дерево
• 2. Двоичное дерево 3. Неориентированное дерево 4. Ориентированное дерево
• 5. n-арное дерево

Дерево

Дерево — это связный ациклический граф. Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.

иже приведен пример дерева.

Двоичное дерево

• иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево является упорядоченным ориентированным деревом[1].
• Для практических целей обычно используют два подвида двоичных деревьев — двоичное дерево поиска и двоичная куча.

Двоичное дерево

Существует следующее рекурсивное определение двоичного дерева (см. БНФ):

<двоичное дерево> ::= ( <данные> <двоичное дерево> <двоичное дерево> ) | null .

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

Например, показанное справа на дерево согласно этой грамматике можно было бы записать так:

Неориентированное дерево

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

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

B
G
I
C
E
F
H
J
K
D
A

Ориентированное дерево

Маршрут в любом дереве называют ветвью

В ориентированном дереве, как и в графе, ребра называют дугами.

Корнем ориентированного дерева называют вершину, полустепень захода которой равна нулю.

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

B
A
G
I
C
E
F
H
J
K
D

n-арное дерево

Корневое дерево называется n-арным, если каждая внутренняя вершина имеет не более n детей.

Порядком дерева называется максимальное количество потомков вершин данного дерева.

Корневое дерево называется полным n-арным деревом, если каждая внутренняя вершина имеет ровно n детей.

Корневое дерево называется бинарным деревом, если каждая внутренняя вершина имеет не более двух детей (n = 2).

Спасибо за внимание !