20
правок
Изменения
Нет описания правки
Распределение степеней <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>G(n, p)</tex> имеет биноминальное биномиальное распределение степеней вершин <tex>k</tex>:
<p>
<tex>
</tex>
</p>
Действительно, если вероятность появления ребра <tex>p</tex>, то вероятность появления ровно <tex>k</tex> рёбер у вершины равна <tex>p^k(1-p)^{n-1-k}</tex>. Таких наборов рёбер у одной вершины всего <tex>{n-1 \choose k}</tex>, откуда получаем искомое распределение.
