ЭМБРИОНАЛЬНОЕ РАЗВИТИЕ

 

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

1. существует единственный узел, полустепень захода которого равна 0. Он называется корнем ордерева;

2. полустепень захода всех остальных узлов равна 1;

3. каждый узел достижим из корня.

(ориентированные деревья)

Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние от корня до узла.

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

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

Наиболее характерные свойства деревьев, которые одновременно служат эквивалентными определениями дерева, сформулируем в следующей теореме.

Граф G(v,x) (v=n>1) является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

v граф G(v,x) связен и не содержит циклов;

v граф G(v,x) не содержит циклов и имеет n-1 ребро;

v граф G(v,x) связен и имеет n-1 ребро;

v граф G(v,x) не содержит циклов, но добавление ребра между несмежными вершинами приводит к появлению одного и только одного простого цикла;

v граф G(v,x) связный, но утрачивает это свойство после удаления любого ребра;

v в графе G(v,x) всякая пара вершин соединена цепью и причем только одной

Итак, дерево с n вершинами имеет n-1 ребро, поэтому оно будет минимальным связным графом. Висячие вершины, за исключением корневой, называются листьями.

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

При описании деревьев принято использовать термины: отец, сын, предок, потомок.

Каждая вершина дерева называется узлом, причем каждый узел является корнем дерева, имеющего n поддеревьев. Тогда узел без поддеревьев называется листом и является висячей вершиной. Узел к-го яруса называется отцом узла (к+1)-го яруса, если они смежны. Узел (к+1) ярус называется сыном узла к-го яруса. Два узла, имеющие одного отца, называются братьями.

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

В информатике принято использовать подмножество множества деревьев, когда каждый узел либо является листом, либо образует два поддерева: левое и правое. Такой вид деревьев называется бинарными деревьями и используется при делении множества на два взаимоисключающих подмножества по какому-то признаку. Для отца А – сыновья В и С, причем В – левый, а С – правый потомки. Строго бинарным деревом называется такой граф, у которого каждый узел, не являющийся листом, содержит два и только два поддерева – левое и правое.

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

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

ЭМБРИОНАЛЬНОЕ РАЗВИТИЕ