Асимптотична поведінка індексу складності зростаючих випадкових дерев

• Дата: 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 назв. — укр.

Запропоновано означення індексу складності зростаючого випадкового ациклічного графа. Цю величину можна розглядати як модифікацію індексу Вінера, який було введено в якості міри компактності молекули і який визначається як сума відстаней між усіма парами вершин графа. Так само як і індекс Вінера, запропонований у статті індекс складності характеризує форму графа, його розгалуженість, але, на відміну від індексу Вінера, його можна обчислити не лише для зв’язного графа, але й для випадкового лісу. Завдяки мультиплікативній властивості, яку має запропонована характеристика, вдалося оцінити знизу математичне сподівання індексу складності випадкового дерева, що отримується в результаті коалесценції випадкового лісу. Встановлено також асимптотичну поведінку не тільки математичного сподівання індексу складності, але й самого індексу складності рекурсивного рівномірного випадкового дерева. Запропонований підхід може бути використаний для обчислення складності широкого класу графів з марковською динамікою зростання.