|
Эта публикация цитируется в 1 научной статье (всего в 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. Доказаны локальные нормальные и пуассоновские теоремы для числа деревьев заданного объема и общего числа деревьев в случайном лесе такого типа. Получены предельные теоремы, оценивающие распределение вероятностей случайной величины, равной объему дерева, содержащего вершину с фиксированным номером.
Статья поступила: 10.07.2003 Переработанный вариант поступил: 24.09.2004
Образец цитирования:
А. Н. Тимашёв, “Случайные свободные деревья и леса с ограничениями на кратности вершин”, Дискрет. матем., 16:4 (2004), 117–133; Discrete Math. Appl., 14:6 (2004), 603–618
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm180https://doi.org/10.4213/dm180 https://www.mathnet.ru/rus/dm/v16/i4/p117
|
Статистика просмотров: |
Страница аннотации: | 564 | PDF полного текста: | 231 | Список литературы: | 74 | Первая страница: | 1 |
|