Изменения

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

Участник:Quarter

2350 байт убрано, 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>.
}}
 
Другими словами, распределение степеней <tex>P(k)</tex> графа определяется как доля узлов, имеющих степень <tex>k</tex>.
 
{{Пример
|id=example_1
}}
{{Утверждение|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>, откуда получаем искомое распределение. == Равномерное распределение ==Модель равномерного распределения подразумевает предположение о том, что все графы с <tex>m</tex> рёбрами равновероятны. Здесь имеем <tex>G(n, m)</tex> - граф на <tex>n</tex> вершинах с <tex>m</tex> рёбрами. Задача стоит уже по-другому - распределить <tex>m</tex> рёбер по <tex>{n \choose 2}</tex> местам с точностью до изоморфизма. Так как граф характеризуется последовательностью степеней, её можно переформулировать следующим образом: найдём число [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D1%85%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D1%80%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B9_%D1%87%D0%B8%D1%81%D0%BB%D0%B0_%D0%BD%D0%B0_%D1%81%D0%BB%D0%B0%D0%B3%D0%B0%D0%B5%D0%BC%D1%8B%D0%B5 разбиений числа] <tex>2m</tex> на <tex>1...n</tex> слагаемых. Данная задача имеет решение за полиноминальное время. В таком разбиении получаемые слагаемые как раз являются получаемыми степенями вершин.  Математическое ожидание количества появлений слагаемого <tex>k</tex> при разбиении <tex>x</tex> на <tex>n</tex> слагаемых можно вычислить, сложив количества его появлений во всех разбиениях, которые могут получиться при данных параметрах, и разделить на количество разбиений. Количество появлений слагаемого <tex>k</tex> соответствует частоте появления вершины степени <tex>k</tex> в нашем случайном графе(<tex>\lambda</tex>). Посчитав <tex>\lambda</tex> для всех степеней и нормировав её по общему количеству(сумме <tex>\lambda</tex> по всем степеням), можем определить функцию распределения степеней <tex>P(x)</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>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>Q(k) = P(k) \cdot (1 - \sum_{x=k+1}^{n} P(x))</tex>
}}
20
правок

Навигация