Модели случайных графов

А. М. Райгородский

Модели случайных
графов

МЦНМО

А. М. Райгородский

Модели случайных графов

Электронное издание

Москва
Издательство МЦНМО


УДК ..
ББК .
Р

Райгородский А. М.
Модели случайных графов.
Электронное издание.
М.: МЦНМО, .
 с.
ISBN ----

Книга посвящена теории случайных графов. Эта теория находится
на стыке комбинаторики, теории графов и теории вероятностей.
Книга основана на многочисленных лекциях, которые автор читал
в МГУ, МФТИ, на школах «Современная математика» в Дубне и «Комбинаторная математика и теория алгоритмов» в Судиславле, а также
в Школе Анализа Данных Яндекса.
Книга предназначена для широкого круга читателей.

Подготовлено на основе книги:
Райгородский А. М. Модели случайных графов. –– -е изд., доп. –– М.: МЦНМО,
. ––  с. –– ISBN ----

Издательство Московского центра
непрерывного математического образования
, Москва, Большой Власьевский пер., ,
тел. ()––.
http://www.mccme.ru

ISBN ----
© Райгородский А. М., .
© МЦНМО, .

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Глава 
Некоторые основы теории вероятностей . . . . . . . . . . . . . . . .

1.1. Классическая вероятность . . . . . . . . . . . . . . . . . . . . . .

1.2. Схема Бернулли . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3. Схема серий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4. Общее конечное вероятностное пространство . . . . . . . . .

1.5. Условные вероятности и независимость событий . . . . . . .

1.6. Несколько слов о бесконечных вероятностных пространствах 
1.7. Случайные величины и их распределения . . . . . . . . . . . .

1.8. Моменты распределений . . . . . . . . . . . . . . . . . . . . . . .

1.9. Формула обращения и предельные теоремы пуассоновского
типа
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.10. Нормальная аппроксимация . . . . . . . . . . . . . . . . . . . .

1.11. Неравенства Чебышёва и Маркова . . . . . . . . . . . . . . . .

1.12. Уточнение неравенства Чебышёва в случае схемы Бернулли 
1.13. Условные вероятности и математические ожидания относительно разбиений . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.14. Понятие о мартингале . . . . . . . . . . . . . . . . . . . . . . . .

1.15. Неравенство Азумы . . . . . . . . . . . . . . . . . . . . . . . . . .


Глава 
Модель Эрдёша –– Реньи случайного графа . . . . . . . . . . . . . . .

2.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2. Определение модели Эрдёша –– Реньи . . . . . . . . . . . . . . .

2.3. Одна естественная модификация модели . . . . . . . . . . . .

2.4. Треугольники в случайных графах . . . . . . . . . . . . . . . . .

2.4.1. Постановка задачи и формулировки результатов . . .

2.4.2. Доказательство теоремы  . . . . . . . . . . . . . . . . .

2.4.3. Доказательство теоремы  . . . . . . . . . . . . . . . . .

2.4.4. Доказательство теоремы  . . . . . . . . . . . . . . . . .

2.5. Связность случайного графа . . . . . . . . . . . . . . . . . . . . .

2.5.1. Формулировки результатов и комментарии к ним . .

2.5.2. Доказательство теоремы  . . . . . . . . . . . . . . . . .

2.5.3. Вокруг теоремы  . . . . . . . . . . . . . . . . . . . . . . .

2.5.4. Гигантская компонента . . . . . . . . . . . . . . . . . . .



Оглавление

2.6. Хроматическое число случайного графа . . . . . . . . . . . . .

2.6.1. Определения, формулировки и комментарии . . . . .

2.6.2. Мартингалы реберного и вершинного типов
. . . . .

2.6.3. Доказательство теоремы : формулировка леммы 
и вывод из нее . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6.4. Доказательство теоремы : доказательство леммы 

2.6.5. Нижняя оценка в теореме  . . . . . . . . . . . . . . . .

2.6.6. Верхняя оценка в теореме : план действий . . . . . .

2.6.7. Верхняя оценка в теореме : идея доказательства . .

2.6.8. Верхняя оценка в теореме : выбор параметров
и оценка вероятности . . . . . . . . . . . . . . . . . . . . . . . . .

2.6.9. Верхняя оценка в теореме : доказательство леммы  
2.6.10. Комментарий к лемме  . . . . . . . . . . . . . . . . . .

2.6.11. Чем Yk лучше Xk, или почему не работает неравенство Чебышёва? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6.12. О функции u в теореме  . . . . . . . . . . . . . . . . .

2.7. О числе независимости и кликовом числе случайного графа

2.8. Числа Рамсея
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.9. Хроматическое число и обхват графа . . . . . . . . . . . . . . .

2.10. Законы нуля или единицы . . . . . . . . . . . . . . . . . . . . .

2.10.1. Язык первого порядка для графов . . . . . . . . . . . .

2.10.2. Формулировки результатов . . . . . . . . . . . . . . . .

2.10.3. Игра Эренфойхта . . . . . . . . . . . . . . . . . . . . . . .

2.10.4. Выигрышная стратегия для Консерватора . . . . . . .

2.11. Еще ряд сюжетов . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.11.1. Деревья в случайных графах
. . . . . . . . . . . . . . .

2.11.2. Еще несколько слов о хроматическом числе случайного графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.11.3. Планарность случайного графа . . . . . . . . . . . . . .

2.11.4. Степени вершин случайного графа . . . . . . . . . . .

2.11.5. Изоморфизм случайных графов . . . . . . . . . . . . .


Глава 
Обобщенная модель Эрдёша –– Реньи и случайные дистанционные
графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1. Определение модели . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2. Случайные подграфы куба . . . . . . . . . . . . . . . . . . . . . .

3.3. Случайные дистанционные графы . . . . . . . . . . . . . . . . .

3.4. Вспомогательные факты и свойства полного дистанционного графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.1. Немного простой аналитики . . . . . . . . . . . . . . . .


Оглавление


3.4.2. О числе независимости полного графа расстояний
.

3.4.3. О кликовом числе полного графа расстояний . . . . .

3.4.4. О хроматическом числе полного графа расстояний .

3.4.5. О числе ребер в произвольном подмножестве множества вершин полного графа расстояний . . . . . . . . . . . . .

3.4.6. «Олимпиадный» комментарий к предыдущему пункту

3.5. Хроматическое и кликовое числа дистанционного графа . .

3.6. Хроматическое число случайного дистанционного графа . .

3.7. Дистанционные числа Рамсея . . . . . . . . . . . . . . . . . . . .

3.7.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . .

3.7.2. Формулировки результатов . . . . . . . . . . . . . . . . .

3.7.3. Доказательство теоремы  . . . . . . . . . . . . . . . . .

3.7.4. Доказательство теоремы  . . . . . . . . . . . . . . . . .

3.8. О связности случайного дистанционного графа . . . . . . . .

3.9. Законы нуля или единицы для случайного дистанционного
графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.10. Дистанционные графы и их случайные подграфы: еще одно определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.10.1. Определение и результаты . . . . . . . . . . . . . . . . .

3.10.2. Доказательство теоремы  . . . . . . . . . . . . . . . .


Глава 
Модели случайных веб-графов . . . . . . . . . . . . . . . . . . . . . .

4.1. Наблюдения Барабаши –– Альберт . . . . . . . . . . . . . . . . .

4.2. Модель Боллобаша –– Риордана . . . . . . . . . . . . . . . . . . .

4.2.1. Динамическая модификация . . . . . . . . . . . . . . . .

4.2.2. Статическая модификация, или LCD-модель . . . . . .

4.2.3. Некоторые результаты . . . . . . . . . . . . . . . . . . . .

4.2.4. Доказательство теоремы  при k =1
. . . . . . . . . .

4.3. Модель копирования
. . . . . . . . . . . . . . . . . . . . . . . . .


Глава 
Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Предисловие

В этой книге мы поговорим об одной весьма красивой и богатой
приложениями науке –– науке о случайных графах. Эта наука находится на стыке комбинаторики, теории графов и теории вероятностей.
В основе ее лежит глубокая идея о том, что мощные инструменты
современной теории вероятностей должны поспособствовать более
верному осознанию природы графа, призваны помочь решению многих комбинаторных и теоретико-графовых задач.
Данная книга возникла на основе лекций, которые ее автор читал на школах «Современная математика» в Дубне и «Комбинаторная
математика и теория алгоритмов» в Судиславле, а также в Школе Анализа Данных Яндекса. В ней мы не претендуем на исчерпывающее изложение теории, которая давно уже превратилась в огромную и бурно
развивающуюся –– почти необозримую –– математическую дисциплину. У нас совсем другая цель. Мы хотим на максимально доступном
уровне рассказать наиболее яркие и красивые сюжеты, связанные
со случайными графами. В сущности, мы постараемся сделать книгу
понятной студентам младших курсов университетов и даже старшеклассникам, всерьез увлекающимся математикой. В то же время мы
дойдем до столь глубоких и нетривиальных фактов, что книга окажется полезной всем, кто интересуется комбинаторикой, вероятностью
и их приложениями.
В целом структура книги следующая. В первой главе мы изложим
основы теории вероятностей, знание которых необходимо для дальнейшего чтения. Читатель, знакомый с этими основами, может при
желании пропустить эту главу. Однако стоит иметь в виду, что некоторые понятия, обсуждаемые в ней, не вполне элементарны. Например,
таково понятие мартингала, которое в стандартных курсах теории
вероятностей обычно не возникает.
Во второй главе мы расскажем о модели Эрдёша –– Реньи случайного графа, которая была предложена ровно полвека назад и с которой, по большому счету, и началась вся наука. Мы представим,
в наглядной и увлекательной форме, несколько результатов, которые
удается получить в рамках такой модели.
В третьей главе мы поговорим о моделях, которые естественным
образом обобщают модель Эрдёша –– Реньи. С их помощью мы дока

