3. Идея доказательства результата Эрдеша – Реньи

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

(q(n))^n?1.

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

n(q(n))^n?1.

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

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

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

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

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

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

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

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

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

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

Назад к Главе 4