AOP_Tom1 (1021736), страница 169
Текст из файла (страница 169)
4. Такое же доказательство можно использовать для многих других типов оптимальных деревьев, включая дерево нз упр. 10. 17. (а) То же, что и в упр. 14. (Ъ) Функцию /(и) можно расширить до вогнутой функции /(х), а потому указанное неравенство справедливо. Тогда Е(т) является минимумом суммы ~,, /(эз ), где эз — веса внутренних узлов расширенного бинарного дерева с весами 1, 1,..., 1. Алгоритм Хаффмэна, который позволяет в данном случае построить полное бинарное дерево с т — 1 внутренними узлами, приводит к построению оптимального дерева. Выбор значения ?с = 2' сС"С~В определяет бинарное дерево с теми же весами внутренних рсс сз узлов, поэтому для него рекуррентное соотношение достигает минимального значения для всех и.
[Я/АМ Х Арр!. МасИ. 31 (1976), 368-378.] Значение г (и) можно оценить эа 0(1об и) шагов (см. упр. 5.2.3-20 и 5.2.3 — 21). Если функция /(и) выпуклая, а не вогнутая (и потому й~/(и) > 0), то решение для этой рекуррентной формулы будет получено для 1 = [и/2]. РАЗДЕЛ 2.3.4.6 1. Выберем одну сторону многоугольника и назовем ее базой. Для данной триангуляции (т. е. рассечения многоугольника на треугольники) пусть треугольник базы соответствует корню бинарного дерева, а две другие его стороны определяют базы левого и правого падмногоугольников, которые таким же образам соответствуют левому и правому поддеревьям. Будем выполнять эти действия рекурсивно до тех пор, пока не достигнем двусторонних многоугольников, которые соответствуют пустым бинарным деревьям. Сформулировав соответствие иначе, пометим небазовые ребра триангулированного многоугольника целыми числами О, ..., и; когда две смежные стороны треугольника будут помечены по часовой стрелке символами и и б, пометим третью сторону как (пД).
Тогда метка базы характеризует бинарное дерево и триангуляцию. Например, многоугольник ь 5 (ПОП2)Нз(43))((07)(8ОПВ соответствует бинарному дереву 2 3.1 — (1). 2. (а) Возьмем базовую сторону, которая описана в упр 1, и присвоим ей И последователей, если зта сторона принадлежит (4 + 1)-угольнику в рассеченном диагоналями г-угольнике. Тогда другие И сторон являются базами поддеревьев. Таким образом определено соответствие между задачей Киркмана и всеми упорядоченными деревьями с г — 1 узлами-листьями, Л-~-1 узлами-не листьями и без узлов степени 1.
(Прн Л = г — 3 получим ту же ситуацию, что и в упр. 1 ) (Ъ) Существует ("„~,) ("ь~) таких последовательностей Абз...г(„еь неотрицательных целых чисел, что г — 1 чисел из И равны О, нн одно из них не равно 1, а сумма раина г+Л вЂ” 1. В точности одна циклическая перестановка из перестановок А с(з... и„4.ы с(з... с(г4.ьгЬ, ..., л 4.ьй .. с( 4.ь-~ удовлетворяет дополнительному свойству: 2 ~,(1 — ы,) > 0 для 1 < о < г+ Л.
[Киркман предложил доказательство своей гипотезы в РЛ71оз. Тгаоз. 147 (1857), 217 — 272, 822, а Кэли доказал ее без упоминания какой-либо связи с деревьями в Ргос. Еолдол МайЛ. Яос. 22 (1891), 237-262] 3. (а) Пусть вершины обозначены числами (1, 2,, и). Проведем связи 31.1ИК от 1 к у', если 1 и у являются последовательно расположенными злементами одной части и 1 < у; проведем связи ШИК от у к у + 1, если у 4- 1 является наименьшим значением в его части.
Тогда существует Й вЂ” 1 ненулевых связей ЬПИК, п — Л ненулевых связей Ы.ХИК и бинарное дерево с узлами 12... п при обходе в прямом порядке. Используя естественное соответствие из раздела 2.3.2, получим, что это правило определяет взаимно однозначное соответствие гаежду "разбиениями вершин п-угольника на Л непересекающихся частеи" и "лесами с и вершинами и и — Л + 1 листьями".
Поменяв местами связи ШИК н КЬ1ИК, можно также получить "леса с и вершинами и й листьями". (Ь) Лес с п вершинами и Л листьями соответствует последовательности вложенных скобок, которые содержат п левых скобок, и правых скобок и /с пар скобок "()". Такие последовательности можно перечислить следующим образом. Будем считать, что строка нулей и единиц является (пй п, к)-строкой, если в ней содержится т нулей, п единиц, а также Л пар "01'Ь Тогда 0010101001110 является (7, б,4)-строкой. Всего существует ( )(") таких (гп,п,й)-строк, поскольку любые нули и единицы могут образовывать пары 01 Пусть о'(и) — число нулей в и минус число единиц. Назовем строку и хорошей, егли 5(п) > О, когда и находится в префиксной части а (нначе говоря, если из о = пб следует, что Я(п) > 0); в противном случае назовем строку и плохой.
Тогда приведенный ниже вариант "принципа отражения" из упр. 2.2,1-4 задает взаимно однозначное соответствие между плохими (и, и, й)-строками и произвольными (п — 1, п+ 1, й)-строками. Всякую плохую (н,п, й)-строку а можно единственным образом представить в виде о = аОВ, где ал и Д- — хорошие строки. (Здесь пл — строка, полученная из строки о за счет ее обращения и дополнения всех ее битов.) Тогда и' = а1Д будет соответствовать (и — 1, и+ 1, й)-строке.
И наоборот, каждую (и — 1, п + 1, й)-строку можно единственным образом представить в виде а18, где а~ и ф — хорошие строки, а аО — плохая (и, и, й)-строка. Следовательно, количество лесов с и вершинами и й листьями равно („")(ь)— ("„-')("„") =М( — ЦЯ -й+Ц)( -й)!М(й-Ц!. За нечанил. Дж. Креверас (С, Кгевегаэ) в работе РЫсгесе МасЛ. 1 (1972), 333-350, перечислил непересекающиеся разбиения другим способом. Частичное упорядочение разбиений за счет более мелкого дробления приводит к интересному частичному упорядочению лесов, которое отличается от упорядочения, обсуждаемого в упр. 2.3.3 — 19 [см. У.
Рапрагб, Сай!егэ г)и Вигеаи Уп!ю с)е Несйегсйе ОрбгаВолпеПе 16 (197ц, С)гарсег 8; Рйсгеге Маей. 2 (1972), 279-288; Р. Ебе!шап, Рбзсгесе Маей. 31 (1980), 171-180, 40 (1982), 171 — 179]. Третий способ определения естественного решеточного упорядочения лесов предложен Р, П. Стэнли (В, Ясал!еу) в работе Р!Ьопасс! Япаггег!у 13 (1975), 215 — 232.
Представим лес в вице строки и из нулей и единиц, которые представляют упомянутые выше левые и правые скобки. В тахом случае а < и' тогда и только тогда, когда Я(пь) ( Ясгь) для всех й, где аь обозначает первые й бит и. Решетка Стэнли дасглрибртиена в отличие от двух других.
4. Пусть т = н-!-2. Используя результат упр. 1, следует установить соответствие между триангулированными т-угольниками и (т — Ц-строчными бордюрами. Сначала более подробно проанализируем предложенное выше соответствие, присваивая ребрам триангуляции ярлыки "верх-ниэ" вместо рассмотренных ярлыков "низ-вверх" так, как описывается ниже. Присвоим пустой ярлык е базе, а затем рекурсивно присвоим ярлыки аб и аН противоположным ребрам треугольника, база которого помечена ярлыком а. Например, так будет выглядеть предыдущая схема при использовании новых обозначений. ФФ 050 в Если базовое ребро в этом примере имеет ярлык 10, а другие ребра, как и прежде, имеют ярлыки от 0 до 9, можно записать О = 10БЪЪ, 1 = 10В! Н, 2 = 10БН, 3 = 10Нуб и т.
д. В качестве базы может быть выбрано любое другое ребро; таким образом, если выбрано ребро О, получим 1 = ОЪ, 2 = ОНЬ, 3 = ОНН7.1Ъ и т. д. Нетрудно проверить, что, если и = ап, получим а = иа, где а получено при чтении строки а справа налево и замене г 7 на Н, Например, 10 = ОННН = 17НН = 2ЬН = ЗНН/ и т. д. Если и, е и 1е — ребра многоугольника с ш = иаь7 и ш = ефН7, то получим и = ебба и е = иаНф Для данной триангуляции многоугольника, стороны которого пронумерованы числами О, 1, ..., т — 1, определим (и, е) для любой пары и и е следующим образом. Пусть и = еа, а а представим в виде матрицы размера 2 х 2, предполагая, что Ь = ( э ' ) и Н = ( ', ) . Тогда (и, е) — это элемент в правом верхнем углу а.
Обратите внимание на то, что матрица а это транспонированная матрица а, так как Н = Ъ~, Следовательно, получим (е, и) = (и, е). Также необходиыо отметить, что (и, е) = 1 тогда и только тогда, когда и и е объединены ребром триангуляции, где и обозначает вершину между ребрами и и и — 1. Пусть (и, и) = 0 для всех сторон многоугольника и. Можно доказать, что из е = иа следует а = ' ( ' ) длявсехи~е, () ((и+1,е) (и+1,е.(-1)) (и,е') (и,е') 1 / (и,е') (и,е +1) (и + 1, е') (и + 1, ее) ) ( (и + 1, е" ) (и + 1, е" + 1) ) а'=( ' е) - а"=( ' а (*) выполняется и для расширенного многоугольника.
Узор бордюра, который соответствует данной триангуляции, теперь определяется периодической последовательностью (О, 1) (1, 2) (2, 3) (О, 2) (1, 3) (2, 4) (т-1,2) (О,З) (1,4) (т-1,3) (0,4) (1,5) (т-1,0) (0,1) (1,2) (т — 1, 1) (О, 2) (1, 3) (тп — 2,1) (т — 1,2) (0,3) (т — 2,2) (т — 1,3) (0,4) и т. д, пока не будут определены т — 1 строк; последняя строка начинается с ((т/2) + 1, (т/21) для т > 3. С помощью условия (ь) можно доказать, что этот узор является бордюром, т.
е что (и, е)(и + 1, е + 1) — (и, е + 1)(и + 1, е) = 1, ('") поскольку из без Ь = бес Н = 1 следует, что без а = 1. Для рассматриваемого здесь примера триангуляции получим следующее. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 2 1 5 1 3 1 4 3 1 2 4 2 1 5 1 3 1 4 2 1 7 7 1 4 4 2 2 3 11 2 1 7 7 1 4 4 2 2 3 1 3 12 3 3 3 7 1 5 8 7 1 3 12 3 3 3 7 1 5 8 3 2 5 5 8 2 5 3 2 13 5 3 2 5 5 8 2 5 3 2 13 5 3 2 13 5 3 2 5 5 8 2 5 3 2 13 5 3 2 5 5 8 3 7 1 5 8 7 1 3 12 3 3 3 7 1 5 8 7 1 3 12 3 4 2 2 3 11 2 1 7 7 1 4 4 2 2 3 11 2 1 7 7 1 о 1 3 1 4 3 1 2 4 2 1 5 1 3 1 4 3 1 2 4 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Отношение (и, е) = 1 определяет ребра триангуляции, поэтому разные триангуляции позволяют получить разные бордюры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