Предисловие


жем ряд исключительно красивых утверждений в области комбинаторной геометрии.
Наконец, в четвертой главе мы выйдем, можно сказать, на передний край науки: мы обсудим модели Интернета и других больших
или, как принято говорить, «реальных» сетей.
Заключительным разделом книги будет «приложение», в котором
мы опишем ряд простых и в то же время довольно скучных понятий
математического анализа. Разумеется, мы предполагаем хотя бы поверхностное знакомство читателя с пределами, производными и интегралами. Однако некоторые объекты и обозначения мы постараемся аккуратно ввести и прокомментировать.
Хотя, повторим еще раз, наша книга отнюдь не является полноценной монографией, она, безусловно, закладывает основы теории
и с нее удобно начинать изучение случайных графов, благо она предлагает сразу (как минимум) три принципиально различных направления исследований. Некоторые факты, доказанные в ней, совсем
свежие, и они еще ждут правильного осмысления и развития. Мы
приглашаем читателя на увлекательную экскурсию и надеемся, что
если кому-то она будет просто интересной, то кому-то она поможет
и с выбором задач для последующего их изучения.
Отметим, что для дальнейшей работы со случайными графами
крайне полезны, например, такие книги, как [,,,]. Есть и масса другой близкой по тематике литературы. Кое-что мы процитируем
по ходу дела, а кое-что заинтересованный читатель, сориентировавшись в науке, отыщет и сам.

. Некоторые основы теории
вероятностей

В этой главе мы расскажем о наиболее значимых для дальнейшего аспектах теории вероятностей. Наше изложение будет достаточно
сжатым, хотя и предельно элементарным, и замкнутым в себе. В качестве литературы к этой главе сразу стоит указать книги [,,].

.. Классическая вероятность

Представим себе обычную игральную кость –– кубик, сделанный
из идеально однородного материала. Если мы бросим такую кость
на стол, то произойдет ровно одно из шести событий: либо кость
выпадет кверху той гранью, на которой нарисована одна точка, либо
той, на которой точек две, и так далее. Поскольку кость идеально однородная, разумно считать, что указанные события равновероятны.
При этом они попарно несовместны в том смысле, что никакие два
из них не происходят одновременно. Наконец, как мы уже говорили,
одно из этих событий непременно случится. Все перечисленные об
стоятельства позволяют сказать, что с вероятностью 1

6 кость выпадет
заданной стороной кверху.
В общем случае классическая вероятность устроена совершенно
аналогично. Есть некоторый набор событий ω1, …, ωn. Они попарно
несовместны, одно из них обязательно реализуется, и они равновероятны. Такие события называют элементарными, и полагают вероят
ность каждого из них равной 1

n.
Теперь допустим, что некоторое событие происходит тогда и только тогда, когда выполнено (ровно) одно из элементарных событий
ωi1, …, ωik. Например, событие «кость выпала кверху гранью, на которой нарисовано четное число точек» имеет место, коль скоро реализовалось либо элементарное событие «с двумя точками», либо элементарное событие «с четырьмя точками», либо элементарное событие
«с шестью точками». Говорят, что такие элементарные события благоприятствуют данному событию. Очевидно, что и в примере с костью

вероятность интересующего нас события следует полагать равной 3

6,

и в общем случае ее нужно приравнивать к k

n.

.. Схема Бернулли


В итоге вероятность любого события есть отношение числа благоприятствующих ему элементарных событий к числу всех элементарных событий.
Обычно используют формальные обозначения и соответствующую терминологию. А именно, полагают Ω ={ω1, …, ωn} и называют
множество Ω пространством элементарных событий. Каждое событие интерпретируют как подмножество в Ω, состоящее из благоприятствующих элементов. Множество всех событий обозначают . Как
правило, –– это множество всех подмножеств из Ω, так что ||=2n.
Наконец, вероятность обозначают символом P (в честь «probability»
(англ.), «probabilit´e» (фр.) и т. д.). Это функция, заданная на множе
стве и принимающая значения в
0, 1

n, …, n −1

n
, 1
: P(A) = |A|

n .

Всю тройку описанных объектов (Ω, , P) называют (классическим)
вероятностным пространством.
Ясно, что события можно объединять и пересекать. Если есть события A, B ∈ , то событие A ∪ B –– это событие, которое, по сути,
состоит в том, что либо выполнено A, либо выполнено B. Аналогично, A ∩ B –– это событие, состоящее в том, что одновременно реализовались A и B. Наконец, через A обозначают отрицание события A:
в терминах множеств A =Ω \ A.
Вероятность обладает очевидными свойствами:
) Для любого события A ∈выполнено P(A)∈[0, 1].
) P(Ω)=1, P(∅)=0.
) Каковы бы ни были A, B ∈ , P(A ∪ B) = P(A) + P(B) − P(A ∩ B).
В частности, если A ∩ B =∅, то P(A ∪ B)= P(A)+ P(B).
) Для любого события A ∈выполнено P(A)=1− P(A).

.. Схема Бернулли

Вот еще одна вероятностная конструкция, которая очень широко
используется в науке и ее приложениях; для нас она также будет одной из основных.
Допустим, есть у нас монетка. Только, в отличие от нашей же
игральной кости, эта монетка сделана из неоднородного материала.
Бросим мы ее на стол. С какой «вероятностью» она ляжет «решкой»
кверху? с какой –– «орлом»? Ну, это зависит от распределения материала внутри монетки. Не будем вдаваться в столь технические детали.
Просто сочтем, что p ∈ [0, 1] –– это и есть вероятность решки. Соответственно, тогда вероятность орла –– это q = 1 − p: на ребро наша
монетка не становится.


. Некоторые основы теории вероятностей

Будем бросать монетку на стол и каждый раз фиксировать «выпавшую» сторону. Если выпала решка, напишем  и скажем, что произошел успех; если выпал орел, напишем  и скажем, что случилась
неудача. Всего таких «испытаний» произведем n штук. Это и будет схемой испытаний Бернулли. На выходе образуется последовательность
из нулей и единиц длины n. Эта последовательность, естественно,
случайна. А какова вероятность, что это будет именно последовательность (x1, …, xn) с конкретными x1, …, xn? Кажется весьма уместным
счесть, что такая вероятность равна произведению вероятностей чисел x1, …, xn. Иными словами, если ω =(x1, …, xn), то

P(ω) = p
n
i=1 xiqn−
n
i=1 xi.

Снова возникает вероятностное пространство. На сей раз элементарными событиями в нем служат как раз последовательности ω:
недаром мы их так и обозначили. В результате Ω –– пространство элементарных событий –– состоит из всевозможных реализаций схемы
испытаний Бернулли, каковых, очевидно, 2n. Как и прежде, события –– это всевозможные подмножества из Ω. Например, событие «в n
испытаниях Бернулли произошло ровно k успехов» формируется из Ck
n
элементарных кирпичиков –– тех последовательностей нулей и единиц, в которых ровно k единиц. Множество событий имеет мощность 22n.
Понятно, что вероятность P –– это и здесь функция, определенная
на и принимающая значения из [0, 1]. По аналогии с классической вероятностью, для данного A ∈ она полагается равной сумме вероятностей элементарных событий, которые благоприятствуют A: P(A) =
ω∈A
P(ω). Например, вероятность события, описанного

в предыдущем абзаце, есть Ck
n pkqn−k. По понятным причинам ее называют биномиальной вероятностью.
Нетрудно видеть, что и в нынешнем пространстве (Ω, , P) выполнены свойства  ––  из предыдущего параграфа.
Приведем пример сравнительно нетривиального вычисления, связанного со схемой Бернулли и биномиальными вероятностями. Пусть
дано множество ℜn = {1, …, n}. Производя схему испытаний Бернулли, извлекаем из него элемент i, коль скоро в i-м испытании произошел успех; иначе переходим к следующему испытанию. В итоге получается случайное подмножество U ⊂ ℜn (состоящее из извлеченных
элементов). Аналогично строим множества V и W. Спрашивается:
какова вероятность того, что U ∩ V ⊆ W ⊆ U ∪ V? Обозначим через A
такое событие.

.. Схема серий


Запишем друг под дружкой реализации схем Бернулли, «породившие» множества U, V, W:

