Введение к работе
Актуальность темы. Вероятностные методы нашли широкое применение при исследовании комбинаторных объектов. Одной из важных областей приложения таких методов является теория графов. Понятие случайного графа возникает при задании на множестве рассматриваемых графов некоторого распределения вероятностей, тогда различные числовые характеристики графов становятся случайными величинами. Такой подход позволяет для решения многих перечислительных задач теории графов использовать мощный аналитический аппарат теории вероятностей, что приводит к результатам, недоступным для традиционных комбинаторных методов.
Одним из наиболее известных и хорошо изученных видов графов являются деревья и леса. Актуальность исследования таких графов связана с тем, что они часто являются удобным средством моделирования разнообразных объектов, как в технике (вычислительные устройства и алгоритмы, транспортные и коммуникационные сети), так и в самой математике (описания конечных множеств, методы кластерного анализа и т.д.). Кроме того, деревья и леса можно рассматривать как подграфы графов более сложной структуры (например, графов отображения), поэтому их изучение полезно и для развития самой теории графов.
Известно, что изучение помеченных графов обычно является значительно более простої! задачей, чем исследование непомеченных графов (т.е.классов изоморфных графов). Поэтому к настоящему времени в основном изучались деревья и леса с занумерованными вершинами. Для исследования лесов различных классов оказалось возможным применение сходных методов, а полученные результаты нередко отличаются лишь конкретными
значениями числовых параметров. В связи с этим представляется актуальной задача создания общей теории случайных лесов, выводы которой были бы справедливы для разнообразных классов случайных лесов. До сих пор случайные деревья и леса в основном изучались при задании равномерного распределения вероятностей на множестве рассматриваемых объектов, ясно, что общая теория должна быть свободна от такого ограничения и охватывать широкий класс вероятностных мер.
Использование вероятностных методов в комбинаторном анализе часто позволяет свести задачи о числовых характеристиках комбинаторных объектов к задачам о суммировании независимых вспомогательных случайных величин. При исследовании асимптотических свойств случайных лесов это приводит к необходимости получения соответствующих предельных распределений. Поведение слагаемых зависит от нескольких параметров, поэтому требуется доказательство большого числа предельных теорем в различных зонах изменения параметров. В большинстве случаев приходится получать локальные предельные теоремы для схем серий вспомогательных независимых случайных величин, в том числе и в области сколь угодно больших уклонений. К сожалению, известные в настоящее время предельные теоремы не охватывают многих возникающих здесь случаев, поэтому для получения результатов о случайных лесах в диссертации приводятся соответствующие доказательства. Ранее, при рассмотрении конкретных видов случайных деревьев и лесов, вводились вспомогательные случайные величины, имеющие специально выбранные распределения вероятностей, что существенно облегчало доказательство предельных теорем в силу возможности использования свойств конкретных распределений. В диссертации приходится рассматривать суммы случайных величин при достаточно общих ограничениях на распределения слагаемых. Поэтому такие предельные теоремы могут представлять самостоятельный инте-
pec. Использование при изучении случайных лесов методов теории ветвящихся процессов вызвало также необходимость получения новых результатов о процессах Гальтона — Ватсона.
Цель работы состоит в получении полного описания предельного поведения важнейших числовых характеристик случайных лесов при всех возможных соотношениях между стремящимися к бесконечности числами образующих лес корневых деревьев и некорневых вершин. Эти теоремы носят общий характер и справедливы для широкого класса случайных лесов. В работе также дается общая характеризация случайных лесов через соответствующие им ветвящиеся процессы Гальтона— Ватсона при весьма слабых ограничениях на распределение числа прямых потомков одной частицы. С помощью полученных результатов о случайных лесах найдены предельные распределения некоторых характеристик случайных отображений.
Методы исследования. Использовались методы теории ветвящихся процессов, обобщенная схема размещения частиц по ячейкам, методы доказательства предельных теорем для сумм независимых случайных величин, включая локальные теоремы и большие уклонения в схеме серий. Использовался также метод характеристических функций, производящие функции, методы теории функций комплексного переменного.
Научная новизна и практическая значимость. Установлена связь между случайными лесами общего вида, состоящими из N корневых деревьев с и некорневыми вершинами и ветвящимися процессами Гальтона —Ватсона, начинающимися с N частиц, при весьма слабых ограничениях как на распределения числа потомков одной частицы, гак и на вероятностную меру, задаваемую на множестве лесов. На основе этой связи предложен метод исследования различных числовых характеристик случайных лесов. С помощью такого подхода получен ряд теорем, описывающих при М, и-^-оо и всех возможных соотношениях между N и п
- A -
асимптотическое поведение важнейших характеристик лесов : высоты, числа деревьев заданного объема, максимального объема дерева. Представляют самостоятельный интерес полученные в диссертации локальные предельные теоремы для схем серий независимых решетчатых слагаемых, в частности, для случая сколь угодно больших уклонений. Обнаружены новые свойства ветвящихся процессов Гальтона—Ватсона, начинающихся с N частиц. С целью иллюстрации возможности использования результатов о случайных лесах для изучения графов более сложной структуры, в диссертации доказан ряд свойств графов отображений. Все полученные результаты являются новыми.
Публикация и апробация работы. По теме диссертации опубликована 31 работа, в том числе монография "Случайные леса". Результаты докладывались на Международном конгрессе математиков (Варшава, 1983), на Петрозаводских конференциях "Вероятностные методы дискретной математики" (1983, 1988, 1992), на Международных Вильнюсских конференциях по теории вероятностей и математической статистике (1985, 1989), на Первом Всемирном конгрессе общества математической статистики и теории вероятностей им.Бернулли (Ташкент, 1986), на Международных семинарах по случайным графам (Познань, 1987, 1989), на Шестой летней школе по теории вероятностей и математической статистике (Варна, 1988), на Всесоюзной школе "Дискретная математика и ее применение при моделировании сложных систем" (Иркутск, 1991), на семинаре "Вероятностные методы в дискретной математике" в Математическом институте РАН им.В.А.Стеклова.