Формула Кэли

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

Теорема 3.6 (Кэли). Число различных деревьев, которые можно построить на n данных вершинах, равно: t_n = n^n-2.

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

1, 2, 3, ... , n. (*)

Установим теперь взаимно однозначное соответствие между множеством всех деревьев с n вершинами и множеством всех векторов (со значениями компонент от 1 до n) длиной (n-2).

Согласно третьему свойству, в дереве Т найдутся хотя бы две концевые вершины. Обозначим через b₁ первую концевую вершину в последовательности (*), а через e₁=(a₁,b₁) - соответствующее концевое ребро. Удалив из дерева Т ребро e₁ и вершину b₁, мы получим новое дерево T₁. Для T₁ найдётся первая в последовательности (*) концевая вершина b₂ с ребром e₂=(a₂,b₂), удалив которое, получим дерево T₂ и т.д. Наконец, после удаления ребра e_n-2=(a_n-2,b_n-2) останется единственное ребро e_n-1=(a_n-1,b_n-1), соединяющее две оставшиеся вершины. Тогда вектор (a₁,a₂,..., a_n-2) однозначно определяется деревом Т и двум различным деревьям соответствуют разные векторы.

Пример. Составить вектор для данного дерева (см. рис. 3.19, а).

Решение.. Концевая вершина с самым маленьким номером - 3, а соответствующее ей концевое ребро - (2,3); поэтому принимаем a₁=2 и отсекаем это ребро.

Концевая вершина с самым маленьким номером из оставшихся - 4, а соответствующее ей концевое ребро - (2,4). Принимаем a₂=2 и отсекаем ребро. Дальше действуем аналогично.

Требуемый вектор имеет вид: (2,2,2,1,6,6).

Покажем теперь, что, наоборот, каждое дерево Т однозначно определяется вектором

(a₁,a₂,..., a_n-2) (**)

Выполним обратное построение. Если дан вектор (**), то в последовательности (*) находится первая вершина b₁, которая не содержится в (**). Это определяет ребро e₁=(a₁,b₁).

Рис. 3.19.

Далее следует удалить вершины a₁ из (**) и b₁ из (*) и продолжить построение аналогичным образом.

Пример. Восстановить дерево Т, если соответствующий ему вектор имеет вид: (1, 2, 2, 1, 4, 4, 4). (’’)

Решение. Данный вектор содержит 7 компонент, значит, дерево Т должно иметь 7+2=9 вершин. Выпишем последовательность номеров этих вершин:

1, 2, 3, 4, 5, 6, 7, 8, 9. (’)

1. В (’) находим первое число, которое не содержится в (’’), - 3. Получаем ребро (1,3).

Зачёркиваем 1 в (’’), 3 в (’); остаётся:

(2, 2, 1, 4, 4, 4), (’’) 1, 2, 4, 5, 6, 7, 8, 9. (’)

2. Первое число в (’), которое не содержится в (’’), - это 5. Получаем следующее ребро - (2,5). Зачёркиваем 2 в (’’), 5 в (’); остаётся:

(2, 1, 4, 4, 4), (’’) 1, 2, 4, 6, 7, 8, 9. (’)

Повторяя эту процедуру ещё 3 раза, получим рёбра (2,6), (1,2), (4,1), (4,7), (4,8). После этого в последовательности (’) останутся два числа - 4 и 9. Они определяют последнее ребро (4,9). Так как все рёбра известны, восстанавливаем дерево Т, схема которого приведена на рис. 3.19, б.

Итак, нам удалось установить взаимно однозначное соответствие между множеством всех деревьев с n вершинами и множеством всех векторов (со значениями компонент от 1 до n) длиной (n-2). Из взаимно однозначного соответствия этих множеств следует их равномощность.

В векторе (a₁, a₂,..., a_n-2) каждая компонента может принимать любое из n значений (от 1 до n), а всего таких компонент n. По следствию из теоремы о мощности прямого произведения можно составить n^n-2 различных векторов вида (a₁,a₂,..., a_n-2), а значит, и различных деревьев с n вершинами будет столько же. ÿ