AOP_Tom1 (1021736), страница 111
Текст из файла (страница 111)
упр. 4). Таким образом, получаем А(з) = г + зг + 2зз + 4зя + 9зь + 20зе + 48вт + 115гв + 286г~+ 719зю+ 1842ам+ . (4) Теперь, когда число ориентированных деревьев найдено, интересно было бы определить количество структурно различных свободных дерееьев с п вершинами. Существует только два различных свободных дерева с четырьмя вершинами, а именно (5) так как два первых и два последних дерева (1) будут тождественны, если не прини- мать во внимание направление. Как было показано выше, в свободном дереве в качестве корня можно выбрать любую вершину Х и единственным образом задать направления ребер так, что это дерево станет ориентированным с корнем Х. Допустим, что для заданной вершины Х корень Х содержит к поддеревьев с вы вы..., вь вершинами в данных поддеревьях.
Ясно, что я — это количество дуг, которые касаются вершины Х, а в1+ вт + . ° + вь = и — 1. Тогда весом (шеьуЫ) вершины Х назовем величину п1ах(вм вэ,..., вь), Таким образом, вершина Р дерева (б) к н имеет вес 3 (каждое из поддеревьев вершины Р содержит по три из девяти остальных вершин), а вершина Е имеет вес шах(7,2) = 7. Вершина с минимальным весом называется ценгпраидом (сеп1гогд) свободного дерева.
Пусть Х и вы вэ,, аь определены так же, как выше, и пусть уы 1'э,..., Уев корни поддеревьев, которые выходят из Х. Вес 3'~ должен быть по крайней мере равен п — в1 — — 1+ в2+. + вь, поскольку, если предполагается, что У~ — корень, в его поддереве существует п — в1 вершин и Х в том числе. Если поддерево У) содержит цептроид У, получим высота (Х) = шах (вы вэ,..., вь) > высота(У) > 1+ вэ + + вь. Это возможно, только если в1 > вэ + . + вь, Аналогичный результат можно получить, если вместо У~ в данных рассуждениях использовать 1'. Поэтому центронд может находиться не более чем в одном поддереве данной вершины.
Это довольно "сильное" условие, из которого следует, что в свободном дереве существует не более двух центропдов я, если имеются два центронда, онн являются смежными (см. упр. 9). И наоборот, если в1 > вэ+ . + вы в поддереве Ъ~ имейся цеитроид, так как высота(11) < шах(в, — 1, 1+вэ+ +вь) < в1 — — высота(Х) и вес всех узлов в поддеревьях Ъ~,,1'ь по крайней мере равен вг + 1. Таким образом доказано, что вершина Х является единственным центрондом свободного дерева тогда и только тогда, когда в < в1 + + вь — в для 1 < 7' < й.
(7) Следовательно, количество свободных деревьев с и вершинами, имеющих только один цеитроид, равно количеству ориентированных деревьев с и вершинами минус количество таких ориентированных деревьев, для которых нарушается условие (7). К последним относятся ориентированные деревья с вз вершинами и ориентированные деревья с п — и < в вершинами. Тогда количество свободных деревьев с одним цеитроидом равно (8) цп п1аь-1 птцп-э ' ' ' а1ь/2~а(п/21 Свободное дерево с двумя центроидамя имеет четное количество вершин, а вес каждого центроида равен и/2 (см. упр.
10). Поэтому, если и = 27п, количество свободных деревьев е двумя центроидами равно количеству вариантов выбора двух объектов из а,ч объектов с повторением, а именно: (а +1) Следовательно, чтобы получить общее количество свободных деревьев, сложим ;,'а,нв(а„~з + 1) с (8) для четных и. Взглянув на выражение (8), можно предложить простую производшцую функцию. И действительно, лргко получить, что производящая функция для структурно различных свободных деревьев равна Е(я) = А(з) — — А(т) + -А(г ) г 1 з 2 2 з+ зг+,з+ 2хч+ 8„э+бсв + 11гт+28зв + 47гэ+ 106сш+ 235с" + ... (9) Это простое соотношение между Е(х) и А(з) впервые было получено М.
Э. К. Джорданом (М. Е. С. Зогбал), который занимался исследованием данной задачи еще в 1869 голу. Приступим теперь к задаче о перечислении упорядоченных деревьев, которые имеют особо существенное значение для программирования компьютерных алгоритмов. На основе четырех вершин можно построить пять следующих структурно различных упорядоченных деревьев: (10) Первые два являются идентичными, если рассматривать их как ориентированные деревья, поэтому только одно из них было показано выше, в (1).
Прежде чем перейти к подсчету различных упорядоченных древовидных структур, рассмотрим бинарные деревья, так как они ближе к действительному представлению данных внутри компьютера и их проще исследовать. Пусть ܄— количество различных бинарных деревьев с и узлами. Согласно определению бинарных деревьев очевидно, что Ьо — — 1 и для и > 0 количество их различных вариантов равно числу способов расположения бинарного дерева с Ь узлами слева от корня и другого бинарного дерева с п — 1 — Ь узлами справа.
Поэтому п > 1. Ь = ЬеЬ„~ + Ь~Ь„-з + + д ~Ьо, Из данного соотношения ясно, что производящая функция В(е) = Ьо + Ь,з+ Ьзз'+ удовлетворяет уравнению (12) Решая это квадратное уравнение с учетом того факта, что В(0) = 1, получим 1 . 1/ /'1 В(з) (1 ~/1 43 ) =.~ 1 '~~ 2 ( 43) 23 23~ 1,Й) ь>о =24 ( )( 4)"=ь ( ) =;;:(.) ~ = 1 + в + 232 + 533 + 1434 + 42вь + 132зв + 42932 + 1430вв + 4862в~ + 16796зш + . (13) (См, упр, 1.2.6 — 47.) Следовательно, искомый ответ таков: (14) По формуле Стирлинга это асимптотически равно 4"/ит/тип+0(4" и в/2).
Некоторые важные обобщения уравнения (14) приводятся в упр. 11 и 32. Возвращаясь к задаче о подсчете упорядоченных деревьев с и узлами, видим, что, по сути, это задача о вычислении количества бинарных деревьев, так как ранее было установлено естественное соответствие между бинарными деревьями и лесами, а дерево минус корень как раз и является лесом. Следовательно, количество упорядоченных деревьев с и вершинами равно 5„м т.
е. количеству бинарных деревьев с и — 1 вершинамп. При выполнении приведенных выше перечислений предполагалось, что вершины являются неразличимыми. Если отметить ярлыками вершины 1-4 из (1) и считать корнем вершину 1, то получится 16 различных ориентированных деревьев. 2 4 2 3 3 4 3 2 4 3 4 2 2 2 3 3 4 4 4 3 4 2 3 2 1 (15) Ясно, что задача перечисления помеченных деревьев существенно отличается от описанной выше задачи. В этом случае ее можно перефразировать так: "Рассмотрим три линии, проходящие от вершин 2-4 к другой вершине. Для каждой из них су~цествует три варианта, а в целом имеется 23 = 27 вариантов.
Сколько из них соответствует различным ориентированным деревьям с корнем 1?". Как показано выше, таких вариантов 16. Аналогичная формулировка той же задачи для и вершин звучит следующим образом: "Пусть /(я) — такая целочисленная функция, что /(1) = 1 и 1 < /(т) < и для всех целых 1 < х < и. Назовем / отображением дерева (1гее таррту), если г(")(я), т. е. выполненная п раз итерация у(1( (1(х)) )) этой функции равна 1 для всех х. Сколько в таком случае существует отображений дерева?". Эта задача возникает, например, в связи с генерированием случайных чисел.
К большому удивлению, можно обнаружить, что в среднем точно одна из каждых и таких функций г является отображением дерева. Можно легко решить задачу перечисления с помощью общих формул для подсчета поддеревьев графа, которые получены в предыдущих разделах (см. упр. 12). Однако существует и более информативный способ решения, который позволяет получить новый и компактный метод представления ориентированной древовидной структуры. Предположим, что дано ориентированное дерево с вершинами (1,2,...,п) и дугами и — 1, которые проходят от у к 1(у) для всех у, за исключением корня.
В нем существует по крайней мере одна концевая вершина (лист), поэтому предположим, что Ъ~ — наименьший номер листа. Если и > 1, запишем ((1'~) и удалим из дерева веРшинУ 7~ и дУгУ Ъ~ -Э 1(Ъ~). ПУсть Уэ — наименьший номеР листа, котоРый получился в результате предыдущей операции. Если п > 2, запишем ((Уэ) и удалим вершину Уэ и дугу 1з -+ ((Уз) из дерева, а затем будем продолжать в таком духе до тех пор, пока из данного дерева не будут удалены все вершины, кроме корня.
Таким образом получим последовательность из и — 1 чисел (16) которая называется капоническим предстпаелением (сапотса1 гергевеп1ай пп) исходного ориентированного дерева. Например, ориентированное дерево (17) с 10 вершинами имеет такое каноническое представление; 1, 3, 10, 5. 10, 1, 3, 5, 3. Важной особенностью здесь является возможность обращения данного процесса и перехода от рассмотрения произвольной последовательности из и — 1 чисел (16) к рассмотрению ориентированного дерева, которое порождает эту последовательность.
Действительно, рассмотрим произвольную последовательность яы яе, ..., я„~ чисел от 1 до п. Пусть У~ — это наименьшее число, которое не представлено в последовательности хы ..,, я„ы а Уэ — это наименьшее число ф Уы которое не представлено в последовательности яг,...,х„~ и т. д. Получив, таким образом, перестановку Ъ~Ув... У„целых чисел (1,2,..., и), проведем дуги от вершины У к вершине х для 1 < у < и и получим ориентированный граф без ориентированных циклов, который согласно результату упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