(x1, x2, …, xn),
(y1, y2, …, yn),

(z1, z2, …, zn).

Если A произошло, то нетрудно видеть, что при любом i столбец
с номером i в приведенной табличке не может состоять из элементов xi = 1, yi = 1, zi = 0 и из элементов xi = 0, yi = 0, zi = 1: в первом случае получилось бы, что i-й элемент множества ℜn принадлежит U и V, но не принадлежит W, что невозможно, поскольку ввиду
A у нас U ∩ V ⊆ W; во втором случае было бы противоречие с условием W ⊆ U ∪ V. Все остальные тройки из нулей и единиц в столбцах
встречаться могут.
Вероятность тройки 1, 1, 0 есть, очевидно, p2q; вероятность тройки 0, 0, 1 есть q2p. Значит, вероятность того, что «запрещенная» тройка в данном столбце не возникла, есть, по свойствам вероятности,
1 − (p2q + q2p) = 1 − pq(p + q) = 1 − pq. Окончательно получаем, что
P(A)=(1− pq)n.
Правомерность возведения в степень в рамках последнего рассуждения так же интуитивно понятна, как и допустимость перемножения
вероятностей в самом определении схемы Бернулли. Строгое обоснование подобным действиям будет дано чуть позднее –– когда мы будем
говорить о независимости событий.

.. Схема серий

Важной разновидностью схемы испытаний Бернулли служит так
называемая схема серий. Рассмотрим произвольную (вообще говоря,
бесконечную) последовательность натуральных чисел n1, n2, …, nk,
… Для каждого i осуществим ni испытаний Бернулли, причем вероятность успеха будем считать зависящей от i. Иными словами, мы
производим серии испытаний, и вероятность успеха в каждой очередной серии есть pi ∈[0, 1] (меняем монетки от серии к серии). Для
определения случайного графа такая схема нам будет очень нужна.

.. Общее конечное вероятностное пространство

Рассмотренные в предыдущих параграфах вероятностные конструкции ничего не стоит обобщить. А именно, пусть Ω –– произвольное конечное множество. Назовем его пространством элементарных


. Некоторые основы теории вероятностей

событий. Пусть, далее, –– произвольная совокупность подмножеств
из Ω, обладающая свойствами:
) для любых A, B ∈выполнено A ∪ B ∈;
) для любых A, B ∈выполнено A ∩ B ∈;
) для любого A ∈выполнено A =Ω \ A ∈;
) Ω ∈.
Элементы совокупности назовем событиями. Ясно, для чего
нужны свойства? Разумеется, для того чтобы можно было корректно говорить об «одновременном» выполнении любых двух событий
(пересекать их), о выполнении «хотя бы одного» из любых двух событий (объединять их) и о «невыполнении» любого события (брать
отрицание). При этом, конечно, «хотя бы что-то должно произойти»,
т. е. Ω –– событие, и бывает «невозможное» событие ∅ = Ω. Впрочем,
как правило, –– это совокупность всех подмножеств пространства
элементарных событий, так что свойства заведомо выполнены.
Пусть, наконец, P –– это функция из в [0, 1] со свойствами  –– 
из параграфа .. Тогда назовем ее вероятностью или вероятностной
мерой, а тройку (Ω, , P) –– вероятностным пространством.
Нетрудно понять, что если Ω = {ω1, …, ωn} и P(ω1) = p1, …,
P(ωn) = pn, то каково бы ни было A ∈ , выполнено P(A) =
ωi∈A
pi,

причем, разумеется, p1 +…+ pn = P(Ω)=1. Имеем прямое обобщение
прежних ситуаций.

.. Условные вероятности и независимость событий

Пусть дано вероятностное пространство (Ω, , P). Для простоты
будем считать, что речь идет о классической модели. Представим себе, что некоторое событие B = {ωi1, …, ωik} ∈ уже произошло. Скажем, бросили мы игральную кость на стол и точно знаем, что она упала четной стороной кверху. Спрашивается: какова, при условии этого
дополнительного знания, вероятность события A ={ωj1, …, ωjl}∈?
Посмотрим сперва на наш пример с игральной костью. Если событие
A состоит в том, что число очков на кости равно , то при условии
указанного выше события B такое просто невозможно, и вероятность

A есть теперь не 1

6, а . Если же, допустим, A –– это событие, при
котором число очков есть полный квадрат натурального числа, то, поскольку среди чисел от единицы до шести таким свойством обладают

 и , обычная вероятность A есть 2

6 = 1

3; условную же вероятность
разумно полагать равной отношению числа полных квадратов среди