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

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

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

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

Рис. 1

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

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

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

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

Граф G не содержит циклов, поэтому ни одно его ребро не является петлей, т. е. концевые вершины любого ребра различны. Предположим, что степень любой вершины графа G превосходит 1. Пусть v 1, v 2 – пара вершин, соединенных ребром a 1. Так как степень вершины v 2 больше 1, имеется ребро a 2, отличное от a 1, соединяющее вершину v 2 с некоторой вершиной v 3. Вершины v 1 и v 3 должны различаться, иначе путь v 1, a 1, v 2, a 2 v 3 являлся бы циклом. Пользуясь тем, что степень вершины v 3 больше 1, можно продолжить путь v 1, a 1, v 2, a 2 v 3 ребром a 3, отличным от a 2, соединяющим вершину v 3 с некоторой вершиной v 4. Вершина v 4 должна отличаться от всех предыдущих вершин построенного пути (иначе получается цикл). Подобным образом можно построить сколь угодно длинный путь, на котором все вершины различны. С другой стороны, любой путь, длина которого превосходит число вершин графа, должен содержать повторяющиеся вершины. Таким образом, предположение об отсутствии висячих вершин на графе 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, сумма степеней вершин графа равна удвоенному числу ребер:

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

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

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

Не нашли, что искали? Воспользуйтесь поиском: