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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Равномерное распределение)
(Равномерное распределение)
Строка 27: Строка 27:
  
 
Так как граф характеризуется последовательностью степеней, её можно переформулировать следующим образом: найдём число [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> слагаемых. Данная задача имеет решение за полиноминальное время.
 
Так как граф характеризуется последовательностью степеней, её можно переформулировать следующим образом: найдём число [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>.
  
 
== Распределение максимальной степени вершин ==
 
== Распределение максимальной степени вершин ==

Версия 02:40, 16 июня 2021

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

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

Так как граф характеризуется последовательностью степеней, её можно переформулировать следующим образом: найдём число разбиений числа [math]2m[/math] на [math]1...n[/math] слагаемых. Данная задача имеет решение за полиноминальное время.

В таком разбиении получаемые слагаемые как раз являются получаемыми степенями вершин.

Математическое ожидание количества появлений слагаемого [math]k[/math] при разбиении [math]x[/math] на [math]n[/math] слагаемых можно вычислить, сложив количества его появлений во всех разбиениях, которые могут получиться при данных параметрах, и разделить на количество разбиений.

Количество появлений слагаемого [math]k[/math] соответствует частоте появления вершины степени [math]k[/math] в нашем случайном графе([math]\lambda[/math]). Посчитав [math]\lambda[/math] для всех степеней и нормировав её по общему количеству(сумме [math]\lambda[/math] по всем степеням), можем определить функцию распределения степеней [math]P(x)[/math].

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

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


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

Максимальная степень вершины равна [math]k[/math] тогда и только тогда, когда не существует вершины степенью больше [math]k[/math]. Таким образом, нужно посчитать вероятность события [math]A: \exists v: \; deg(v) = k \;\&\; !\exists v: \; 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=k+1}^{n} P(x)[/math]

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