Деревья и их свойства.

Дерево - это частный случай графа, наиболее широко применяемый в программировании.

Основные определения

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

Дерево - это связный граф без циклов.

Дерево - это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

Дерево - это граф, между любыми двумя вершинами которого существует ровно один путь.

Аналогичным образом определяется и ориентированное дерево - как орграф, в котором между любыми двумя вершинами существует не более одного пути.

Деревом называют конечный связный граф с выделенной вершиной (корнем), не имеющей циклов.

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

Расстояние до корневой вершины V₀ называется ярусом s вершины.

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

При удалении ребра единственный маршрут прерывается и граф распадается на два подграфа.

Корневое дерево - это ориентированное дерево, в котором можно выделить вершины трех видов: корень, листья (другое их название: терминальные вершины) и остальные вершины (нетерминальные); причем должны выполняться два обязательных условия:

из листьев не выходит ни одна дуга; из других вершин может выходить сколько угодно дуг;

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

Традиционно в математике и в родственных ей науках (в том числе и в теоретическом программировании) деревья "растут" вниз головой: это делается просто для удобства наращивания листьев в случае необходимости. Таким образом, на рисунках корень дерева оказывается самой верхней вершиной, а листья - самыми нижними.

Предок вершины v - это вершина, из которой исходит дуга, заходящая в вершину v. Потомок вершины v - это вершина, в которую заходит дуга, исходящая из вершины v. В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков.

Бинарное дерево - это корневое дерево, каждая вершина которого имеет не более двух потомков. В таком случае иногда говорят о левом потомке и правом потомке для текущей вершины.

Высота корневого дерева - это максимальное количество дуг, отделяющих листья от корня. Если дерево не взвешенное, то его высота - это просто расстояние от корня до самого удаленного листа.

Свойства деревьев.

Граф G(V,X) является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

4. Граф G(V,X) связен и не содержит циклов.

5. Граф G(V,X) связный , но утрачивает это свойство после удаления любого ребра.

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

Висячие вершины, за исключением корневой, называют листьями.

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

Подграф G1 = (V1, E1) графа G = (V, E), называется остовным деревом в

графе G = (V, E), если G1 = (V1, E1) — дерево и V1 = V.