► 4. [М25] (Задача Э. С. Шварца (Е. S. Schwartz) и Б. Каллика (В. KaUick).) Предположим, wi < w2 < • < wm- Покажите, что существует расширенное бинарное дерево, которое минимизирует "wjlj ч для которого концевые узлы в порядке слева направо содержат значения ил, шг, • , Шт- [Например, дерево (11) не удовлетворяет этому условию, так как веса в нем располагаются в порядке 19, 23, И, 13, 29, 2, 3, 5, 7, 17, 31, 37, 41. Мы ищем дерево, в котором веса располагаются в порядке возрастания, а это условие не всегда выполняется в построении Хаффмэна.]

5. [НМ26] Пусть

B{w,z)= ЬпрЛ",

п,р>0

где Ьпр - количество бинарных деревьев с п узлами и внутренним путем длиной р. [Таким образом,

B(w, z) = l + z + 2u)2 + (ш + 4w)z + (4ш + 2w + 8w)z + • •;

B{l,z)-функция B(z) из уравнения (13) раздела 2.3.4.4.]

a) Найдите функциональное соотношение, которое характеризует B(ui,z), обобщив 2.3.4.4-(12).

b) Используйте результат (а) для определения средней внутренней длины пути бинарного дерева с п узлами, предполагая, что каждое из ;;;{) деревьев равновероятно.

c) Найдите асимптотическое значение этой величины.

6. [16] Какое соотношение, аналогичное соотношению (2), можно установить между количеством квадратных и круглых узлов, если t-арное дерево расширить квадратными узлами, как в (1)?

7. [М21] Какое соотношение можно установить между длинами внешнего и внутреннего путей в t-арном дереве? (См. упр. 6; необходимо получить обобщение уравнения (3).)

8. [М23] Докажите справедливость формулы (7).

9. 1М21] Числа в круглых узлах дерева (И) равны сумме весов из внешних узлов соответствующих поддеревьев. Покажите, что сумма всех значений в круглых узлах равна взвешенной длине пути.

► 10. [М26] (Задача Д. Хаффмэна.) Покажите, как можно построить t-арное дерево с минимальной взвешенной длиной пути для заданных неотрицательных весов ич, шг,..., wm-Постройте оптимальное тернарное дерево для весов 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

11. [16] Существует ли связь между полным бинарным деревом (5) и десятичной системой обозначений Дьюи для бинарных деревьев, описанной в упр. 2.3.1-5?

► 12. [М20] Пусть случайным образом выбран некоторый узел бинарного дерева, причем такой выбор равновероятен для всех узлов дерева. Покажите, что средний размер поддерева с корнем в этом узле связан с длиной пути данного дерева.

13. [22] Создайте алгоритм, который на основе т весов ил < шг < • < приводит к построению расширенного бинарного дерева с минимальной взвешенной длиной пути. Представьте итоговое дерево в виде трех массивов

А[1]... А[2т - 1], L[l]... L[m - 1], Д[1]... Д[т - 1],

где L[i] и R[i] указывают на правых и левых детей внутреннего узла t, корнем является узел 1, а A[i] - это вес узла г. Исходные веса следует представить в виде весов внешних узлов Л[т], ..., А[2т - 1]. При этом в созданном алгоритме должно выполняться менее чем 2т сравнений весов. Замечание. Некоторые или все из представленных весов могут иметь отрицательное значение!

14. [25] (Задача Т. Ц. Ху (Т. С. Ни) и А. К. Такера (А. С. Tucker).) После к шагов алгоритма Хаффмэна объединенные узлы образуют лес из т - к расширенных бинарных деревьев. Докажите, этот лес имеет наименьшую обнулю взвешенную длину пути среди всех лесов, состоящих из т - к расширенных бинарных деревьев с данными весами.

15. [М25] Покажите, что алгоритм, подобный алгоритму Хаффмэна, позволяет найти расширенное бинарное дерево, которое минимизирует величины

(a) тах(ил + /l, . . . , Шт + /т)

(b) iDix + • • + Wmx" ДЛЯ заданного X > 1.

16. [М25] (Задача Ф. К. Хвана (F. К. Hwang).) Пусть два множества весов с

Wj < "j ДЛЯ 1 < < m. j=i j=i

Докажите, что минимальная взвешенная длина пути удовлетворяет неравенству

±w,lj<±wjl).

17. [НМЗО] (Задача ЧР. Глэсси (С R. Glassey) и Р. М. Карпа (R. М. Кагр).) Пусть Si, ..., Sm-i -числа во внутренних (круглых) уатах расширенного бинарного дерева, образованного с помощью алгоритма Хаффмэна, расположенные в порядке его построения. Пусть si, ..., sm-\ - веса внутренних узлов произвольного расширенного бинарного дерева с тем же множеством весов {wi,..., Wm}, которые перечислены в таком произвольном порядке, что каждый некорневой внутренний узел располагается перед его родителем.

(a) Докажите, что

* к

Sj < 2 *j для 1 < fc < тп.

j=l J=l

(b) Результат (a) эквивалентен выражению

m-I m-1

для каждой неубывающей вогнутой функции /, а именно - для каждой функции / с /(х) > О и /"(х) < 0. [См. Hardy, Littlewood, and Polya, Messenger of Math. 58 (1939), 145-152.] Используйте этот факт, чтобы показать, что минимальное значение в рекуррентном соотношении

