Iндекси складностi випадкових зростаючих графiв
Вантажиться...
Дата
2024
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
В робот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.
Опис
Ключові слова
випадкове дерево, рекурсивне випадкове дерево, iндекс вiнера, складнiсть графаrandom tree, recursive random tree, wiener index, graph complexity
Бібліографічний опис
Калитюк, Д. М. Iндекси складностi випадкових зростаючих графiв : магістерська дис. : 113 Прикладна математика / Калитюк Дар’я Миколаївна. - Київ, 2024. - 61 с.
.