Как было показано выше, в свободном дереве в качестве корня можно выбрать любую вершину X и единственным образом задать направления ребер так, что это дерево станет ориентированным с корнем X. Допустим, что для заданной вершины X корень X содержит к поддеревьев с Si,S2,..., Sjt вершинами в данных поддеревьях. Ясно, что к - это количество дуг, которые касаются вершины X, а si + S2 + • • • + Sfc = n - 1. Тогда весом {weight) вершины X назовем величину max(si, S2,..., Sfc). Таким образом, вершина D дерева

к н

имеет вес 3 (каждое из поддеревьев вершины D содержит по три из девяти остальных вершин), а вершина Е имеет вес шах(7,2) = 7. Вершина с минимальным весом назьшается центроидом {centroid) свободного дерева.

Пусть X и si, S2, ,Sk определены так же, как выше, и пусть Y\,Y2, . ,Yk - корни поддеревьев, которые выходят из X. Вес Fi должен быть по крайней мере

равен n - si = I + S2-I-----hs, поскольку, если предполагается, что Fi - корень, в его

поддереве существует п - si вершин и X в том числе. Если поддерево Fi содержит центроид Y, получим

высота{X) = max(si,«2,• ,Sk) > высота(F) > I + + • + Sk-

Это возможно, только если si > S2 + + Sk- Аналогичный результат можно получить, если вместо Fi в данных рассуждениях использовать Yj. Поэтому центроид может находиться не более чем в одном поддереве данной вершины.

Это довольно "сильное" условие, из которого следует, что в свободном дереве существует не более двух центроидов и, если имеются два центроида, они являются смежными (см. упр. 9).

И наоборот, если si > S2 +----h s, в поддереве Fi имеется центроид, так как

высота (Fl) < max (si - 1, 1 -f- S2 -Ь----1- Sk) < si - высота (X)

и вес всех узлов в поддеревьях l2,---,Ft по крайней мере равен Si -f- 1. Таким образом доказано, что вершина X является единственным центроидом свободного дерева тогда и только тогда, когда

Sj < si +----\- Sk - Sj для I <j <к. (7)

Следовательно, количество свободных деревьев с п вершинами, имеющих только один центроид, равно количеству ориентированных деревьев с п вершинами минус количество таких ориентированных деревьев, для которых нарушается условие (7). К последним относятся ориентированные деревья с Sj вершинами и ориентированные деревья с п - Sj < Sj вершинами. Тогда количество свободных деревьев с одним центроидом равно

а„ - aia„ i - а2а„ 2-----a[n/2ja[n/2l (8)

Свободное дерево с двумя центроидами имеет четное количество вершин, а вес каждого центроида равен п/2 (см. упр. 10). Поэтому, если п = 2т, количество свободных деревьев « двумя центроидами равно количеству вариантов выбора двух объектов из От объектов с повторением, а именно:

Следовательно, чтобы получить общее количество свободных деревьев, сложим ап/2(Оп/2 + 1) с (8) для четных п. Взглянув на выражение (8), можно предложить простую производящую функцию. И действительно, лргко получить, что производящая функция для структурно различных свободных деревьев равна

F{z) = A{z) -\a{z) + \a{z)

= z + z + z + 2z-\- 2,z + &z + lU + 22,z

+ 473 + 1061° + 235" +

Это простое соотношение между F{z) и A[z) впервые было получено М. Э. К. Джорданол(1 (М. Е. С. Jordan), который занимался исследованием данной задачи еще в 1869 году.

Приступим теперь к задаче о перечислении упорядоченных деревьев, которые имеют особо существенное значение для программирования компьютерных алгоритмов. На основе четырех вершин можно построить пять следующих структурно различных упорядоченных деревьев:

(10)

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

Прежде чем перейти к подсчету различных упорядоченных древовидных структур, рассмотрим бинарные деревья, так как они ближе к действительному представлению данных внутри компьютера и их проще исследовать. Пусть 6„ - количество различных бинарных деревьев с п узлами. Согласно определению бинарных деревьев очевидно, что 6о = 1 и для п > О количество их различных вариантов равно числу способов расположения бинарного дерева с к узлами слева от корня и другого бинарного дерева с п - 1 - А: узлами справа. Поэтому

Ьп = bobn-\-\-bibn-i Л-----bbn-ibo, п > 1.

Из данного соотношения ясно, что производящая функция

B{z) - bo biz + biz +

удовлетворяет уравнению

zB{zf B{z) - 1.

(12)

Решая это квадратное уравнение с учетом того факта, что В{0) = 1, получим

n>0 п>0

\ п J п + 1

п>0

п + 1

= 1 +z + 2z + Ъг + 142 + 422 + 132 + 4292

+ 14302* + 48622 + 167962° + • • •. (13)

(См. упр. 1.2.6-47.) Следовательно, искомый ответ таков:

1 f2n п + 1 \ п

Ь„ =

(14)

По формуле Стирлинга это асимптотически равно 4"/nV7m+0(4"n""/). Некоторые важные обобщения уравнения (14) приводятся в упр. 11 и 32.

Возвращаясь к задаче о подсчете упорядоченных деревьев с п узлами, видим, что, по сути, это задача о вычислении количества бинарных деревьев, так как ранее было установлено естественное соответствие между бинарными деревьями и лесами, а дерево минус корень как раз и является лесом. Следовательно, количество упорядоченных деревьев с п вершинами равно 6„ i, т. е. количеству бинарных деревьев с п - 1 вершинами.

При выполнении приведенных выше перечислений предполагалось, что вершины являются Fiepaзличимыми. Если отметить ярлыками вершины 1-4 из (1) и считать корнем вершину 1, то получится 16 различных ориентированных деревьев.

1а 1а 1а 1а 1а 1а 1 1» It 1» 1 1

2 3 4

(15)

Ясно, что задача перечисления помеченных деревьев существенно отличается от описанной выше задачи. В этом случае ее можно перефразировать так: "Рассмотрим три линии, проходящие от вершин 2-4 к другой вершине. Для каждой из них существует три варианта, а в целом имеется 3 = 27 вариантов. Сколько из них соответствует различным ориентированным деревьям с корнем 1?". Как показано выше, таких вариантов 16. Аналогичная формулировка той же задачи для п вершин звучит следующим образом: "Пусть f{x) -такая целочисленная функция, что /(1) = 1 и 1 < f{x) < п для всех целых 1 < а; < п. Назовем / отображением, дерева