Участник:Quarter — различия между версиями
Quarter (обсуждение | вклад) |
Quarter (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 11: | Строка 11: | ||
</tex> | </tex> | ||
</p> | </p> | ||
− | Действительно, если вероятность появления ребра <tex>p</tex>, то вероятность появления ровно <tex>k</tex> рёбер у вершины равна <tex>p^k(1-p)^{n-1-k}</tex>. Таких наборов рёбер у одной вершины всего <tex>{n-1 \choose 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> | + | Максимальная степень вершины равна <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> |
Версия 21:57, 15 июня 2021
Распределение степеней вершин
Распределение степеней
графа определяется как доля узлов, имеющих степень . Таким образом, если есть в общей сложности узлов в графе и из них имеют степень , то . Другими словами, равно вероятности того, что отдельно взятая вершина в имеет степень .Случайный граф
имеет биномиальное распределение степеней вершин :
Действительно, если вероятность появления ребра
, то вероятность появления ровно рёбер у вершины равна (схема Бернулли). Таких наборов рёбер у одной вершины всего , откуда получаем искомое распределение.
Распределение максимальной степени вершин
Максимальная степень вершины равна
тогда и только тогда, когда не существует вершины степенью больше . Таким образом, нужно посчитать вероятность события .Получаем: