Оглавление
Введение 4
1 История и формулировки результатов 8
1.1 Основные определения и история задачи.......................... 8
1.2 Постановка основной задачи ....................................10
1.3 Формулировки результатов.......................................10
2 О связности случайного дистанционного графа 13
2.1 Доказательство пункта б) теоремы 1.............................14
2.2 Схема доказательства пункта а) теоремы 1.....................16
2.3 Доказательства утверждений 2.2, 2.3, 2.4, 2.5, 2.6.............17
2.3.1 Доказательство утверждения 2.2...........................17
2.3.2 Доказательство утверждения 2.3...........................20
2.3.3 Доказательство утверждения 2.4...........................20
2.3.4 Доказательство утверждения 2.5...........................21
2.3.5 Доказательство утверждения 2.6...........................22
3 О распределении количества древесных компонент в случайном дистанционном графе 23
3.1 Вспомогательные утверждения и леммы............................24
3.1.1 Формулировки вспомогательных утверждений.................24
3.1.2 Доказательство утверждения 3.1...........................26
3.1.3 Доказательство утверждения 3.2...........................27
3.1.4 Формулировка и доказательство леммы 1....................29
3.1.5 Формулировка и доказательство леммы 2....................33
3.1.6 Доказательство утверждения 3.3...........................34
3.1.7 Доказательство утверждения 3.4...........................35
3.1.8 Доказательство утверждения 3.5...........................35
3.2 Доказательство теоремы 2.......................................36
3.2.1 Доказательство пункта. 1 ............................37
3.2.2 Доказательства пунктов 2 и 4...........................37
3.2.3 Доказательство пункта 3 ...............................39
2
3.2.4 Доказательство пункта 5 .................................41
4 О гигантской компоненте в случайном дистанционном графе 43
4.1 Вспомогательные утверждения и леммы.............................44
4.1.1 Формулировки вспомогательных утверждений и лемм . . 44
4.1.2 Доказательство утверждения 4.1.........................45
4.1.3 Доказательство утверждения 4.2.........................46
4.1.4 Доказательство утверждения 4.3.........................48
4.1.5 Доказательство утверждения 4.4.........................49
4.1.6 Доказательство утверждения 4.5.........................51
4.2 Завершение доказательства пункта б) теоремы 3...................51
4.3 Доказательство пункта а) теоремы 3..............................54
4.3.1 Ветвящиеся процессы......................................54
4.3.2 Завершение доказательства пункта а) теоремы 3..........54
4.4 О предельной вероятности связности внутри фазового перехода 56
4.4.1 Доказательство теоремы 4.................................56
3
Введение
Открытие того, что детерминированные утверждения могут быть доказаны с помощью вероятностных соображений, позволило уже в первой половине XX в. установить ряд замечательных фактов из анализа, теории чисел, комбинаторики и теории информации. Вскоре стало ясно, что метод, который сейчас называется вероятностным, является весьма мощным инструментом получения результатов в дискретной математике.
Одним из тех, кто первым применил данный метод к задачам экстремальной комбинаторики, был венгерский математик Т. Селе. С помощью вероятностных соображений он доказал, что существует турнир на п вершинах, который содержит не менее п\/2п~1 гамильтоновых путей (1943, [1]). Селе не построил явную конструкцию такого турнира, но показал, что множество турниров, удовлетворяющих данному требованию, не пусто. Это является характерной чертой такого способа доказательств. Именно поэтому этот метод также называется неконструктивным.
Широкое применение метода к теории чисел привело к появлению вероятностной теории чисел ([2] — [3]). Одним из первых применений неконструктивного метода к данной отрасли математики было новое, более простое доказательство теоремы Г. Харди и С. Рамануджана (1917, [4]), принадлежащее П. Турану (1934, [5]).
Примечательно, что примерно в это же время в вычислительной математике стремительно развивается применение статистических методов испытаний, более известных под названием “Метод Монте-Карло” (1949, |6|). Статистические методы вычислений использовались еще в XVIII - XIX вв. Самым широкоизвестным таким методом, в том или ином виде входящем во многие университетские учебники по теории вероятностей, является метод определения числа 7г с помощью бросания иглы Бюффона (например, [7]).
Наибольшее применение вероятностный метод получил в экстремальной теории множеств, а также в теории графов и гиперграфов. Одним из первых результатов в этих областях была теорема П. Эрдеша, Ч. Ко и Р. Радо (1938, [8]) об экстремальных свойствах совокупностей подмножеств конечного множества. Именно выдающийся венгерский математик Эрдеш считается
4
основателем вероятностного метода. В 50-е годы он занялся систематическим развитием метода, внеся тем самым неоценимый вклад в становление комбинаторики (в том числе — вероятностной).
Результаты, получаемые вероятностным методом, можно условно разделить на две группы. К первой группе относятся факты, которые формулируются в терминах существования комбинаторных структур, обладающих рядом определенных свойств. Основная идея доказательства подобных фактов может быть описана следующим образом: мы строим вероятностное пространство, в котором роль элементарных событий играют некоторые комбинаторные структуры, и затем показываем, что такие структуры обладают необходимыми свойствами с положительной вероятностью ([8] — [15] и др.). Вторая группа состоит из результатов, которые сами по себе являются теоретико-вероятностными. Эти результаты связаны с изучением определенных классов комбинаторных объектов, например, случайных графов или случайных матриц ((15) — [22]).
В диссертации приведены результаты, которые в соответствии с изложенной выше классификацией можно отнести ко второй группе. А именно, рассмотрена модель случайного дистанционного графа специального вида.
Как часто бывает в математике, изучение вероятностных свойств графа было начато независимо и практически одновременно несколькими исследователями. А именно, Дж. Фордом и Дж. Уленбеком (1956, [23]), Э. Гильбертом (1957, |24|), Т. Остином, Р. Фэйгином, В. Пенне и Дж. Риорданом (1959, [25]), П. Эрдешом и А. Реньи (1959, [17] — [19]). Тем не менее, только последние двое авторов предложили методы, которые легли в основу вероятностного построения теории случайных графов.
Эрдеш и Реньи рассмотрели две близких модели случайного графа (7(АГ, М) и С(Аг,р). В обеих моделях в роли элементарных событий в вероятностном пространстве Пдг выступают графы на N вершинах без петель, кратных ребер и ориентации. В первом случае рассматриваются только графы с М ребрами (М < Сдг), и вероятность каждого из этих графов полагается равной 1/С$ . Во второй модели количество ребер не фиксировано, то или иное ребро между' вершинами графа проводится с вероятностью р независимо от других ребер.
Рассмотрим второй случай более подробно. Пусть N 6 К, 0 < |) < 1. Рассмотрим множество
ПА: = {С = (У„,Е)}
всех неориентированных графов без петель и кратных ребер с множеством вершин Рдг = {1,..., А^}. Случайный граф в модели С(М,р) Эрдеша Репьи —
5
это случайный элемент со значениями во множестве Qn и распределением РN,p на
Fn = 2n,v,
определенным формулой
Pnj>{G) = р|£|(1 - p)c«_|ß|.
Задачам, связанным с исследованиями случайного графа G(I\г,р), посвящено огромное количество работ. П. Эрдеш, А. Реньи (| 17], (18]), К. Шургер ([26]), Б. Боллобаш ([27]), 3. Палка ([28]), А.Д. Барбур ([29]) и др. произвели значительный вклад в изучение распределения малых подграфов в случайном графе. Распределением количества деревьев занимались П. Эрдеш, А. Реньи ([18]), Б. Боллобаш ([30]), А.Д. Барбур ([29]) и др. Вопросам, касающимся связности случайного графа, посвящены работы Е.Н. Гильберта ([31]), Т.Л. Остина и др. ([25]), П. Эрдеша, А. Реньи, В.Е. Степанова ([32], [33]), Г.И. Ивченко ([34]), Б. Боллобаша ([35]) и др. Поиском гигантской компоненты и определением ее размера занимались Т. Лучак ([36], [37]), Дж. Вирман ([37]), Б. Боллобаш ([30]), П. Эрдеш, А. Реньи ([18]) и др. При каких условиях случайный граф является гамильтоновым, можно узнать из работ И. Палаш-ти (|38| - [40]), В.А. Перепелицы ([41]), Дж. Муна ([42]), Е. Райта ([43], [44]) и др. Длину максимального пути для р = c/N изучали М. Айтаи, Дж. Комлош, Е. Семереди ([45]), В.Ф. деля Вега ([46]), Б. Боллобаш ([47], [48]), Т.П. Фснне, А.М. Фриз ([48]) и др. В работах А. Хоффмана, Р. Синглетона ([49]), Р. Дэме-релла (|50|), Е. Баннаи, Т. Ито (|51|), Х.Д. Фридмана ([52], [53]) и др. изучено распределение диаметра случайного графа.
Тем не менее во многих приложениях модель Эрдеша-Реньи мало применима. Поэтому разрабатывались другие модели, которые призваны описывать зарождение или рост тех или иных реальных структур. Это могут быть биологические, социальные, транспортные сети и др. В связи со своим стремительным развитием в последние годы особенное место среди этих структур занимает Интернет. Множество работ посвящено исследованию так называемых веб-графов, вершины которых суть какие-либо структурные единицы в Интернете: речь может идти о страницах, сайтах, хостах, владельцах и пр., а ребра — гиперссылки между вершинами ([16], [54]).
Также представляют интерес модели, которые естественным образом обобщают модель Эрдеша-Реньи. А именно, фиксируется некоторый граф Я = (V,E), а затем ребра этого графа удаляются независимо друг от друга с одной и той же вероятностью. Понятно, что случай полного графа на п вершинах соответствует классической модели. Граф Я может как отображать некоторую реальную структуру, так и иметь геометрическое происхождение.
6
- Київ+380960830922