В качестве дополнительного материала к этой главе рекомендуем книгу Андрея «Модели случайных графов». Там в подробностях приводится доказательство теоремы Эрдеша – Реньи и много других интересных результатов из теории случайных графов.

Рассмотрим мини-сеть как в примере, приведенном в главе: три компьютера – 1, 2, 3 и три канала связи: 1–2, 1–3, 2–3. Допустим, что канал связи доступен с вероятностью р и недоступен с вероятностью 1 − p, где 0 < p < 1. Предположим, что каналы независимы друг от друга. Связь между всеми тремя компьютерами сохраняется в двух случаях.

Случай 1. Все три канала связи доступны. Соответствующая вероятность равна

Вероятности перемножаются потому, что каналы независимы друг от друга. Допустим, у нас тысяча мини-сетей и p = 0,6. Тогда примерно в 600 из них будет доступен канал 1–2. Поскольку доступность канала 1–2 никак не влияет на канал 1–3, из нашей 1000 сетей оба канала 1–2 и 1–3 будут доступны в среднем 600 × 0,6 = 360 случаев. Чтобы вычислить среднее количество сетей, в которых доступны все три канала, надо взять долю 0,6 от 360, получаем 360 × 0,6 = 216. В результате вероятность доступности всех трех каналов равна

Случай 2. Два канала связи доступны и один недоступен. Недоступным может быть любой из трех каналов связи, поэтому случай 2 можно получить тремя разными способами. В результате соответствующая вероятность равна

Общая вероятность сохранения связи в сети теперь равна

(П.3) + (П.4) = p³ + 3p² (1 − p) = 3p² −2p³.

Потеря связи хотя бы с одним из компьютеров тоже происходит в двух случаях, которые мы назовем случай 3 и случай 4.

Случай 3. Два канала связи недоступны и один доступен. Заметьте, что этот случай совершенно аналогичен случаю 2, только р и (1 − p) поменялись местами. Соответствующая вероятность равна

3 (p − 1)² p. (П.5)

Случай 4. Все три канала связи недоступны. Этот случай опять же аналогичен случаю 1, если поменять местами р и (1 − p). Соответствующая вероятность равна

(1 − p)³. (П.6)

Вероятность, что хотя бы один компьютер окажется отрезанным от сети, равна

(П.5) + (П.6) = 3(1 − p)² − 2(1 − p)³. (П.7)

Естественно, если просуммировать все вероятности, то получится единица. Это очень красиво следует из бинома Ньютона третьей степени:

(П.3) + (П.4) + (П.5) + (П.6) = p³ + 3p² (1 − p) + 3(p − 1)² p + (1 − p)³ = (p + (1 − p))³ = 1³ = 1

Если провести еще немножко алгебраических манипуляций, то можно переписать вероятность (П.7) по-другому:

3(1 − p)² − 2(1 − p)³ = (1 − p)² (3 − 2(1 − p)) = (1 − p)² (1 + 2p) = (1 − p) ((1 − p) (1 + 2p)) = (1 − p) (1 + p − 2p²)

Легко проверить, что если p > ½, то вторая скобка меньше единицы. Получается, что если p > ½, то вероятность потери связи в мини-сети меньше, чем вероятность потери связи в отдельно взятом канале, которая равна (1 − p).

Кроме того, выражение (П.7) всегда меньше, чем 3 (1 − p)². Поэтому если вероятность неисправности канала (1 − p) уменьшается, то вероятность потери связи в сети уменьшается еще быстрее. Когда вероятность (1 − p) очень мала, то термином −2 (1 − p)³ можно пренебречь. Тогда вероятность потери связи в сети приблизительно равна 3 (1 − p)². Если (1 − p) = 0,01 (то есть 1 %), то эта формула верна до третьего знака после запятой, что мы и видим в последней строчке .

Теорема (Эрдеша – Реньи). Допустим, граф состоит из п вершин. Предположим, что ребра независимы друг от друга и любые две вершины соединены ребром с вероятностью р(п). Обозначим вероятность помехи через q(n) = 1 − p(n) и предположим, что

(i) Если c > 1, то вероятность связности стремится к единице при п, стремящемся к бесконечности, причем скорость стремления к единице тем выше, чем больше число с. Например, при c ≥ 3 скорость стремления к единице не ниже, чем у выражения 1 − 1/n, как в разделе в главе 4.

(ii) Если c < 1, то вероятность связности стремится к нулю при п, стремящемся к бесконечности, причем скорость стремления к нулю тем выше, чем меньше число с.

(iii) При c = 1 вероятность связности стремится не к нулю и не к единице, а к числу e⁻¹ ≈ 0,3679, где e = 2,71828… – основание натурального логарифма.

Допустим, граф состоит из n вершин. Предположим, что ребра независимы друг от друга и любые две вершины соединены ребром с вероятностью р(п). Обозначим вероятность помехи через q(n) = 1 − p(n). Рассмотрим одну вершину. Вероятность того, что она не соединена ребром ни с одной из оставшихся n − 1 вершин, равна

Поскольку всего вершин п, то в среднем число вершин, которые не соединены ребрами ни с одной другой вершиной, составит

Возьмем, как и прежде,

Вспомните один известный замечательный предел

где е – основание натурального логарифма. Интуитивно результат следует из похожего предельного перехода:

Давайте посмотрим, о чем нам говорит эта формула.

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

Если c > 1, то в среднем число вершин, у которых нет ни одного ребра, стремится к нулю. Значит, с большой вероятностью таких вершин не будет и связность сети сохранится.

Таким образом, мы видим, откуда появляется фазовый переход!

Наконец, если c = 1, то в среднем число вершин, у которых нет ни одного ребра, равно единице. Заметим, что единица – это среднее значение, а в реальности таких вершин может быть 0, 1, 2… Можно доказать, что соответствующее распределение вероятности близко к закону Пуассона с параметром 1:

Соответственно, вероятность того, что таких вершин не будет, то есть связность сети сохранится, равна е^–1.

Добавим, что это еще не строгое доказательство, потому что мы проанализировали только среднее количество вершин, у которых нет ни одного ребра. Для завершения доказательства нужно еще показать, что в случае c < 1 и c > 1 число вершин без ребер относительно мало отклоняется от среднего значения. Для этого разработаны стандартные методы, в частности, основанные на неравенствах Маркова и Чебышева. Эти неравенства названы в честь замечательных русских математиков, стоявших у истоков теории вероятностей.