Участник:Quarter — различия между версиями

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

Версия 20:31, 15 июня 2021

Распределение степеней вершин

Распределение степеней [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]P(k)[/math] равно вероятности того, что отдельно взятая вершина в [math]G(n, p)[/math] имеет степень [math]k[/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], откуда получаем искомое распределение.


Распределение максимальной степени вершин

Максимальная степень вершины равна [math]k[/math] тогда и только тогда, когда [math]P(k) \gt 0 \;\&\; \forall x\gt k \; P(x) = 0[/math]