нз. [Создание внутреннего узла.] Установить к к - 1, Ь[к] 4- х, R[k] 4- у, А[к] 4-А[х] + А[у].

Н4. [Готово?] Прекратить выполнение алгоритма, если к = 1.

Н5. [Поиск левого указателя.] (В этом месте j > к и очереди содержат всего к неиспользованных весов. Если А[у] < О, получим j = k, г = у + 1и A[i] > A[j].) Если А[г] < A\j], то установить х 4- г и г 4- г + 1; в противном случае установить X 4- j и j 4- j - 1. Вернуться к шагу Н2.

14. С небольшими изменениями здесь можно использовать то же доказательство, в котором А: = m - 1. [См. SIAM 3. Appl. Math. 21 (1971), 518.]

15. Вместо правила объединения весов wi -Ь W2 из (9) используем здесь такие функции объединения весов: (а) 1 -- max(u;i, тог) и (Ь) xwi -Ь xw2 соответственно. Случай (а) исследован в работе М. С. Golumbic, ШЕЕ Trans. С-25 (1976), 1164-1167, а стучай (Ъ) - в работе Т. С. Ни, D. Kleitman, and J. К. Tamaki, SIAM J. Appl. Math. 37 (1979), 246-256. Задача Хаффмэна - это предельный случай (b) при х -> 1, так как + f)"; = Yruj+eYh+Oie").

Д. Стот Паркер показал, что алгоритм, подобный алгоритму Хаффмэна, позволяет также найти минимальное значение клх -I- • • • -Ь Wmx", когда О < х < 1, если два максимальных веса объединяются на каждом этапе, как в случае (Ь). В частности, минимальное

значение ил2~ Н-----\-Wm2~" для u;i < • • • < равно wi/2-i-----i-nm-i/2""-l-Wm/2""

Продолжение обсуждения этой темы можно найти в работе D. Е. Knuth, J. Comb. Theory A32 (1982), 216-224.

16. Пусть Im+i = Irn+i = 0. Тогда

m mm km km

J=l J = l k=l j=l /b=l j = l j = l

поскольку > Ij + i, как и в упр. 4. Такое же доказательство можно использовать для многих других типов оптимальных деревьев, включая дерево из упр. 10.

17. (а) То же, что и в упр. 14. (Ь) Функцию /(тг) можно расширить до вогнутой функции /(х), а потому указанное неравенство справедливо. Тогда Е{т) является минимумом суммы EJLV f{j)j Д *J -веса внутренних узлов расширенного бинарного дерева с веса-ми 1, 1, ..., 1. Алгоритм Хаффмэна, который позволяет в данном случае построить полное бинарное дерево с т - 1 внутренними узлами, приводит к построению оптимального дерева. Выбор значения к = г*"! определяет бинарное дерево с теми же весами внутренних узлов, поэтому для него рекуррентное соотношение достигает минимального значения для всех тг. [SIAM J. Appl. Math. 31 (1976), 368-378.] Значение F{n) можно оценить за O(log тг) шагов (см. упр. 5.2.3-20 и 5.2.3-21). Если функция /(тг) выпуклая, а не вогнутая (и потому f{n) > 0), то решение для этой рекуррентной формулы будет получено для к =

РАЗДЕЛ 2.3.4.6

1. Выберем одну сторону многоугольника и назовем ее базой. Для данной триангуляции (т. е. рассечения многоугольника на треугольники) пусть треугольник базы соответствует корню бинарного дерева, а две другие его стороны определяют базы левого и правого подмногоугольников, которые таким же образом соответствуют левому и правому поддеревьям. Будем выполнять эти действия рекурсивно до тех пор, пока не достигнем двусторонних многоугольников, которые соответствуют пустым бинарным деревьям.

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

помечены по часовой стрелке символами а и /3, пометим третью сторону как (aff). Тогда метка базы характеризует бинарное дерево и триангуляцию. Например, многоугольник

(((01)2)((3(45))((67)(89))))

соответствует бинарному дереву 2 3.1-(1).

2. (а) Возьмем базовую сторону, которая описана в упр 1, и присвоим ей d последователей, если эта сторона принадлежит {d + 1)-угольнику в рассеченном диагоналями г-угольнике. Тогда другие d сторон являются базами поддеревьев. Таким образом определено соответствие между задачей Киркмана и всеми упорядоченными деревьями с г - 1 узлами-листьями, к+1 узлами-не листьями и без узлов степени 1. (При к = г-3 получим ту же ситуацию, что и в упр. 1 )

(Ь) Существует (iJC) таких последовательностей didi.-.dr+k неотрицательных целых чисел, что г - 1 чисел из d равны О, ни одно из них не равно 1, а сумма равна г+к-1. В точности одна циклическая перестановка из перестановок didi .. dr+k, di ... dr+kdi, ..., dr+kdi . .d-r+k-i удовлетворяет дополнительному свойству: X]j=i(l ~ dj) > 0 для 1 < g < r + k.

