RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические вопросы криптографии // Архив

Матем. вопр. криптогр., 2011, том 2, выпуск 2, страницы 95–118 (Mi mvk33)

Эта публикация цитируется в 1 статье

Случайные отображения с неподвижными элементами

В. Н. Сачков

Академия криптографии Российской Федерации, Москва

Аннотация: Рассматриваются ориентированные графы случайных отображений $n$-элементного множества в себя, выбираемых случайно и равновероятно из множества всех отображений, имеющих неподвижную точку. Найдены точные и предельные (при $n\to\infty$) распределения числа вершин в дереве или лесе, которые содержат заданную вершину, и высоты заданной вершины при условии, что она принадлежит лесу. Найдены также точные и предельные распределения высоты заданной вершины в случайном корневом дереве или лесе с $n$ вершинами.

Ключевые слова: случайные отображения с неподвижными элементами, орграфы, корневые деревья, леса, высота заданной вершины, предельные распределения.

УДК: 519.212.2

Получено 22.IV.2010

DOI: 10.4213/mvk33



© МИАН, 2024