Изменения

Перейти к: навигация, поиск

Участник:Quarter

1867 байт добавлено, 16 июнь
Нет описания правки
== Распределение степеней вершин ==
{{Определение
|id=def_degree_dist
|definition='''Распределение степеней вершин случайного графа''' - это функция <tex>P(x)</tex>, определённая на <tex>\mathbb{R}</tex> как <tex>P(\xi=x)</tex>, то есть выражающая вероятность того, что вершина <tex>\xi</tex> в графе <tex>G(n, p)</tex> имеет степень <tex>x</tex>. Другими словами, распределение степеней <tex>P(k)</tex> графа определяется как доля узлов, имеющих степень <tex>k</tex>.
}}
{{Пример
|id=example_1
|example=Если есть в общей сложности <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>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>.Утверждение|about=Биномиальное распределение|statement=Случайный граф <tex>G(n, p)</tex> имеет биномиальное распределение степеней вершин <tex>k</tex>:
<p>
<tex>
</tex>
</p>
|proof=Действительно, если вероятность появления ребра <tex>p</tex>, то вероятность появления ровно <tex>k</tex> рёбер у вершины равна <tex>p^k(1-p)^{n-1-k}</tex>([[схема Бернулли]]). Таких наборов рёбер у одной вершины всего <tex>{n-1 \choose k}</tex>, откуда получаем искомое распределение.}} == Распределение максимальной степени вершин =={{Определение|id=def_max_degree_dist|definition='''Распределение максимальной степени вершин случайного графа''' - это функция <tex>Q(x)</tex>, определённая на <tex>\mathbb{R}</tex> как <tex>P(\xi=x)</tex>, то есть выражающая вероятность того, что максимальная степень вершины <tex>\xi</tex> равна <tex>x</tex>.}}{{Утверждение|statement=<tex>Q(k) = P(k) \cdot (1 - \sum_{x=k+1}^{n} P(x))</tex>|proof=Будем выводить формулу для <tex>Q(k)</tex> через распределение степеней вершин <tex>P(k)</tex>.
Максимальная степень вершины равна <tex>k</tex> тогда и только тогда, когда не существует вершины степенью больше <tex>k</tex>. Таким образом, нужно посчитать вероятность события <tex>A: \exists v\in G: \; deg(v) = k \;\&\; !\exists v\in G: \; deg(v) > x</tex>.
<tex>P(\exists v: \; deg(v) =k) = Распределение максимальной степени вершин ==P(k)</tex>
Максимальная степень вершины равна <tex>P(k)</tex> тогда и только тогда- вероятность того, когда не существует вершины степенью больше что вершина имеет степень <tex>k</tex>. Таким образомТогда вероятность того, нужно посчитать вероятность события что имеет одну из степеней <tex>1...k</tex> - <tex>A: \exists \; sum_{x=1}^{k}P(x)</tex>. Нам нужно обратное событие, при наступлении которого вершина \; степенью \; имеет степень больше <tex>k </tex>. Его вероятность равна <tex>1 - \;\&\; \forall sum_{x>=1}^{k \; !\exists \; вершины \; степенью \; }P(x)</tex>.
Получаем: <tex>QP(!\exists v: \; deg(v) > k) = P(k) \cdot 1 - \sum_{x=k+1}^{n} (1-P(x))</tex>
События независимы, поэтому получаем: <tex>Q(k) = P(n-k)P\cdot (k) 1 - P(k)\sum_{x=k+1}^{n} P(x))</tex>}}
20
правок

Навигация