Асимптотична поведінка індексу складності зростаючих випадкових дерев
Запропоновано означення індексу складності зростаючого випадкового ациклічного графа. Цю величину можна розглядати як модифікацію індексу Вінера, який було введено в якості міри компактності молекули і який визначається як сума відстаней між усіма парами вершин графа. Так само як і індекс Вінера, за...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2024 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2024
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/202320 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Асимптотична поведінка індексу складності зростаючих випадкових дерев / А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко // Доповіді Національної академії наук України. — 2024. — № 3. — С. 3-10. — Бібліогр.: 11 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-202320 |
|---|---|
| record_format |
dspace |
| spelling |
Дороговцев, А.А. Калитюк, Д.М. Ніщенко, І.І. 2025-03-13T11:12:13Z 2024 Асимптотична поведінка індексу складності зростаючих випадкових дерев / А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко // Доповіді Національної академії наук України. — 2024. — № 3. — С. 3-10. — Бібліогр.: 11 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/202320 519.21 DOI: doi.org/10.15407/dopovidi2024.03.003 Запропоновано означення індексу складності зростаючого випадкового ациклічного графа. Цю величину можна розглядати як модифікацію індексу Вінера, який було введено в якості міри компактності молекули і який визначається як сума відстаней між усіма парами вершин графа. Так само як і індекс Вінера, запропонований у статті індекс складності характеризує форму графа, його розгалуженість, але, на відміну від індексу Вінера, його можна обчислити не лише для зв’язного графа, але й для випадкового лісу. Завдяки мультиплікативній властивості, яку має запропонована характеристика, вдалося оцінити знизу математичне сподівання індексу складності випадкового дерева, що отримується в результаті коалесценції випадкового лісу. Встановлено також асимптотичну поведінку не тільки математичного сподівання індексу складності, але й самого індексу складності рекурсивного рівномірного випадкового дерева. Запропонований підхід може бути використаний для обчислення складності широкого класу графів з марковською динамікою зростання. In the article a definition of the complexity index of a growing random acyclic graph is proposed. This value can be considered as a modification of the Wiener index, which was introduced as a measure of compactness of a molecular graph and is defined as the sum of distances between all pairs of vertices of the graph. Like the Wiener index, the proposed complexity index characterizes the shape or sparsity of a graph, but can be computed not only for a connected graph but also for a random forest. Its multiplicative property allowed us to estimate from below the mathematical expectation of the complexity index of the random tree resulting from the merging of random forests. For the recursive uniform random tree the asymptotic behaviour of both the mathematical expectation of the complexity index and the complexity index itself are established. The proposed measure of complexity can be applied to a wide class of random graphs with markovian growth dynamics. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Математика Асимптотична поведінка індексу складності зростаючих випадкових дерев Asymptotic behaviour of the complexity index of growing random trees Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Асимптотична поведінка індексу складності зростаючих випадкових дерев |
| spellingShingle |
Асимптотична поведінка індексу складності зростаючих випадкових дерев Дороговцев, А.А. Калитюк, Д.М. Ніщенко, І.І. Математика |
| title_short |
Асимптотична поведінка індексу складності зростаючих випадкових дерев |
| title_full |
Асимптотична поведінка індексу складності зростаючих випадкових дерев |
| title_fullStr |
Асимптотична поведінка індексу складності зростаючих випадкових дерев |
| title_full_unstemmed |
Асимптотична поведінка індексу складності зростаючих випадкових дерев |
| title_sort |
асимптотична поведінка індексу складності зростаючих випадкових дерев |
| author |
Дороговцев, А.А. Калитюк, Д.М. Ніщенко, І.І. |
| author_facet |
Дороговцев, А.А. Калитюк, Д.М. Ніщенко, І.І. |
| topic |
Математика |
| topic_facet |
Математика |
| publishDate |
2024 |
| language |
Ukrainian |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Asymptotic behaviour of the complexity index of growing random trees |
| description |
Запропоновано означення індексу складності зростаючого випадкового ациклічного графа. Цю величину можна розглядати як модифікацію індексу Вінера, який було введено в якості міри компактності молекули і який визначається як сума відстаней між усіма парами вершин графа. Так само як і індекс Вінера, запропонований у статті індекс складності характеризує форму графа, його розгалуженість, але, на відміну від індексу Вінера, його можна обчислити не лише для зв’язного графа, але й для випадкового лісу. Завдяки мультиплікативній властивості, яку має запропонована характеристика, вдалося оцінити знизу математичне сподівання індексу складності випадкового дерева, що отримується в результаті коалесценції випадкового лісу. Встановлено також асимптотичну поведінку не тільки математичного сподівання індексу складності, але й самого індексу складності рекурсивного рівномірного випадкового дерева. Запропонований підхід може бути використаний для обчислення складності широкого класу графів з марковською динамікою зростання.
In the article a definition of the complexity index of a growing random acyclic graph is proposed. This value can be considered as a modification of the Wiener index, which was introduced as a measure of compactness of a molecular graph and is defined as the sum of distances between all pairs of vertices of the graph. Like the Wiener index, the proposed complexity index characterizes the shape or sparsity of a graph, but can be computed not only for a connected graph but also for a random forest. Its multiplicative property allowed us to estimate from below the mathematical expectation of the complexity index of the random tree resulting from the merging of random forests. For the recursive uniform random tree the asymptotic behaviour of both the mathematical expectation of the complexity index and the complexity index itself are established. The proposed measure of complexity can be applied to a wide class of random graphs with markovian growth dynamics.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/202320 |
| citation_txt |
Асимптотична поведінка індексу складності зростаючих випадкових дерев / А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко // Доповіді Національної академії наук України. — 2024. — № 3. — С. 3-10. — Бібліогр.: 11 назв. — укр. |
| work_keys_str_mv |
AT dorogovcevaa asimptotičnapovedínkaíndeksuskladnostízrostaûčihvipadkovihderev AT kalitûkdm asimptotičnapovedínkaíndeksuskladnostízrostaûčihvipadkovihderev AT níŝenkoíí asimptotičnapovedínkaíndeksuskladnostízrostaûčihvipadkovihderev AT dorogovcevaa asymptoticbehaviourofthecomplexityindexofgrowingrandomtrees AT kalitûkdm asymptoticbehaviourofthecomplexityindexofgrowingrandomtrees AT níŝenkoíí asymptoticbehaviourofthecomplexityindexofgrowingrandomtrees |
| first_indexed |
2025-11-30T16:43:58Z |
| last_indexed |
2025-11-30T16:43:58Z |
| _version_ |
1850858165372977152 |