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

Дискрет. матем., 2007, том 19, выпуск 3, страницы 35–50 (Mi dm964)

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

Об условии возникновения гигантского дерева в случайном непомеченном лесе

Е. В. Хворостянская


Аннотация: Рассматривается множество случайных лесов, состоящих из $N$ корневых деревьев, упорядоченных одним из $N!$ возможных способов, и $n$ некорневых непомеченных вершин. При $N,n\to\infty$ найдены предельные распределения $(N-p)$-х членов вариационного ряда, полученного расположением объемов деревьев случайного непомеченного леса в неубывающем порядке, при фиксированных $p=1,2,\dots$. Установлено, что гигантское дерево (то есть дерево объема $n+o(n)$) возникает только в случае, когда $N,n\to\infty$ так, что $N/\sqrt n\to0$.
Работа выполнена при поддержке Российского Фонда фундаментальных исследований, проект 05-01-00007а, и программы Президента Российской Федерации поддержки ведущих научных школ, грант НШ 1758.2003.1.

УДК: 519.2

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

DOI: 10.4213/dm964


 Англоязычная версия: Discrete Mathematics and Applications, 2007, 17:5, 439–454

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


© МИАН, 2024