Iндекси складностi випадкових зростаючих графiв

Скорочена інформація про документ
dc.contributor.advisorНіщенко, Ірина Іванівна
dc.contributor.authorКалитюк, Дар’я Миколаївна
dc.date.accessioned2024-09-26T08:16:23Z
dc.date.available2024-09-26T08:16:23Z
dc.date.issued2024
dc.description.abstractВ роботi було розглянуто двi моделi випадкового дерева — модифiковану модель Ердеша-Реньї та рiвномiрне рекурсивне дерево. Для кожної моделi був запропонований власний iндекс складностi, знайдено його математичне сподiвання та вивчено асимптотичну поведiнку при зростаннi кiлькостi вершин дерева. Було продемонстровано залежнiсть iндексу складностi вiд ступеня розгалуженостi дерева, структури лiсу, з якого виростає дерево тощо. Також було знайдено нижню межу для iндексу складностi випадкового лiсу в довiльний момент часу. Для iндексу складностi рiвномiрного рекурсивного дерева було доведено iснування границi майже напевне при зростаннi кiлькостi вершин дерева до нескiнченностi.
dc.description.abstractotherTwo random tree models were considered in the study: a modified Erdos-Renyi model and the uniform recursive tree. For each model, we proposed its own complexity index, found its mathematical expectation and established its asymptotics as the number of vertices of the tree tends to infinity. The dependence of the complexity index on the degree of branching of the tree, the structure of the forest from which the tree grows was demonstrated. An lower bound was also found for the complexity index of a random forest at an arbitrary point in time. For the complexity index of a uniform recursive tree, we also proved the existence of a limit almost surely as the number of vertices of the tree tends to infinity.
dc.format.extent61 с.
dc.identifier.citationКалитюк, Д. М. Iндекси складностi випадкових зростаючих графiв : магістерська дис. : 113 Прикладна математика / Калитюк Дар’я Миколаївна. - Київ, 2024. - 61 с. .
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/69256
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectвипадкове дерево
dc.subjectрекурсивне випадкове дерево
dc.subjectiндекс вiнера
dc.subjectскладнiсть графаrandom tree
dc.subjectrecursive random tree
dc.subjectwiener index
dc.subjectgraph complexity
dc.subject.udc519.21
dc.titleIндекси складностi випадкових зростаючих графiв
dc.typeMaster Thesis

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Kalytiuk_magistr.pdf
Розмір:
763.15 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (ММЗІ)
Магістерські роботи