Основные определения. Дерево – связный граф без циклов

Дерево – связный граф без циклов. Лес (или ациклический граф) – неограф без циклов. Компонентами леса являются деревья.

Теорема 14.1. Для неографа G с n вершинами без петель следующие условия эквивалентны:

1) G – дерево;

2) G – связной граф, содержащий n – 1 ребро;

3) G – ациклический граф, содержащий n – 1 ребро;

4) Любые две несовпадающие вершины графа G соединяет единственная цепь;

5) G – ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.

Теорема 14.2. Неограф G является лесом тогда и только тогда, когда коранг графа v(G)=0.

Висячая вершина в дереве – вершина степени 1. Висячие вершины называются листьями, все остальные – внутренними вершинами.

Если в дереве особо выделена одна вершина, называемая корнем, то такое дерево называется корневым, иначе – свободным.

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

Вершины дерева, удаленные на расстояние k (в числе дуг) от корня, образуют k -й ярус (уровень) дерева. Наибольшее значение k называется высотой дерева.

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