AOP_Tom1 (1021736), страница 167
Текст из файла (страница 167)
Таким образом, а < 1 и согласно предельной теореме Абеля получям о = а ехр(а+-.4(а )+ с» -'А(аз) -> ). (Ь) А(»з), А(»з), ...— аналитические для !»( < з/а, а 1А(»~)Ч--'А(»з)+ равномерно сходится в меныпем круге. (с) Если дГ/Дш = а — 1 ф О, та из теоремы о неявной функции следует, чзо существует такая аналитическая функция /(») в окрестности (а, а/а), что Г(», /(»)) = О. Но из этого получается /(») = А(»)/», а это противоречит тому факту, что А(») имеет особую точку » = а.
(д) Это очевидна. (е) дР/дш = А(х) — 1 и ]А(г)] < А(п) = 1, поскольку все коэффициенты А(г) положительны. Следовательно, как и для (с), функция А(г) регулярна во всех таких точках. (1) Вблизи (а, 1/а) имеем тождество 0 = д(г — а) + (а/2)(ш — 1/а) + члены более высокого порядка, где ш = А(г)/г, поэтому и — аналитическая функция от ч/г — а согласно теореме о неявной функции. Следовательно, существует область ]г] < аг с разрезом [а, пг), в которой А(г) имеет указанный вцд. (Знак "минус" выбран потому, что знак "плюс" в конце концов приводит к отрицательным коэффициентам.) (6) Любая функция указанного вида имеет коэффициенты, асимптотически равные х-Зе ('~~).
Обратите внимание, что ( / ) =О(-'( / )). Более подробное описание этих приемов и асимптотические значения для количества сво- бодных деревьев можно найти в работе В.. Оссег, Апп. Маей. (2) 49 (1948), 583 — 599. 5. Е (сг+зг 1) (с" +3" 1) 1 м+ггг+- = Следовательно, получим 2С(г) +1 — г = (1 — г) "(1 — х~) '(1 — х~) '... = ехр(С(г) + -С(гг)-~- ). 2 Поэтому С(з) = г+г~+2г~+бг~ 412гг+ЗЗге+90гг 1 261ге+76бг~+ .. для и ) 1 качичество последовательно-параллельных сетей с и ребрами равно 2с„[см. Р. А.
МасМаЬап, Ргос. 5опг)оп Мас)ь дос. 22 (1891), 330 — 339]. 6. гС(г) = 2С(г) — 2 — гС(гг); С(г) = 1+ г+ гг + 2гг + Зг~ 4 бгг + Пге + 23гг + 46гг Ч- 98гэ -Г .. Функция Р(г) = 1 — гС(х) удовлетворяет более простому соотношению Р(г~) = 2г+ Р(г)~. [3. Н, М. ггеЫсгЬпгп, Аппа)э о/Масй. 24 (1922), 121-140] 7. д„= са" п ~г~(1 4- О(1/и)), где с 0.7916031835775, а 2.483253536173. 9. При наличии двух центроидов, рассмотрев путь от одного центроида к другому, получим, что между ними не должно быть промежуточных вершин, поэтому два центроида должны быть смежными. Так как дерево не может содержать три взаимно смежных центроила, то их может быть не более двух. 10.
Если Х и У вЂ” смежные вершины, пусть з(Х,У) — количество вершин в У-поддереве узлаХ Тогда з(Х, У)+з(У,Х) = п. Согласно приведенным вэтом разделе аргументам, если У нвляется центроидом, вес Х равен з(Х, У). Следовательно, если Х и У вЂ” центроиды, то вес узла Х = весу узла У = и/2. На основе этого опредедения и приведенных в данном разделе аргументов можно показать, что если з(Х,У) > э(У,Х), то существует центроид в У-поддереве узла Х. Поэтому, если два свободных дерева с т вершинами соединены ребрам между узлами Х и У, получим свободное дерево, в котором з(Х, У) = т = з(У, Х) и в котором должны существовать два центроида (а именно, Х и У). [Прекрасным упражнением в программировании было бы создание программы для вычисления вссов э(Х, У) для всех смежных узлов Х и У за О(п) шагов, так как на основе этих данных можно быстро найти узлы-центроиды.
Эффективный алгоритм быстрого поиска расположения центроида был впервые предложен А. Дж. Голдманом; см. А. 3. Со!с)шап, Тгалэрогсапоп Зсь 5 (1971), 212-22Ц 11. аТ(з)' = Т(г) — 1, тогда а+ Т(з) ' = Т(а)' '. Из соотношения 1.2.9 — (21) следует, что Т(с) = 2 „А„(1, — С)в", поэтому количество 1-арных деревьев равно ( и )1+1и (и)(1 — 1)и+1 12. Рассмотрим ориентированный граф, который имеет одну лугу от Ъ( к \:~ для всех с ф у[ Матрица Аа из упр.
2.3,4.2-19 является комбннаторной матрицей размера (и — 1) х (и — 1) с равными и — 1 диагональными элементами и равными — 1 недиагональными элементами. Поэтому ее детерминант равен (и+ (и — 1)(-1))и" = и" т. е. количеству ориентированных деревьев с заданным корнем. (Здесь можно было бы также использовать результат упр.
2.3.4.2-20.) 13. 10 14. Да, справедливо, поскольку этот корень не станет листом, пока не будут удалены все ветви. 13. В каноническом представлении('м ъм..., ъ' м г(1г -с) является топологической сортировкой ориентированного дерева, которое рассматривается как ориентированный граф.
Но, вообще говоря, этот порядок может и не соответствовать порядку вывода в алгоритме 2.2.ЗТ. Для определения значений К~, '«с, ..., Ъ'„с алгоритм 2.2.3Т может быть изменен соответствующим образом, если операцию вставки в очередь на шаге Тб заменить процедурой, которая таким образом настраивает связи, что элементы гписка от начала к канну располагаются в порядке возрастания. Тогда эта очередь становится очередью по приоритету. (Однако очередь по приоритету общего типа не нужна для поиска канонического представления.
Потребуется талька пройти через вершины от 1 до и, выполняя поиск листьев и в то же время отсекая все пути от новых листьев, которые меньше указателя отсечения, см. следующее упражнение.) 16. 331. Установить С[Ц с- с- С[и3 с- О, затем установить СЩ$))3 с- С[[(Ъ~)3 + 1 для 1 < у < п. (Таким образом, вершина 1 является листом тогда и талька тогда, когда С [)с3 = 0.) Установить й с- 0 и у с- 1. 332. Увеличивать )с до тех пор, пока не будет выполнено условие С [/с] = О., а затем установить 1 с- й. [13. Установить РАЕЕЕТ[13 с — ДЪ~), 1 с- [($~), СИ с — СИ вЂ” 1 и 3 с- у + 1. 334.
Если у = и, то установить РайЕЕТ И с- 0 и прекратить выполнение алгоритма. [33. Если СИ = 0 и 1 < й, перейти к шагу [)3; в противном случае вернуться к .«[)г. 1 17. Должен существовать в точности один цикл ям кэ, ..., хь, где 7(к~) = х~.н и 7(яь) = хь Перечислим все такие ) с циклом длиной !г, что итерации каждого к в конце концов будут включаться в этот цикл.
Определим каноническое представление 1 Я ), 1(1г),, У(Р -ь) так же, как в данном разделе. У(К ь) находится в цикле, поэтому продолжим создание "канонического представления', запи- сываЯ остальнУю часть цикла Щ(хм-ь)), 7(7(7(гм-ь))) 9 10 и т. д Например, функция с та = 13 для показанного здесь графа приводит к такому представлению: 3, 1, 8, 8, 1, 12, И 1З 7 В 12, 2, 3, 4, 5, 1. Получим последовательность пг — 1 чисел, в которой последние Ь чисел будут различными. И наоборот, начиная с такой последовательности, можно выполнить обратное построение (при условии, что известно к). Сле- 1 12 довательно, существует в точности тйт таких функций, содержащих й-цикл.
(Для знакомства с другими аналоя гичными результатами обратитесь к упр. 3.1-14. Формулу гп 'О(т) впервые получил Л. Кац; он привел ее в работе К Каса, Аппа!э оУ Маей. Бгайэеюсэ 28 (1955), 512-517.) 18. Для реконструкции дерева на основе последовательности эм эг, ..., э„-~ начнем с э~ в качестве карня и последовательно будем присоединять дуги, ведущие в эп эг, .... Если вершина эь ранее встречалась, то оставим начальную вершину дуги, ведущей к эь без имени, в противном случае присвоим этой вершине имя эы После размещения п — 1 дуг присвоим имена 3 всем безымяннымн вершинам с помощью цифр, которые еще не встречались, в порядке возрастания по мере их появления. Например, на основе представления 3, 1, 4, 1, 5, 9, 2, б, 5 можно построить дерево, показанное справа. Между 4 этим методом и методом, описанным в данном разделе, не существует никакой простой связи.
О других представлениях речь идет в Е. Н. Нег!!!е, Ргос. СатбгЫВе РЫ!. Яоп 49 (1953), 381 — 385. 19. Каноническое представление имеет точно п — Ь различных величин, поэтому перечислим последовательности и -1 чисел, которые обладают данным свойством. Таким образом, ответ — и" — ( -а) 20. Рассмотрим каноническое представление таких деревьев. Тогда возникает вопрос: сколько членов разложения (я~ 4 + к„)" ' имеют ко нулевых степеней, !и степеней 1 и т, д, Понятно, что каждое такое число равно коэффициенту такого члена, умноженного на количество таких членов, а именно; (и — 1)! и! х (О!)ье(1!)ьч ... (и!)ь" !го! )гг!... к ! 21. Для четного количества вершин 2тп таких деревьев не существует, а для нечетного количества вершин и = 2ш+ 1 ответ можно получить на основе упр.
20 с йо = т + 1, кэ = гп, а именно — ( ~')(2т)!/2 22. Точно п" ~; действительно, если Х вЂ” некоторая вершина, то существует взаимно однозначное соответствие между свободными деревьями и ориентированными деревьями с корнем Л. 23. Каждое непомеченное упорядоченное дерево можно пометить и! способами, и все такие помеченные упорядоченные деревья будут различными, Поэтому их общее количество равно и!6„1 = (2и — 2)!/(и — 1)!.
24. Деревьев с фиксированнмм одним корнем столько же, сколько деревьев с другим корнем, поэтому ответ будет равен ответу из упр. 23, умноженному на 1/и. Например, в данном случае ответ — 30. 26. г(и, д) = (и — д)ил 1 для О < д < и. (Особый случай — з = 1 для уравнения (24).) 26. (Ь = 7) дьСнннй тый Красный 27. Пусть дана такая функция д с областью определения (1,2, ,г) и областью значений (1,2,...,9), что добавление дуг от к„.
к [7д1ю не приводит к появлению ориентированных циклов. Построим последовательность ам ..., а,. Назовем вершину 1'ь "свободной", если не существует ориентированных путей от Ъз к Уь для любых д ~ Й. Поскольку не существует ориентированных циклов, должна существовать ло крайней мере одна свободная вершина. Пусть 61 — наименьшее целое число, для которого вершина Уы является свободной.
Предположив, что выбраны числа 6м ..., Ьи допустим, что Ьь,1— наименьшее целое число, отличное от Ьм, 6и для которых Уи„, является свободной вершиной в графе, полученном путем удаления дуг от ЪЫ к (7жьь1 для 1 < й < 1 Это правило определяет перестановку 616е...6, целых чисел (1,2,...,г). Пусть аь = д(Ьь) для 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}
