Введение
1 Реализация случайных графов графами расстояний 6
1.1 Введение и формулировки геометрических результатов 6
1.2 Постановка вероятностной задачи и формулировки соответствующих результатов 8
1.3 Доказательства геометрических результатов 9
1.3.1 Доказательство теоремы 1 9
1.3.2 Доказательства теорем 2-4 10
1.3.3 Доказательство теоремы 8 11
1.4 Доказательства вероятностных результатов 13
1.4.1 Доказательство теоремы 5 13
1.4.2 Доказательство теоремы 6 13
1.5 Обобщения вероятностных результатов 15
1.5.1 Пороговые вероятности для реализации графом расстояний в размерностях d ^ 3 15
1.5.2 Пороговые вероятности для реализации графом расстояний в размерности d = 1 16
2 Реализация случайных графов графами диаметров в размер ностях d = 2 и d = 3 19
2.1 Введение 19
2.2 Формулировки результатов 20
2.3 Доказательства результатов для случая d = 2 22
2.3.1 Доказательство теоремы 13 22
2.3.2 Доказательство теоремы 14 23
2.3.3 Доказательство теоремы 15 23
2.3.4 Доказательство теоремы 16 24
2.3.5 Доказательство теоремы 17 27
2.3.6 Доказательство теоремы 18 31
2.4 Доказательства результатов для случая d = 3 35
2.4.1 Доказательство теоремы 19 35
2.4.2 Доказательство теоремы 20 36
2.4.3 Доказательство теоремы 21 36
2.4.4 Доказательство теоремы 22 38
2.4.5 Доказательство теоремы 23 41
3 Реализация случайных графов графами диаметров в размер ности d 4 48
3.1 Введение и формулировки результатов 48
3.2 Верхние оценки 49
3.2.1 Доказательство теоремы 26 49
3.2.2 Доказательство теоремы 28 50
3.3 Нижние оценки 51
3.3.1 Доказательство теоремы 24 51
3.3.2 Доказательство теоремы 25 54
3.4 Доказательство теоремы 27 55
3.4.1 Случай d = 4, р = const 56
3.4.2 Случай d > 4, р = const 60
3.5 Проблема со случаем р —> 0 63
Заключение 64
Список литературы
