Деревья.(ориентированные, сбалансированные, бинарные, остовные)

Деревом называют связный граф, не содержищий циклов. т.к любой граф без циклов называются лесом, то компонентами леса являются деревья.

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

Висячая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви называется высотой ордерева.

Расстояиние от корня до некоторой вершины называется уровнем вершины. Сам корень имеет уровень 0. Вершины одного уровня образуют ярус дерева.

 

Бинарным деревом называется ордерево, из каждой вершины которого выходит не более двух дуг.

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

 

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