ный результат вычисления некоторого детерминанта (упр. 2.3.4.2-28). Независимо от него Кэли предложил еще один способ вывода данной формулы в 1889 году [см. приведенную выше еылку]. В его весьма туманном обсуждении этого результата есть намек на связь между помеченными ориентированными деревьями и кортежами из (п - 1) чисел. Явное указание такой взаимосвязи было впервые опубликовано Хайнцем Прюфером (Heinz Priifer) [Arch. Math, und Phys. 27 (1918), 142-144] совершенно независимо от работы Кэли. С тех пор этой теме было посвящено огромное количество публикаций. Прекрасный обзор классических результатов можно найти в книге Дж. В. Муна (J. W. Moon) Counting Labelled Trees (Montreal: Canadian Math. Congress, 1970).

Очень важная статья о перечислении деревьев и многих других видов комбинаторных структур опубликована Д. Пойа (G. Polya) в Acta Math. 68 (1937), 145-253. Обсуждение задач перечисления для графов и прекрасная библиография ранних результатов по этой теме приводится в обзоре Фрэнка Харари (Franlc Harary) [Graph Theory and Theoretical Physics (London: Academic Press, 1967), 1-41].

Метод поиска минимального значения взвешенной длины пути за счет повторного объединения наименьших весов был открыт Д. Хаффмэном (D. Huffman) [Proc. IRE 40 (1952), 1098-1101] в связи с задачей создания кодов для сжатия сообщений. Аналогичная идея была независимо предложена Сетом Циммерманом (Seth Zimmerman) [АММ 66 (1959), 690-693].

Несколько других достойных внимания статей о теории древовидных структур упомянуты в разделах 2.3.4.1-2.3.4.5 в связи с обсуждаемы.ми в них частными вопросами.

УПРАЖНЕНИЯ

► 1. [21] Найдите простое взаимно однозначное соответствие между бинарными деревья.ми с п узлами и сечениями (п + 2)-стороннего выпуклого многоугольника на п треугольников при условии, что стороны многоугольника различны.

► 2. [М26] Т. П. Кнркман (Т. Р. Kirkiiiaii) предположил в 1857 году, что количество способов проведения к неперекрывающихся диагоналей в г-стороннем многоугольнике равно

a) Расширьте соотнощение из упр. 1, чтобы можно было получить эквивалентную задачу о перечислении деревьев.

b) Докажите предположение Киркмана с по.мощью методов, описанных в упр. 2.3.4.4-32.

► 3. [МЗО] Рассмотрите все способы такого разбиения вершин выпуклого п-угольника на к непустых частей, что ни одна из диагоналей межд> двумя вершинами одной части не пересекает диагональ .между двуА{я вершинами другой части.

a) Найдите взаи.мно однозначное соответствие между непересекающимися разбиениями и каким-нибудь интересным классом древовидных структур.

b) Сколько существует способов выполнения такого разбиения для заданных пик?

► 4. [МЗЗ] (Задача Конвэя (Conway) и Коксетера (Coxeter).) Узор бордюра-это бесконечный массив наподобие

1111111111111111111

3131412313141231314 ...

5222331522233152223 ...

3315222331522233152 ...

1412313141231314123 ... 1111111111111111111

в котором верхняя и нижняя строки полностью состоят из единиц, а каждый ромбик смежных значений а d удовлетворяет соотношению ad - be = 1. Найдите взаимно однозначное соответствие между п-узловыми бинарными деревьями и (п Ч- 1)-строчными узорами бордюра, которыесостоят из положительных целых чисел.

2.3.5. Списки и "сборка мусора"

Почти в самом начале раздела 2.3 Список неформально определялся как "конечная последовательность атомов или Списков, число которых может быть больше нуля или равно нулю".

Любой лес является Списком, например лес

b с d f 9 (1)

может рассматриваться как Список

{a:{b,c,d),e:if,g:{h)}), (2)

а схема Списка будет выглядеть следующим образом:

Читателю необходимо еще раз просмотреть предложенное ранее вводное описание Списков, в частности схемы (3)-(7), предложенные в самом начале раздела 2.3. Напомним, что в схеме (2) "а: (6, с, d)" означает, что (6, с, d) является Списком из трех атомов, который помечен атрибутом "а". Это обозначение совместимо с нашими общими представлениями о том, что в каждом узле дерева может, по.мимо структурных взаи.мосвязей, содержаться другая полезная информация. Однако, как и при обсуждении деревьев в разделе 2.3.3, вполне возможно, а иногда и очень желательно, использовать непомеченные Списки, чтобы вся информация содержалась в атомах.

Хотя любой лес может рассматриваться как Список, обратное утверждение неверно. Показанный ниже Список, вероятно, более типичен, чем (2) и (3), поскольку в нем показано, как могут нарушаться накладываемые на древовидную. cTpyKTj-py ограничения:

L={a:N,b,c:id:N),e:L), N = [f: {), д: (h: L,j: N)). (4)

Схематически эту структуру можно представить в таком виде:

*[L]

a*[N] Ь с* e[L]

/ \ I (5)

/* 9* d[N]

h[L] j[N]

[Ср. со схемой 2.3-(7). При этом форму данных схем не стоит воспринимать слишком серьезно.]

Как и следовало ожидать, структуры наподобие Список мохут быть отображены в памяти компьютера самыми разнообразными способами. Эти методы обычно являются вариациями на ту же основную тему, т. е. являются способами представления лесов деревьев общего типа на основе бинарных деревьев. Например, поле RLINK используется для указания следующего элемента Списка, а поле DLINK - для указания первого элемента подСписка. За счет естественного расширения представления в памяти, описанного в разделе 2.3.2, Список (5) можно отобразить так:

К сожалению, эта простая идея не совсем пригодна для наиболее распространенных приложений, в которых применяется обработка Списков. Предположим, например, что в Списке L = {А, а, {А, А)) содержатся три ссылки на Список А = (Ь, с, d). Одна из типичных операций при обработке Списков заключается в удалении крайнего слева элемента Списка А таким образом, чтобы Список А после этого имел вид (с, d). Но для представления данного Списка в виде (6) в Списке L потребуется внести три изменения, поскольку каждый указатель на Список А указывает на удаляемый элемент Ь.

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

Поэтому вместо схемы представления (6) обычно используется другая схема, в которой в начале каждого Списка располагается заголовок Списка {List head) (о нем уже упоминалось в разделе 2.2.4). Каждый Список содержит дополни