[Киркман предложил доказательство своей гипотезы в Pbilos. Trans. 147 (1857), 217-272, §22, а Кэли доказал ее без упоминания какой-либо связи с деревьями в Proc. London Math. Soc. 22 (1891), 237-262 ]

3. (a) Пусть вершины обозначены числами {1, 2, .., п}. Проведем связи RLINK от г к j, если г и j являются последовательно расположенными элементами одной части и г < j; проведем связи LLINK от j к j -Ь 1, если j + 1 является наименьшим значением в его части. Тогда существует А: - 1 ненулевых связей LLINK, п - к ненулевых связей RLINK и бинарное дерево с узлами 12 ... п при обходе в прямом порядке. Используя естественное соответствие из раздела 2.3.2, получим, что это правило определяет взаимно однозначное соответствие между "разбиениями вершин п-угольника на к непересекающихся частей" и "лесами с п вершинами и п - А: -Ь 1 листьями". Поменяв местами связи LLINK и RLINK, можно также получить "леса с п вершинами и А: листьями".

(Ь) Лес с п вершинами и А: листьями соответствует последовательности вложенных скобок, которые содержат п левых скобок, п правых скобок и А: пар скобок "()". Такие последовательности можно перечислить следующим образом.

Будем считать, что строка нулей и единиц является (т, п, А:)-строкой, если в ней содержится т нулей, п единиц, а также А: пар "01". Тогда 0010101001110 является (7, 6,4)-стро-кой. Всего существует С) () таких (т, п, А:)-строк, поскольку любые нули и единицы могут образовывать пары 01

Пусть S{a) - число нулей в q минус число единиц. Назовем строку а хорошей, если S(q) > О, когда q находится в префиксной части а (иначе говоря, если из (т = ар следует.

что S{a) > 0); в противном случае назовем строку <т плохой. Тогда приведенный ниже вариант "принципа отражения" из упр. 2.2.1-4 задает взаимно однозначное соответствие между плохими (п, п, А;)-строками и произвольными (п - 1, п + 1, А;)-строками.

Всякую плохую (п, п, А;)-строку <т можно единственным образом представить в виде ет = аО/З, где 5 и /3 - хорошие строки. (Здесь 5 - строка, полученная из строки q за счет ее обращения и дополнения всех ее битов.) Тогда <т = al/3 будет соответствовать (п - 1, п + 1, А;)-строке. И наоборот, каждую (п - 1,п + 1,А;)-строку можно единственным образом представить в виде al/3, где 5 и /3 - хорошие строки, а qO - плохая (п, п, А;)-строка.

Следовательно, количество лесов с п вершинами и к листьями равно () () - ("fc) ("f) =п\{п- 1)!/(п - + 1)! (п - fc)! fc! (fc - 1)!.

Замечания. Дж. Креверас (G. Kreweras) в работе Discrete Math. 1 (1972), 333-350, перечислил непересекающиеся разбиения другим способом. Частичное упорядочение разбиений за счет более мелкого дробления приводит к интересному частичному упорядочению лесов, которое отличается от упорядочения, обсуждаемого в упр. 2.3.3-19 [см. Y. Poupard, Cahiers du Bureau Univ. de Recherche Operationnelle 16 (1971), Chapter 8; Discrete Math. 2 (1972), 279-288; P. Edelman, Discrete Math. 31 (1980), 171-180, 40 (1982), 171-179].

Третий способ определения естественного решеточного упорядочения лесов предложен Р. П. Стэнли (R. Stanley) в работе Fibonacci Quarterly 13 (1975), 215-232. Представим лес в виде строки <т из нулей и единиц, которые представляют упомянутые выше левые и правые скобки. В таком случае <т < <т тогда и только тогда, когда S(<tj.) < 5(<т) для всех fc, где (Тк обозначает первые fc бит <т. Решетка Стэнли дистрибутивна в отличие от двух других.

4. Пусть m = п-Ь 2. Используя результат упр. 1, следует установить соответствие между триангулированными т-угольниками и (то - 1)-строчными бордюрами. Сначала более подробно проанализируем предложенное выше соответствие, присваивая ребрам триангуляции ярлыки "верх-низ" вместо рассмотренных ярлыков "низ-вверх" так, как описывается ниже. Присвоим пустой ярлык е базе, а затем рекурсивно присвоим ярлыки аЬ и aR противоположным ребрам треугольника, база которого помечена ярлыком q. Например, так будет выглядеть предыдущая схема при использовании новых обозначений.

=-RLR- -

Если базовое ребро в этом примере имеет ярлык 10, а другие ребра, как и прежде, имеют ярлыки от О до 9, можно записать О = 10LLL, 1 = WLLR, 2 = 10LR, 3 = WRLL и т. д. В качестве базы может быть выбрано любое другое ребро; таким образом, если выбрано ребро О, получим 1 = OL, 2 = ORL, 3 = ORRLLL и т. д. Нетрудно проверить, что, если и = va, получим V = иа, где получено при чтении строки q справа налево и замене