RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2004, том 16, выпуск 3, страницы 63–75 (Mi dm163)

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

Предельные теоремы для объемов деревьев непомеченного графа случайного отображения

Ю. Л. Павлов


Аннотация: Получены предельные распределения максимального объема дерева и числа деревьев заданного объема в непомеченном случайном лесе, состоящем из $N$ корневых деревьев и $n$ некорневых вершин, при $N,n\to\infty$ так, что $0<C_1\le N/\sqrt{n}\le C_2<\infty$. С помощью этих результатов для непомеченного графа случайного однозначного отображения множества $\{1,2,\ldots,n\}$ в себя при $n\to\infty$ доказаны теоремы о предельном поведении максимального объема дерева и числа деревьев объема $r$ в случае фиксированного $r$ и $r/n^{1/3}\ge C_3>0$.
Работа выполнена при поддержке гранта НШ 1758.2003.1 Президента Российской Федерации государственной поддержки ведущих научных школ Российской Федерации.

УДК: 519.2

Статья поступила: 20.02.2004

DOI: 10.4213/dm163


 Англоязычная версия: Discrete Mathematics and Applications, 2004, 14:4, 329–342

Реферативные базы данных:


© МИАН, 2024