2. Теорема Эрдеша – Реньи о фазовом переходе

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

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

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

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