AOP_Tom1 (1021736), страница 116
Текст из файла (страница 116)
Э. Я. Браузра (1.. Е. 3. Вго~пчег) [1'егйап- сИ!пяеп Акаг!. Атэгегс!агп 12 (1919), 7], но автору пришлось использовать гораздо более "сильные" предположения. Работа Брауэра обсуждается в книге А. Хейтинга (А. Неубпй) 1пгшйоттип (1956), в разделе 3.4. Формула (3) из раздела 2.3.4.4 для перечисления непомеченных ориентированных деревьев была предложена Кэли в его первой статье о деревьях. Во второй работе Кэлп перечислил непомеченные упорядоченные деревья. Эквивалентная задача в геометрии (см. упр. 1) была поставлена и решена Й. А. фон Зегнером (3. гоп Бейпег) и Л.
Эйлером (Ь, Еп1ег) еще за сто лет до этого [г!ог! Сошшепгагй Асадеш!ю Бс!епг!агит Реггоро!!ганю 7 (17о8 — 1759), 13 — 15, 203 — 210]. К тому же ей были посвящены семь статей Г. Ламэ (С. 1.аше), Э. Ш. Каталана (Е. С. Сага!ац), Б. О. Родригеса (В. О. Нос!г!8пеэ) и Ж. Ф. М.
Бине (3. Р. М. В!пе1) в Уоигпа! де тагйетайдиеэ 3, 4 (1838, 1839). Дополнительные ссылки по этой теме можно найти в ответе к упр. 2.2.1 — 4. Соответствующие числа получили общепринятое название "числа Каталана" (Сага!ап ппшЬегэ). Монголо-китайский математик Ан-Ту Минг (Ап-Т'и М1п8) рассматривал числа Каталана еще до 1750 года в исследованиях бесконечных рядов, но но связывал их с деревьями или другими комбинаторными объектами [см. 3. 1 по, Ас1а Бс!епбагит Хасига!!пт (лииегэйаг!э 1пггатопйо!!сье 19 (1988), 239-245; СошЫпагог!сэ ии! Сгарй ТЬеогу (1тог!6 Бс!епббс РпЫ!эЫпй, 1993), 68-70]. Числа Каталана возникают при изучении множества самых разнообразных задач. В великолепной книге Ричарда Стэнли (Н!сЬагг! Бган!еу) содержится около 60 примеров их применения [Епшпегаг!ге СощЫпагог!сз 2 (СащЬгьййе Епй . Ргеээ, 1999), СЬаргег 6].
Вероятно, наиболее удивительное из всех применений чисел Каталана связано с упорядочениями чисел, которые Г. С. М. Коксетер (Н. 8. М. Сохегег) из-за их симметрии назвал "узоры бордюра" (ббехе рас1егпэ) (ель упр. 4). Формула и" э для числа помеченных свободных деревьев была получена Сильвестром (3. д. Бу!теэгег) [(гиага .1. Риге апг! Арр!!ес! Л!а!!ь 1 (1857), 55 56] как побоч- ный результат вычисления некоторого детерминанта (упр. 2.3.4.2 — 28). Независимо от него Кэли предложил еще один способ вывода данной формулы в 1889 году [слг. приведенную выше ссылку]. В его весьма туманном обсуждении этого результата есть намек на связь между помеченными орнентврованными деревьями и кортежами из (и — 1) чисел.
Явное указание такой взаимосвязи было впервые опубликовано Хайнцелг Прюфером (Не!пх Ргйгег) [АгсЛ. Ма!0. ипг! РЛуя. 27 (1918), 142-144] совершенно независилю от работы Кэпи. С тех пор этой теме было посвящено огромное количество публикаций. Прекрасный обзор классических результатов можно найти в книге Дж. В. Муна (3. ллг. Мооп) Соилбпб Лабебегг' Тгеея (Мопсгеа!: Сапаг!!ап Ма!Ь. Сопйтеяя, 1970). Очень важная статья о перечислении деревьев и многих других видов комбинаторных структур опубликована Д. Пойа (О. Рб!уа) в Асса МагЛ. 68 (1937), 145-253, Обсуждение задач перечисления для графов и прекрасная библиография ранних результатов по этой теме приводится в обзоре Фрэнка Харари (Ргап!г Нагагу) [СгарЛ ТЛеогу апгг' ТЛеогебса1 РЛуягся (Ьопг)оп: Асаг1еш!с Ргеяя, 1967), 1 — 41]. Метод поиска лгинимального значения взвешенной длинь! пути за счет повторного объединения наименьших весов был открыт Д.
Хаффмэном (Р. НиКшап) [Ргос, 1НН 40 (1952), 1098-110Ц в связи с задачей создания кодов для сжатия сообщений. Аналогичная идея была независимо предложена Сетом Циммерлганом (8есЬ Еипшегшап) [АММ 66 (1959), 690-693]. Несколько других достойных внимания статей о теории древовидных структур упомянуты в разделах 2.3.4.1-2.3.4.5 в связи с обсуждаемыми в них частными вопросами. УПРАЖНЕНИЯ 1. [2!] Найдите простое взаимно однозначное соответствие между бинарными деревьями с и узлами и сечениями (и+ 2)-стороннего выпуклого лгиогоугольиика иа и треугольников при условии, что стороны многоугольника различны.
2. [гийо] Т. П. Киркмаи (Т. Р. К!г!ггглагг) предположив в 1857 году, что количество способов проведения !г иеперекрывающихся диагоналей в г-стороннем многоугольнике равно („"++,) (' )/(г + !г). а) Расширьте соотношение из упр. 1, чтобы можно было получить эквивалентную задачу о перечислении деревьев. Ъ) Докажите предположение Киркмаиа с помощью методов, описанных в упр. 2.3.4.4-32. 3. [МУ0] Рассмотрите все способы такого разбиения вершин выпуклого и-угольника иа Й иепустых частей, что ии одна из диагоналей между двумя вершииалги одной части не пересекает диагональ между двулгя вершиналги другой части. а) Найдите взаимно однозначное соответствие между непересекающимися разбиениями и каким-нибудь интересным классом древовидных структур Ь) Сколько существует способов выполнения такого разбиения для заданных и и Лг 4. [Муз] (Задача Конвэя (Саплэау) и Коксетера (Сохелег).) Узор 6ордюра — это бесконечный лгассив наподобие 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 3 1 4 1 2 3 1 3 1 4 1 2 3 1 3 1 4 5 2 2 2 3 3 1 5 2 2 2 3 3 1 5 2 2 2 3 3 3 1 5 2 2 2 3 3 1 5 2 2 2 3 3 1 5 2 1 4 1 2 3 1 3 1 4 1 2 3 1 3 1 4 1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 в котором верхняя и нижняя строки полностью состоят из единиц, а каждый рольбик смежных значений, л удовлетворяет соотношению ль1 — Ьс = 1.
Найдите взаимно одь нозначное соответствие между и-узловыми бинарными деревьями и (и + 1)-строчными узорами бордюра, которые состоят из положительных целых чисел. 2.3.5. Списки и "сборка мусора" Почти в самом начале раздела 2.3 Список неформально определялся как "конечная последовательность атомов или Списков, число которых может быть больше нуля или равно нулю". Любой лес является Списком, например лес может рассматриваться как Список (а:(Ь,с,ь1),е:(У,уд(Ь))), а схема Списка будет выглядеть следующим образом: (2) (3) Ь = (л: М Ь т(сЬж) е: Ц ж = И:() уд(Ь:Ь у':Г~)) (4) Читателю необходимо еще раз просмотреть предложенное ранее вводное описание Списков, в частности схемы (3) — (7), предложенные в самом начале раздела 2.3.
Напомним, что в схеме (2) "а: (Ь, с, ь1)" означает, что (Ь, с, 0) является Списком из трех атомов, который помечен атрибутом "л". Это обозначение совместимо с нашими общими представлениями о том, что в каждом узле дерева может, помимо структурныхх взаимосвязей, содержаться другая полезная информация. Однако, как и при обсуждении деревьев в разделе 2.3.3, вполне возможно, а иногда и очень желательно, использовать непомеченные Списки, чтобы вся информация содержалась в атомах. Хотя любой лес может рассматриваться как Список, обратное утверждение неверно.
Показанный ниже Список, вероятно, более типичен, чем (2) и (3), поскольку в нем показано, как могут нарушаться накладываемые на древовидную. структуру ограничения: Схематически эту структуру можно представить в таком виде: "М д* И[И] /~ ЬЩ 7(Л] (5) (Ср. со схемой 2.3 — (7). При этом форму данных схем не стоит воспринимать слишком серьезно.] Как и следовало ожидать, структуры наподобие Список могут быть отображены в памяти компьютера самыми разнообразными способами.
Эти методы обычно являются вариациями иа ту же основную тему, т. е. являются способами представления лесов деревьев общего типа на основе бинарных деревьев. Например, поле йЫМК используется для указания следующего элемента Списка, а поле Р~.1МК вЂ” для указания первого элемента подСписка. За счет естественного расширения представления в памяти, описанного в разделе 2.3.2, Список (5) можно отобразить так: (6) К сожалению, эта простая идея не совсем пригодна для наиболее распространенных приложений, в которых применяется обработка Списков. Предположим, например, что в Списке Е = (А, а, (А, А)) содержатся три ссылки на Список А = (Ь, с, И). Одна из типичных операций при обработке Списков заключается в удалении крайнего слева элемента Списка А таким образом, чтобы Список А после этого имел вид (с, Н).
Но для представления данного Списка в виде (6) в Списке Ь потребуется внести гири изменения, поскольку каждый указатель на Список А указывает на удаляемый элемент Ь. Немного поразмыслив, читатель, несомненно, придет к выводу, что было бы крайне нежелательно изменять указатели на каждую ссылку на Список А только потому, что удаляется первый элемент Списка А.
(В этом примере можно попытаться схитрить и, предположив, что нет указателей иа элемент с, сначала скопировать весь элемент с в ячейку. прежде занятую элементом Ь, а затем удалить старый элемент с. Однако эта уловка ие поможет в ситуации, когда Список А утрачивает свой последний элемент и становится пустым.) Поэтому вместо схемы представления (6) обычно используется другая схема, в которой в начале каждого Списка располагается заголовок Списка (1лэЬ Ьеад) (о нем уже упоминалось в разделе 2.2А). Каждый Список содержит дополни тельный узел, который называется заголовком Списка, поэтому конфигурацию ~6) можно представить, например', таким образом: На самом деле использование узлов-заголовков не приводит к неэкономному расходованию памяти, так как в большвнстве случаев другие, казалось бы, неиспользуемые поля (на схеме (7) они показаны в виде заштрихованных прямоугольников) этих узлов могут быть полезны в иных целях, например для счетчика ссылок, для указателя на правый конец Списка, для символьного имени, для "вспомогательного' поля, которое упрощает алгоритмы обхода деревьев, и т, д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
