деревом в контрпримере последовательности. Если выбраны Ti, 7}, пусть Tj + i - такое дерево с минимально возможным количеством узлов, что Ti, ..., Tj, Tj+i является началом контрпримера последовательности. Этот процесс определяет контрпример последовательности (Тп). Ни одно из деревьев Т не является только корнем. Рассмотрим теперь эту последовательность более внимательно.

(a) Предположим, что имеется последовательность Гщ, Тп, контрпримером которой является l{Tni), /(Tnj), .... Это невозможно, ибо последовательность Ti, ..., Гщ-г, l{Tni), 1{Тп2), была бы контрпримером последовательности, что противоречит определению Тщ .

(b) Согласно (а) существует только конечное количество j, для которых l{Tj) нельзя вложить в l{Tk) для любого к > j. Следовательно, для ni, большего, чем такое j, можно получить подпоследовательность, для которой /(Гщ) С /(Tnj) С 1{Тпз) Q

(c) Теперь согласно результату упр. 2.3.2-22 г{Тп) нельзя вставить в г(Тп) для любого к > j, так как в противном случае Tnj С Тп- Значит, Ti, .. ., Тщ-!, r(Tni), (Tnj), ... - контрпример последовательности. Но это противоречит определению Тщ

Замечания. Крускал в своей работе [IVans. Amer. Math. Soc. 95 (1960), 210-225] на самом деле доказал более "сильный" результат на основе более "слабого" понятия вставки. Его теорема не следует непосредственно из леммы о бесконечном дереве, хотя оба результата, в общем, подобны. Действительно, Кениг доказал особый случай теоремы Крускала о том, что не существует бесконечной последовательности парных несравнимых тг-кортежей неотрицательных целых чисел, где под сравнимостью подразумевается, что все компоненты одного кортежа меньше соответствующих компонентов другого кортежа или равны им [Matematikai es Fizikai Lapok 39 (1932), 27-29]. Дальнейшее развитие этой интересной темы можно найти в работе J. Combinatorial Theory А13 (1972), 297-305, а применение результатов для изучения вопроса о том, закончится ли алгоритм, - в работе Н. Дершовица [N. Dershowitz, Inf. Proc. Letters 9 (1979), 212-215].

РАЗДЕЛ 2.3.4.4

fc>l k,t>l t>l

2. Дифференцируя и приравнивая коэффициенты z", получим тождество

nUn+i = Е ydadUn+i-k,

к>1 d\k

а затем изменим порядок суммирования.

4. (а) A{z) сходится по крайней мере для \z\ < , так как а„ меньше числа упорядоченных деревьев Ьп-ь Поскольку А(1)-бесконечно и все коэффициенты положительны, существует такое положительное число а < 1, что A(z) сходится для \z\ < q, и существует особая точка z = а. Пусть ф{z) = A{z)jz\ так как (z) > е ясно, что из (z) = т следзет z < Inm/m, поэтому функция ф{z) ограничена и существует предел 1]тг->а-о ф{г). Таким образом, q < 1 и согласно предельной теореме Абеля получим а = q-exp(a-f- A(q)--iA(a«)+ ...).

(b) A(z), A(z), ... - аналитические для z < /a, a A(z)-b 5 A(z)-I----равномерно

сходится в меньшем круге.

(c) Если dF/dw = а - 1 / О, то из теоремы о неявной функции следует, что существует такая аналитическая функция /(z) в окрестности {а, а/а), что F(z,f{z)) = 0. Но из этого получается /(z) = A{z)/z, а это противоречит тому факту, что A(z) имеет особую точку Z = q.

(d) Это очевидно.

(e) dFjdw = A{z) - 1 и \A{z)\ < A{a) = 1, поскольку все коэффициенты A{z) положительны. Следовательно, как и для (с), функция A{z) регулярна во всех таких точках.

