Изменения

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

Участник:Quarter

74 байта убрано, 01:51, 16 июня 2021
Равномерное распределение
== Равномерное распределение ==
Модель равномерного распределения подразумевает предположение о том, что все графы с <tex>m</tex> рёбрами равновероятны. Здесь имеем <tex>G(n, m)</tex> - граф на <tex>n</tex> вершинах с <tex>m</tex> рёбрами. Задача стоит уже по-другому - распределить <tex>m</tex> рёбер по <tex>{n \choose 2}</tex> местам с точностью до изоморфизма.  Её можно переформулировать следующим образом: найдём число разбиений мультимножества из <tex>m</tex> одинаковых чисел на <tex>n</tex> множеств, возможно пустых(или на не более <tex>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 задаче о нахождении количества разбиений на слагаемые].
Так как граф характеризуется последовательностью степеней, её можно переформулировать следующим образом: найдём число [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> слагаемых. Данная задача имеет решение за полиноминальное время.
== Распределение максимальной степени вершин ==
20
правок

Навигация