Общее понятие дерева

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

«ветвление».

Граф (неориентированный) называется деревом, если он связен и не имеет циклов. Например, граф на рис.1 является деревом.

Рис. 1

Укажем некоторые свойства деревьев.

1. Любые две вершины дерева можно соединить ровно одной простой цепью.

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

2. Если дерево G содержит хотя бы одно ребро, на нем найдется висячая вершина.

Граф G не содержит циклов, поэтому ни одно его ребро не является петлей, т. е. концевые вершины любого ребра различны. Предположим, что степень любой вершины графа G превосходит 1. Пусть v1, v2 – пара вершин, соединенных ребром a1. Так как степень вершины v2 больше 1, имеется ребро a2, отличное от a1, соединяющее вершину v2 с некоторой вершиной v3. Вершины v1 и v3 должны различаться, иначе путь v1, a1, v2, a2 v3 являлся бы циклом. Пользуясь тем, что степень вершины v3 больше 1, можно продолжить путь v1, a1, v2, a2 v3 ребром a3, отличным от a2, соединяющим вершину v3 с некоторой вершиной v4. Вершина v4 должна отличаться от всех предыдущих вершин построенного пути (иначе получается цикл). Подобным образом можно построить сколь угодно длинный путь, на котором все вершины различны. С другой стороны, любой путь, длина которого превосходит число вершин графа, должен содержать повторяющиеся вершины. Таким образом, предположение об отсутствии висячих вершин на графе G приводит к противоречию.

3. Число ребер дерева G на единицу меньше числа его вершин.

Доказательство проведем индукцией по числу вершин. Дерево с одной вершиной не содержит ребер, так что при n = 1 имеем m = 0 – доказываемое соотношение выполняется.

Предположим теперь, что доказываемое равенство справедливо для любого дерева с n – 1 вершиной и докажем его справедливость для любого дерева с n вершинами. Пусть n ≥ 2 – число вершин, а m число ребер дерева G. Покажем, что m = n – 1. В соответствии с предыдущим пунктом дерево G содержит висячую вершину v. Удалим эту вершину вместе с инцидентным ей ребром. Легко видеть, что оставшийся граф является деревом, которое содержит n – 1 вершину и m – 1 ребро. По индуктивному предположению имеем m – 1 = n – 2. Отсюда m = n – 1.

Отметим, что последнее свойство является характеристическим.

4. Связный граф, в котором число ребер на единицу меньше числа вершин, является деревом.

Доказательство проведем индукцией по числу вершин графа n. При n = 1 граф состоит из одной вершины и не содержит ребер и, значит, является деревом. Предположим теперь, что доказываемое утверждение справедливо для всех графов, содержащих n – 1 вершину, и рассмотрим граф G с n вершинами и n – 1 ребром. Сначала заметим, что граф G содержит висячую вершину. В самом деле, как показано в 13.1, сумма степеней вершин графа равна удвоенному числу ребер:

(v1) + (v2) +…+ (vn) = 2(n – 1).

Хотя бы одно слагаемое в левой части этого равенства меньше двух (в противном случае сумма превосходила бы 2n). Пусть

для определенности, (vn) < 2. Так как граф связный, то степень любой вершины не меньше 1. Следовательно, (vn) = 1. Это означает, что вершина vn висячая. Граф G′, получающийся удалением этой вершины вместе с инцидентным ей ребром, связен, содержит n – 1 вершину и n – 2 ребра. По индуктивному предположению G′ является деревом. Но тогда и исходный граф также является деревом (ни один цикл не может содержать висячую вершину vn, а циклов, не содержащих эту вершину, нет, поскольку они должны были бы целиком находиться в G′).