20
правок
Изменения
→Равномерное распределение
Так как граф характеризуется последовательностью степеней, её можно переформулировать следующим образом: найдём число [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>.
== Распределение максимальной степени вершин ==
