Изменения

== Распределение степеней вершин == Распределение степеней <tex>P(k)</tex> графа определяется как доля узлов, имеющих степень <tex>k</tex>. Таким образом, если есть в общей сложности <tex>n</tex> узлов в графе и из них <tex>n_k</tex> имеют степень <tex>k</tex>, то <tex>P(k) = \frac{n_k}{n}</tex>. Другими словами, <tex>P(k)</tex> равно вероятности того, что отдельно взятая вершина в <tex>G(n, p)</tex> имеет степень <tex>k</tex>.

Действительно, если вероятность появления ребра <tex>p</tex>, то вероятность появления ровно <tex>k</tex> рёбер у вершины равна <tex>p^k(1-p)^{n-1-k}</tex>(схема Бернулли). Таких наборов рёбер у одной вершины всего <tex>{n-1 \choose k}</tex>, откуда получаем искомое распределение.  == Распределение максимальной степени вершин == Максимальная степень вершины равна <tex>k</tex> тогда и только тогда, когда не существует вершины степенью больше <tex>k</tex>. Таким образом, нужно посчитать вероятность события <tex>A: \exists \; вершина \; степенью \; k \;\&\; \forall x>k \; !\exists \; вершины \; степенью \; x</tex>. Получаем: <tex>Q(k) = P(k) \cdot \sum_{x=k+1}^{n} (1-P(x))</tex> <tex>Q(k) = (n-k)P(k) - P(k)\sum_{x=k+1}^{n} P(x)</tex>