Участник:Quarter

Распределение степеней [math]P(k)[/math] графа определяется как доля узлов, имеющих степень [math]k[/math]. Таким образом, если есть в общей сложности [math]n[/math] узлов в графе и из них [math]n_k[/math] имеют степень [math]k[/math], то [math]P(k) = \frac{n_k}{n}[/math].

Случайный граф [math]G(n, p)[/math] имеет биномиальное распределение степеней вершин [math]k[/math]:

[math] \begin{equation*} P(k) = {n-1 \choose k} p^k(1-p)^{n-1-k} \end{equation*} [/math]

Действительно, если вероятность появления ребра [math]p[/math], то вероятность появления ровно [math]k[/math] рёбер у вершины равна [math]p^k(1-p)^{n-1-k}[/math]. Таких наборов рёбер у одной вершины всего [math]{n-1 \choose k}[/math], откуда получаем искомое распределение.