Введение к работе
Актуальность темы. Вероятностные методы широко применяются для решения комбинаторных задач. При задании вероятностной меры на множестве изучаемых комбинаторных объектов различные числовые характеристики таких объектов можно рассматривать как случайные величины и использовать для их исследования методы теории вероятностей. В этом случае вероятностные формулировки комбинаторных задач дают возможность использовать хорошо развитый теоретико-вероятностный аналитический аппарат, что позволяет во многих случаях существенно упростить получение результатов о комбинаторных объектах или даже находить решения, которые не удается получить с помощью других методов. Вероятностный подход обеспечивает удобную форму изложения и помогает применять хорошо развитые методы асимптотического анализа. Одним из важнейших направлений исследований является изучение предельных свойств комбинаторных объектов, проявляющихся при неограниченном возрастании числа элементов, образующих такие объекты. К наиболее известным комбинаторным объектам относятся графы. При задании на множестве рассматриваемых графов некоторого распределения вероятностей возникает понятие случайного графа. За последние 30 лет появилось множество публикаций, посвященных изучению случайных графов.
В диссертации рассматриваются деревья и леса, являющиеся удобным средством моделирования разнообразных природных и технических систем. Они находят применение при моделировании транспортных и телекоммуникационных систем, в прикладной статистике, в теории алгоритмов. Деревья и леса часто являются подграфами графов более сложной структуры, поэтому их изучение полезно в целом для теории графов.
Цель исследования. Целью работы является получение полного описания предельного поведения важнейших числовых характеристик лесов Гальтона —Ватсона при всех возможных случаях стремления к бесконечности числа деревьев и вершин леса. В частности, предполагалось:
-
Получить предельные распределения к — ых наибольших объемов деревьев, к — 1,2,...
-
Выявить условия возникновения гигантского дерева.
-
Получить предельные теоремы для числа вершин в слоях.
Объекты исследования. Объектами исследования являются леса Гальтона — Ватсона. Эти леса состоят из N корневых деревьев, принадлежащих просто генерируемому семейству. Понятие просто генерируемого семейства деревьев было введено Meir А. и Moon J.W. в 1978 г. Существует связь между такими лесами и совокупностью реализаций ветвящегося процесса Гальтона — Ватсона, начинающегося с N частиц. Точнее говоря, существует взаимно однозначное соответствие между реализациями ветвящегося процесса и классами лесов, в каждом из которых леса отличаются друг от друга только нумерацией вершин (то есть в каждом классе леса изоморфны конкретной реализации). Главное внимание в диссертации уделяется множеству лесов Гальтона — Ватсона, состоящих из N корневых деревьев и п некорневых вершин. Для таких лесов исследуются характеристики, не зависящие от нумерации вершин. В работе рассматривается предельное поведение наибольших объемов деревьев и числа вершин в слоях леса.
Методы исследования. Основными методами, используемыми в диссертации, являются обобщенная схема размещения частиц по ячейкам, методы теории ветвящихся процессов, методы характеристических и производящих функций, а также прямые комбинаторные методы. В большинстве случаев задачи о лесах сводятся к получению предельных теорем для сумм независимых одинаково распределенных случайных величин. Главной технической трудностью получения этих результатов явилось доказательство локальных предельных теорем для таких сумм в схеме серий, включая двумерный случай.
Научная новизна. В работе впервые рассматриваются леса Гальтона — Ватсона. Показано, что изучение характеристик таких лесов может быть сведено к исследованию соответствующих характеристик ветвящихся процессов Гальтона —Ватсона при уело-
вий, что общее число частиц, существовавших в процессе, фиксировано. На этом факте основаны доказательства предельных теорем. Все полученные результаты являются новыми.
Основные положения диссертации, выносимые на защиту. На защиту выносятся:
-
Установленная связь между просто генерируемыми лесами и ветвящимися процессами Гальтона—Ватсона при условии, что общее число частиц в процессе фиксировано.
-
Полное описание предельного поведения наибольших к —
ых, к — 1,2,..., членов вариационного ряда объемов дере-
вьев, расположенных в неубывающем порядке.
-
Условия возникновения гигантского дерева (то есть дерева, число вершин которого имеет порядок п, в то время как каждое из остальных деревьев содержит меньшее по порядку число верщин).
-
Предельные распределения числа вершин в слоях во всех зонах изменения параметров N, п.
Связь работы с крупными научными программами, темами.
Результаты диссертации были получены в ходе проработки темы "Вероятностные и алгебраические методы исследования дискретных объектов", входящей в план научно — исследовательских работ Института прикладных математических исследований Карельского научного центра РАН (№ гос. регистрации 01.9.60 0 12636) и выполняющейся совместно с кафедрой алгебры и теории вероятностей математического факультета Петрозаводского университета в рамках проекта "Интеграция высшего образования и фундаментальной науки Республики Карелия" Федеральной целевой программы "Государственная поддержка интеграции высшей школы и фундаментальной науки на 1997 — 2000 годы"(ФЦП "Интеграция", per. №634). В 1997 — 98 г.г. автор диссертации была руководителем гранта РФФИ 97 — 01 —00065 "Исследование случайных лесов", в 2000 г. автор входит в состав исполнителей гранта РФФИ 00 — 01 — 00233 "Вероятности на деревьях и лесах" и является победителем конкурса персональных грантов для аспиран-
тов, проведенного Администрацией Санкт-Петербурга, Министерством образования РФ и РАН при участии ФЦП "Интеграция".
Апробация результатов диссертации. Основные результаты диссертации докладывались на IV и V Петрозаводских международных конференциях "Вероятностные методы в дискретной математике" (1996, 2000), 2—ой Международной школе по теории графов (Новосибирск, 1997), 7 —ой Вильнюской конференции по теории вероятностей и математической статистике (1998), семинаре Института прикладных математических исследований Карельского научного центра РАН (2000).
Публикация результатов. По теме диссертационной работы опубликовано 7 научных работ, из них 3 статьи в центральном журнале, 1 статья в сборнике трудов международной конференции, 2 статьи в сборниках научных трудов и 1 тезисы доклада на международной конференции.
Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Общий объем диссертации составляет 112 страниц. Список литературы содержит 69 наименований.