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

Дискрет. матем., 2004, том 16, выпуск 4, страницы 117–133 (Mi dm180)

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

Случайные свободные деревья и леса с ограничениями на кратности вершин

А. Н. Тимашёв


Аннотация: Рассматриваются свободные (некорневые) деревья с $n$ занумерованными вершинами, кратности которых принимают значения из некоторого фиксированного подмножества $A$ множества целых неотрицательных чисел такого, что $A$ содержит нуль, $A\ne\{0\}$, $A\ne\{0,1\}$ и наибольший общий делитель чисел $\{k\mid k\in A\}$ равен единице. Получена асимптотика числа всех таких деревьев при $n\to\infty$. В предположении, что на множестве этих деревьев задано равномерное распределение, для случайной величины $\mu_r^{(A)}$ ($r\in A$), равной числу вершин кратности $r$ в случайно выбранном дереве, найдены асимптотики математического ожидания и дисперсии при $n\to\infty$, а также доказаны локальная нормальная и пуассоновская теоремы для распределения вероятностей этой случайной величины. Для случая $A=\{0,1\}$ получены оценки чисел всех лесов с $n$ занумерованными вершинами, состоящих из $N$ свободных деревьев, при $n\to\infty$ и различных предположениях о функции $N=N(n)$. Найдена асимптотика числа всех лесов из свободных деревьев с $n$ вершинами, кратности которых не превосходят 1. Доказаны локальные нормальные и пуассоновские теоремы для числа деревьев заданного объема и общего числа деревьев в случайном лесе такого типа. Получены предельные теоремы, оценивающие распределение вероятностей случайной величины, равной объему дерева, содержащего вершину с фиксированным номером.

УДК: 519.2

Статья поступила: 10.07.2003
Переработанный вариант поступил: 24.09.2004

DOI: 10.4213/dm180


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

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


© МИАН, 2024