AOP_Tom1 (1021736), страница 168
Текст из файла (страница 168)
Поскольку а, < р, имеется не более г — 1 несвободных вершин. Пусть 6~ — наименьшее целое, для которого вершина Уы является свободной. Предположив, что выбраны Ьм .,,, Ьи допустим, что Ььы — наименьшее целое, отличное от Ьм ..,, 6и для которых вершина Уь,„, является свободной по отношению к последовательности а~ем, а,. Данное правило определяет перестановку 616ю ..Ь, целых чисел (1,2,,г). Пусть д(Ьь) = аь для 1 < )с < г; зто определяет такую функцию, что добавление дуг от Уь к (7з1ю не приводит к появлению ориентированных циклов.
28. Пусть / — любая из и ' функций с областью определения (2,..., ш) и областью значений (1, 2,..., и). Рассмотрим ориентированный граф с вершинами (7м,, П„, Ум..., У и дугами от оь к УПЮ для 1 < Ь < иь Применим результат упр.
27 с р = 1, д = ги, г = и, чтобы показать, что существует ти" ' способов добавления дополнительных дуг от У к (7 для получения ориентированного дерева с корнем 17м Поскольку между рассматриваемым множеством свободных деревьев и множеством ориентированных деревьев и можно построить подпаследовательность 4... г('„= г(г м ..4г04гч.ы .. 4„, в которой и, з раз встречается ! для г Р г!и иг — 1 раз встречается !' для ! = г(г Тогда 2 (1 — з! ) равна г(г для Ь = и и эта сумма равна г)г — з для Ь = Е Для Ь < ! получим (1 — 4,) — ~ (1-Ы,) < ~ (1 — 4,) = г!г — з — 1. гйг« г<г<с гйгбг — г Отсюда следует, что для данного з и любой последовательности Иг...г!'„это построение можно обратить.
Значит, количество последовательностей с(г... Ы„для заданных значений 4г и з можно выразить с помощью полиномиального коэффициента (...,., и — 1 пе,,пз, 1,,п ) Тогда количество последовательностей 4г... Ы„, которые соответствуют деревьям, можно получить за счет суммирования всех допустимых значений йг и з: причем последняя сумма равна 1. Еще более простое доказательство этого результата предложено Дж. Н.
Рэйни (6. Х. Баасу) ]ем. ТгалзасНопз оГ гбе Атепсап МаСЬ. Бос!егу 94 (1960), 441 — 451]. Если бгг)г...б †произвольн последовательность, в которой и раз встречается у, то сушествует в точности одна циклическая перестановка 4г... д„Иг... И» и которая соответствует дереву, а именно: перестановка, в которой Ь вЂ” такое максимальное значение, что сумма 2,", (1 — г)г) Явлаетса минимальной. [По-видимомУ, этот РезУльтат длЯ бинаРных деРевьев впервые был получен Ч.
С С. Пирсом (С. Я. 8. Реггсе) в неопубликованной рукописи; см. его книгу №и" Е!етелгз ог МагЬетайсз 4 (ТЬе Набпе: Монгол, 197б), 303 — 304 Для барных деревьев доказательство предложено Дворецким и Моцкиным; см. Рнйе МагЬ. Х 14 (1947), 305 †3.] Ещг одно доказательство предложено Дж. М.
Бергманом (С,М. Вегрпап),в котором согласно методу индукции 4гбг.гг заменяется на (Иь + Ыьег — 1), если 4г ) О (А!яеЬга (уп!гегзайз 8 (1978), 129 — 130]. Описанные выше методы можно обобщить и показать, что количество упорядоченных и непомеченных лесов с г" деревьями и пг узлами степени у равно (и — 1)'1!по!пг! и !, если выполняется условие по = г+ пг + 2пз + 33. Рассмотрим количество деревьев с пг узлами, которые помечены номером 1, с пг узлами, которые помечены номером 2, и т.
д., таких, что каждый узел с меткой (номером) у имеет степень ег. Пусть зто число равно с(пм пг,... ) с фиксированными степенями ег, ег, ... Производящая функция С(ем ге,...) = 2 с(пг,иг,...)з~'. г~ ., удовлетворяет тождеству С = гггз" + + г,6 ", так как г,6'г перечисляет деревья с корнями, помеченными номером 50 Согласно результату предыдущего упражнения с(пипг,...) = (пг + пг + ° ° — 1)! если (1 — ег)пг +(1 — ег)пг+ = 1! пг! пгЕ .. 0 в остальных случаях. Вообще говоря, поскольку Сг! перечисляет все упорядоченные леса с такими ярлыками, для целых 7 > 0 получим / ч (пг + пг + — 1)! ! гз зг гг пП пг!...
!=О- О г-Нг-~г) г,. Эти формулы имеют смысл, когда г = со, и, по существу, они эквивалентны формуле обратного преобразования Лагранжа. РАЗДЕЛ 2.3.4.5 1. Всего существует (е) таких деревьев, поскольку узлы с номерами 3-12 можно присоединить в любом из 8 мест под узлами 4-2. 3. Согласно методу индукции по т данное условие является необходимым.
И наоборот, если 2 ~, 2 О = 1, нужно построить расширенное бинарное дерево с длинами пути !м..., ! . Если т = 1, имеем 1~ = О, и построение становится тривиальным. В противном случае можно предположить, что 1 упорядочены так, что 1~ = !э = . = !т > !ет~ > !деэ > > ! > О для некоторого е с 1 < о < тп.
Тогда 2ц ' = 2 , 2ц О ' = 12 + целое число. Следовательно е — четно. На основании метода индукции по ш можно доказать, что существует дерево с длинами пути 1~ — 1, !з, !4, ..., ! . В таком дереве заменим один из внешних узлов на уровне 1~ — 1 внутренним узлом, дети которого находятся на уровне 6 =Еь 4. Сначала построим дерево по методу Хаффмэна. Если ш, < шьем то !з > !зэы так как это дерево является оптимальным. Построение из ответа к упр.
3 теперь позволяет получить другое дерево с теми же длинами пути и весами в соответствующей последовательности. Например, дерево (11) принимает вид ), 166-169.! б. (а) б р — — ) Ьг,бм. Следовательно, хВ(ш,шх) = В(ш,з) — 1. ье!= -1 + + — г=е (Ъ) Возьмем частную производную по ш: 2хВ(ш, шз)(В (ш, шг) 4- яВг(ш, шз)) = В,(ш, з).
Значит, если Н(е) = В (1,г) = 2 „Ь„в", найдем Н(х) = 2зВ(з)(Н(з) + еВ'(з)). Из из- вестной формулы для В(з) Зи+ 1 12и1 следовательно, Ь„ = 4"— и+1 1и! Среднее значение равно Ь„/Ь„. (с) Асимптотически это выражение равно ичгяи и— Зи + 0( /й). [См. решения аналогичных задач в работах ЮоЬп Вюгг)аи, 1ВМ 1. Вез. алг( Веге!.
4 (1960), 473-478; А. Вену! апг! С. Бяеуегев, 1. Аизсгабап МагЬ. Яос. Т (1967), 497-507; ЛоЬп В(- отдав аль Ы. Л. А. 8!аале, Х Аиэ!га!!ап МагЬ. Яос. 10 (1969), 278-282; а также в упр. 2.3.1 — 11.] 6. и + э — 1 = Ггь 7. Е = (г — 1)1 + 1и, 8. Суммируя по частям, получим ~ т",, [!ой,((! — 1)Ь)] = ид — ~:Ь, где суммнр е справа выполняется по таким Ь, что 0 < Ь < и и (! — 1)Ь + 1 = Н для некоторого 1. Последнюю сумму можно представить в виде ~ э,(Н вЂ” 1)/(1 — 1). 9. Воспользуйтесь методом индукции по размеру дерева.
10. Добавив (если это необходимо) дополнительные нулевые веса, можно предположить, что гп шаг)(! — 1) = 1. Чтобы получить барное дерево с минимальной взвешенной длиной пути, на каждом этапе объединим наименьшие значения ! и заменим их суммой этих же значений. Доказательство в таком случае выполняется, как для бинарного дерева.
Искомое тернарпае дерево наказано справа. Ф. К, Хван (Р. К.Нюапй) заметил [ЯАМ 1. Арр!. Ма1Л. ЗТ (1979), 124 — 127], что аналогичная процедура справедлива для построения деревьев с минимальным взвешенным путем, имеющих произвольно заданное мультимножество степеней. Для этого следует объединить ! весов на каждом этапе, где ! является минимально возможным, 11. Десятичная система обозначений Дьюи является двоичным представлением номеров узлов. 12. Согласно результату упр.
9 средний размер поддерева с корнем в этом узле равен внутренней длине пути, деленной на и плюс 1. (Втот результат верен как для деревьев общего типа, так и для бинарных деревьев.) 13. [См. Л. чап Ьееивеп, Ргас. Згй 1п1егла1!опе! Со!!оФ Аиготага, Бапбиа8ез апг! Ргобгатт!л8 (Е61иЬигб!ь 1. и!гегяйу Ргсвз, 1976), 382-410.] Н1. [Инициализация.] Установить А[т — 1+ 4) г — ш, для 1 < ! < т.
Затем установить А[2т] е- со, т э- т, ! +- т + 1, ! е- т — 1, Ь +- т. (В данном алгоритме А[1] < . < А[2т — 1] — очередь неиспользованных внешних весов; А[у] » .. А[1]— очередь неиспользованных внутренних весов, которая пуста в случае, когда ! < й; я и у — текущие левый и правый указатели.) Н2. [Поиск правого указателя.] Если ! < Ь или А[!] < А[)], то установить у е- 1 и 1 е- ! + 1; в противном случае установить у э- / и ! г- ! — 1. Н3. [Создание внутреннего узла.] Установить )с с — й — 1, Х [5] с- х, В[5] с — у, А[5] еА[х] + А[у]. Н4. [Готово?] Прекратить выполнение алгоритма, если 1 = 1.
Н5. [Поиск левого указателя.) (В этом месте у > 1 и очереди содержат всего )с неиспользованных весов. Если А[у] < О, получим у = ?с, с = у+ 1 и А[1] > А[/].) Если А[с] < А[Я, то установить х с — с и 1 с — с + 1; в противном случае установить х+- 1 и у +- 1 — 1. Вернуться к шагу Н2. 5 14. С небольшими изменениями здесь можно использовать то же доказательство, в котором )с = т — 1.
[См, $1АМ Х Арр!. Масб. 21 (1971), 518.] 15. Вместо правила объединения весов сас + юэ из (9) используем здесь такие функции объединения весов: (а) 1 + шах(вышэ) и (Ъ) хвс + хслз соответственно. Случай (а) исследован в работе М. С. Со!ппсЬ|с, 1ЕЕЕ Т?апэ. С-25 (1976), 1164 — 1167, а случай (Ъ)— в работе Т. С. Нп, П. К!е)сшап, авб Х К. ТашаЫ, ЯАМ Х Арр!. Масб.
37 (1979), 246-256. Задача Хаффмзна — это предельный случай (Ь) при х -+ 1, так как 2 (1 Ч- е) 'ну ~аЬ+е~ шэ1, +0(с ). Д. Стот Паркер показал, что алгоритм, подобный алгоритму Хаффмэна, позволяет также найти минимальное значение сасхи + + са х', когда 0 < х < 1, если два максимальных веса объединяются на каждом этапе, как в случае (Ь). В частности, минимальное значениешс2 Ь+ +ш 2 ' дляшс « . са равно сас/2+ .+са ~/2 '+ю /2 Продолжение обсуждения этой темы можно найти в работе Г). Е. КппсЬ, Х Сошб. ТЬеогу А32 (1982), 216 — 224. 16. Пусть 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}
