Дополнение. Деревья.

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

Теорема 6. Пусть - связный неориентированный граф с выделенной вершиной. Тогда следующие свойства эквивалентны:

1). - дерево;

2). В графе нет простых циклов (в частности петль);

3). Любые две вершины графа связаны единственной простой цепью;

4). Число ребер на 1 меньше числа вершин: = - число вершин графа.

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

Замечание. Деревья часто рисуют корнем вверх, поэтому вместо высоты дерева говорят о его глубине.

Рис 8. Дерево. - корень

На рисунке 8 изображено дерево высоты (глубины) 3. Вершины и - первого уровня, вершины , , - второго уровня, , , , - третьего уровня (листья).