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

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

Текущая версия на 00:48, 17 июня 2021

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

Определение:
Распределение степеней вершин случайного графа - это функция [math]P(x)[/math], определённая на [math]\mathbb{R}[/math] как [math]P(\xi=x)[/math], то есть выражающая вероятность того, что вершина [math]\xi[/math] имеет степень [math]x[/math]. Другими словами, распределение степеней [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]k[/math].


Утверждение:
Дан случайный граф [math]G(n, p)[/math] в биноминальной модели. Тогда для него распределение степеней вершин

[math] \begin{equation*} P(k) = {n-1 \choose k} p^k(1-p)^{n-1-k} \end{equation*} [/math]

[math]\triangleright[/math]
Действительно, если вероятность появления ребра [math]p[/math], то вероятность появления ровно [math]k[/math] рёбер у вершины равна [math]p^k(1-p)^{n-1-k}[/math](схема Бернулли). Таких наборов рёбер у одной вершины всего [math]{n-1 \choose k}[/math], откуда получаем искомое распределение.
[math]\triangleleft[/math]

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

Определение:
Распределение максимальной степени вершин случайного графа - это функция [math]Q(x)[/math], определённая на [math]\mathbb{R}[/math] как [math]P(\xi=x)[/math], то есть выражающая вероятность того, что максимальная степень вершины [math]\xi[/math] равна [math]x[/math].
Утверждение:
[math]Q(k) = P(k) \cdot (1 - \sum_{x=k+1}^{n} P(x))[/math]
[math]\triangleright[/math]

Будем выводить формулу для [math]Q(k)[/math] через распределение степеней вершин [math]P(k)[/math].

Максимальная степень вершины равна [math]k[/math] тогда и только тогда, когда не существует вершины степенью больше [math]k[/math]. Таким образом, нужно посчитать вероятность события [math]A: \exists v\in G: \; deg(v) = k \;\&\; !\exists v\in G: \; deg(v) \gt x[/math].

[math]P(\exists v: \; deg(v) = k) = P(k)[/math]

[math]P(k)[/math] - вероятность того, что вершина имеет степень [math]k[/math]. Тогда вероятность того, что имеет одну из степеней [math]1...k[/math] - [math]\sum_{x=1}^{k}P(x)[/math]. Нам нужно обратное событие, при наступлении которого вершина имеет степень больше [math]k[/math]. Его вероятность равна [math]1 - \sum_{x=1}^{k} P(x)[/math].

[math]P(!\exists v: \; deg(v) \gt k) = 1 - \sum_{x=1}^{k} P(x)[/math]

События независимы, поэтому получаем: [math]Q(k) = P(k) \cdot (1 - \sum_{x=1}^{k} P(x))[/math]
[math]\triangleleft[/math]