F{n) = f(n) + min (F(fc) + F{n - fc)), F(l) = 0

l<A:<n

всегда достигается для fc = 2" при условии, что данная функция /(п) обладает свойствами Д/(гг) = /(п + 1) - /(п) > О и ДV(") = A/(n + 1) - Дfin) < 0.

*2.3.4.6. История и библиография. Как известно, деревья появились уже на третий день сотворения мира и на протяжении веков древовидные структуры (особенно - генеалогические деревья) очень широко применялись. Как математический объект понятие дерева было впервые формально определено, по-видимому, в работе Г. Р. Кирхгофа (G. R. KirchhofF) [Annalen der Physik und Chemie 72 (ШТ), 497-508, в английском переводе опубликовано в IRE Transactions СТ-5 (1958), 4 7]. Он

использовал свободные деревья для поиска набора фундаментальных циклов в электрической цепи с помощью законов, которые теперь носят его имя. Причем Кирхгоф делал это почти так же, как uifi в разделе 2.3.4.1. Приблизительно в то же время понятие "дерево" появилось в книге К. Г. К. фон Штаудта (К. G. Chr. von Staudt) [Geometrie der Lage (pp. 20-21)]. Термин "дерево" и многие результаты, которые, в основном, имеют отношение к задаче перечисления деревьев, появились десять лет спустя в ряде работ Артура Кэли (Arthur Cayley) [см. Collected Mathematical Papers of A. Cayley 3 (1857), 242-246; 4 (1859), 112-115; 9 (1874), 202-204; 9 (1875), 427-460; 10 (1877), 598-600; 11 (1881), 365-367; 13 (1889), 26-28]. Кэли не знал о работах Кирхгофа и фон Штаудта и свои исследования начал, изучая структуру алгебраических формул. Позднее Кэли продолжил их в основном для изучения задач изомерии в химии. Древовидные структуры также независимо изучались К. В. Борхардтом (С. W. Borchardt) [Crelle 57 (1860), 111-121], И. Б. Листингом ( J. В. Listing) [Gottinger Abhandlungen, Math. Classe, 10 (1862), 137-139] и М. Э. К. Жорданом (М. Е. С. Jordan) [Crelle 70 (1869), 185-190].

"Лемма о бесконечном дереве" впервые была сформулирована Д. Кенигом (Denes Konig) [Fundamenta Math. 8 (1926), 114-134]; особое место он уделил ей в главе 6 своей классической книги Theorie der endlichen und unendlichen Graphen (Leipzig, 1936). Аналогичный результат, так называемая "теорема о веере", чуть раньше был опубликован в работе Л. Э. Я. Брауэра (L. Е. J. Brouwer) [Verhan-delingen Akad. Amsterdam 12 (1919), 7], но автору пришлось использовать гораздо более "сильные" предпшюжения. Работа Брауэра обсуждается в книге А. Хейтинга (А. Heyting) Intuitionism (1956), в разделе 3.4.

Формула (3) из раздела 2.3.4.4 для перечисления непомеченных ориентированных деревьев была предложена Кэли в его первой статье о деревьях. Во второй работе Кэли перечисгшл непомеченные упорядоченные деревья. Эквивалентная задача в геометрии (см. упр. 1) была поставлена и решена Й. А. фон Зегнером (J. von Segner) и Л. Эйлером (L. Euler) еще за сто лет до этого [Novi Commentarii Academise Scientiarum Petropolitanee 7 (1758-1759), 13-15, 203-210]. К тому же ей были посвящены семь статей Г. Ламэ (G. Lame), Э. Ш. Каталана (Е. С. Catalan), Б. О. Родригеса (В. О. Rodrigues) и Ж. Ф. М. Бине (J. Р. М. Binet) в Journal de mathematiques 3, 4 (1838, 1839). Дополнительные ссылки по этой теме можно найти в ответе к упр. 2.2.1-4. Соответствующие числа получили общепринятое название "числа Каталана" (Catalan numbers). Монголо-китайский математик Ан-Ту Минг (An-Tu Ming) рассматривал числа Каталана еще до 1750 года в исследованиях бесконечных рядов, но не связывал их с деревьями или другими комбинаторными объектами [см. J. Luo, Acta Scientiarum Naturalium Universitatis Intramongolicse 19 (1988), 239-245; Combinatorics and Graph Theory (World Scientific Publishing, 1993), 68-70]. Числа Каталана возникают при изучении множества самых разнообразных задач. В великолепной книге Ричарда Стэнли (Richard Stanley) содержится около 60 примеров их применения [Enumerative Combinatorics 2 (Cambridge Univ. Press, 1999), Chapter 6]. Вероятно, наиболее удивительное из всех применений чисел Каталана связано с упорядочениями чисел, которые Г. С. М. Коксетер (Н. S. М. Coxeter) из-за их симметрии назвал "узоры бордюра" (frieze patterns) (см. упр. 4).

Формула п"~ для числа помеченных свободных деревьев была получена Сильвестром (J. J. Sylvester) [Quart. J. Pure and Applied Math. 1 (1857), 55-56] как побоч-