(f) Вблизи (q, 1/q) имеем тождество о = p{z - а) + {a/2){w - -ь члены более высокого порядка, где w = A{z)/z, поэтому w - аналитическая функция от \/z - а согласно теореме о неявной функции. Следовательно, существует область \z\ < Qi с разрезом [q, qi], в которой A{z) имеет указанный вид. (Знак "минус" выбран потому, что знак "плюс" в конце концов приводит к отрицательным коэффициентам.)

(g) Любая функция указанного вида имеет коэффициенты, асимптотически равные (п)- Обратите внимание, что

Более подробное описание этих приемов и асимптотические значения для количества свободных деревьев можно найти в работе R. Otter, Ann. Math. (2) 49 (1948), 583-599.

< jl J "Л jn

Cn, n>l.

Следовательно, получим

2C{z) + 1 - 2 = (1 - z)-" (1 - zYl - z)-"... = ехр(С(г) + C{z) + •••)•

Поэтому C{z) = z + z +2z + bz -b 12z -h33z -b90z -b261z* -b766z® -b • • • • Для n > 1 количество последовательно-параллельных сетей с п ребрами равно 2сп [см. Р. А. MacMahon, Proc. London Math. Soc. 22 (1891), 330-339].

6. zG{zf = 2G{z) - 2 - zG{z); G{z) = \ + z + z + 2z + iz + Gz -b Пг -Ь 23z + 46z* 4- 98z® + . Функция F{z) = 1 - zG{z) удовлетворяет более простому соотношению F(z2) = 2z + F{zf. [J. H. M. Wedderburn, Anmls of Math. 24 (1922), 121-140.]

7. gn = ca7i-/2(i + 0{l/n)), где с и 0.7916031835775, a и 2.483253536173. 8.

9. При наличии двух центроидов, рассмотрев путь от одного центроида к другому, получим, что между ними не должно быть промежуточных вершин, поэтому два центроида должны быть смежными. Так как дерево не может содержать три взаимно смежных центроида, то их может быть не более двух.

10. Если X и У - смежные вершины, пусть s{X,Y) - количество вершин в У-поддереве узла А. Тогда s{X, У) --5(У, А) = п. Согласно приведенным в этом разделе аргументам, если У является центроидом, вес X равен s{X,Y). Следовательно, если X и У - центроиды, то вес узла X = весу узла У = п/2.

На основе этого определения и приведенных в данном разделе аргументов можно показать, что если s{X,Y) > s{Y,X), то существует центроид в У-поддереве узла X. Поэтому, если два свободных дерева с пг вершинами соединены ребром между узлами А и У, по.11учим свободное дерево, в котором s{X,Y) = т - s{Y,X) и в котором должны существовать два центроида (а именно. X и У).

[Прекрасным упражнением в программировании было бы создание программы для вычисления весов s{X, У) для всех смежных узлов АГ и У за 0{п) шагов, так как на основе этих данных можно быстро найти узлы-центроиды. Эффективный алгоритм быстрого поиска расположения центроида был впервые предложен А. Дж. Голдманом; см. А. J. Goldman, Ti-ansportation Sci. 5 (1971), 212-221.]

n + tn\ 1 \ n J l + tn~

11. zT{zy = T{z) - 1, тогда z + T{z)- = r(z)~. Из соотношения 1.2.9-(21) следует, что T{z) = J2„ An(l, -t)z", поэтому количество t-арных деревьев равно

/tn\ 1

тг j (t - 1)71 + 1

12. Рассмотрим ориентировалный граф, который имеет одну дугу от V, к для всех i ф j. Матрица Ло из упр. 2.3.4.2-19 является комбинаторной матрицей размера (тг - 1) х (тг - 1) с равными Т1 - 1 диагональными элементами и равными -1 недиагональными элементами. Поэтому ее детерминант равен

т. е. количеству ориентированных деревьев с заданным корнем. (Здесь можно было бы также использовать результат упр. 2.3.4.2-20.)

14. Да, справедливо, поскольку этот корень не станет листом, пока не будут удалены все ветви,

15. В каноническом представлении Vi, v2, . .., Vn-i, /(Vn-i) является топологической сортировкой ориентированного дерева, которое рассматривается как ориентированный граф. Но, вообще говоря, этот порядок может и не соответствовать порядку вывода в алгоритме 2.2.3Т. Для определения значений Vi, V2, Vn-i алгоритм 2.2.3Т может быть изменен соответствующим образом, если операцию вставки в очередь на шаге Т6 заменить процедурой, которая таким образом настраивает связи, что элементы списка от начала к концу располагаются в порядке возрастания. Тогда эта очередь становится очередью по приоритету.

(Однако очередь по приоритету общего типа не нужна для поиска канонического представления. Потребуется только пройти через вершины от 1 до тг, выполняя поиск листьев и в то же время отсекая все пути от новых листьев, которые меньше указателя отсечения; см. следующее упражнение.)

16. D1. Установить С[1] Ч- • • • ч- СЕтг] ч- О, затем установить С[/(У)] +- С[/(У)] + 1

для 1 < j < тг. (Таким образом, вершина к является листом тогда и только тогда, когда С [И = 0.) Установить 4- О и j Ч- 1.

D2. Увеличивать fc до тех пор, пока не будет выполнено условие C[fc] = О, а затем установить / 4- fc.

D3. Установить PARENTEO 4- f{Vj), I 4- f{Vj), СШ 4- СШ - 1 и j 4- j + 1.

D4. Если j = тг, то установить PARENT [/] 4- О и прекратить выполнение алгоритма.

D5. Если С[/] = О и / < fc, перейти к шагу D3; в противном случае вернуться к шагу D2. I