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>P(k)</tex> равно вероятности того, что отдельно взятая вершина в <tex>G(n, p)</tex> имеет степень <tex>k</tex>.
Случайный граф <tex>G(n, p)</tex> имеет биномиальное распределение степеней вершин <tex>k</tex>:
</p>
Действительно, если вероятность появления ребра <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>P(k) > 0 \;\&\; \forall x>k \; P(x) = 0</tex>
