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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2024
Hauptverfasser:	Дороговцев, А.А., Калитюк, Д.М., Ніщенко, І.І.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Видавничий дім "Академперіодика" НАН України 2024
Schriftenreihe:	Доповіді НАН України
Schlagworte:	Математика
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/202320
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Асимптотична поведінка індексу складності зростаючих випадкових дерев / А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко // Доповіді Національної академії наук України. — 2024. — № 3. — С. 3-10. — Бібліогр.: 11 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-202320
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-2023202025-03-17T01:09:30Z Асимптотична поведінка індексу складності зростаючих випадкових дерев Asymptotic behaviour of the complexity index of growing random trees Дороговцев, А.А. Калитюк, Д.М. Ніщенко, І.І. Математика Запропоновано означення індексу складності зростаючого випадкового ациклічного графа. Цю величину можна розглядати як модифікацію індексу Вінера, який було введено в якості міри компактності молекули і який визначається як сума відстаней між усіма парами вершин графа. Так само як і індекс Вінера, запропонований у статті індекс складності характеризує форму графа, його розгалуженість, але, на відміну від індексу Вінера, його можна обчислити не лише для зв’язного графа, але й для випадкового лісу. Завдяки мультиплікативній властивості, яку має запропонована характеристика, вдалося оцінити знизу математичне сподівання індексу складності випадкового дерева, що отримується в результаті коалесценції випадкового лісу. Встановлено також асимптотичну поведінку не тільки математичного сподівання індексу складності, але й самого індексу складності рекурсивного рівномірного випадкового дерева. Запропонований підхід може бути використаний для обчислення складності широкого класу графів з марковською динамікою зростання. 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. 2024 Article Асимптотична поведінка індексу складності зростаючих випадкових дерев / А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко // Доповіді Національної академії наук України. — 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 uk Доповіді НАН України application/pdf Видавничий дім "Академперіодика" НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Математика Математика
spellingShingle	Математика Математика Дороговцев, А.А. Калитюк, Д.М. Ніщенко, І.І. Асимптотична поведінка індексу складності зростаючих випадкових дерев Доповіді НАН України
description	Запропоновано означення індексу складності зростаючого випадкового ациклічного графа. Цю величину можна розглядати як модифікацію індексу Вінера, який було введено в якості міри компактності молекули і який визначається як сума відстаней між усіма парами вершин графа. Так само як і індекс Вінера, запропонований у статті індекс складності характеризує форму графа, його розгалуженість, але, на відміну від індексу Вінера, його можна обчислити не лише для зв’язного графа, але й для випадкового лісу. Завдяки мультиплікативній властивості, яку має запропонована характеристика, вдалося оцінити знизу математичне сподівання індексу складності випадкового дерева, що отримується в результаті коалесценції випадкового лісу. Встановлено також асимптотичну поведінку не тільки математичного сподівання індексу складності, але й самого індексу складності рекурсивного рівномірного випадкового дерева. Запропонований підхід може бути використаний для обчислення складності широкого класу графів з марковською динамікою зростання.
format	Article
author	Дороговцев, А.А. Калитюк, Д.М. Ніщенко, І.І.
author_facet	Дороговцев, А.А. Калитюк, Д.М. Ніщенко, І.І.
author_sort	Дороговцев, А.А.
title	Асимптотична поведінка індексу складності зростаючих випадкових дерев
title_short	Асимптотична поведінка індексу складності зростаючих випадкових дерев
title_full	Асимптотична поведінка індексу складності зростаючих випадкових дерев
title_fullStr	Асимптотична поведінка індексу складності зростаючих випадкових дерев
title_full_unstemmed	Асимптотична поведінка індексу складності зростаючих випадкових дерев
title_sort	асимптотична поведінка індексу складності зростаючих випадкових дерев
publisher	Видавничий дім "Академперіодика" НАН України
publishDate	2024
topic_facet	Математика
url	https://nasplib.isofts.kiev.ua/handle/123456789/202320
citation_txt	Асимптотична поведінка індексу складності зростаючих випадкових дерев / А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко // Доповіді Національної академії наук України. — 2024. — № 3. — С. 3-10. — Бібліогр.: 11 назв. — укр.
series	Доповіді НАН України
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_	1850234415233368064
fulltext	3 ОПОВІДІ НАЦІОНАЛЬНОЇ АКАДЕМІЇ НАУК УКРАЇНИ МАТЕМАТИКА MATHEMATICS ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2024. № 3: 3—10 Ц и т у в а н н я: Дороговцев А.А., Калитюк Д.М., Ніщенко І.І. Асимптотична поведінка індексу складності зроста- ючих випадкових дерев. Допов. Нац. акад. наук Укр. 2024. № 3. С. 3—10. https://doi.org/10.15407/dopovidi2024.03.003 © Видавець ВД «Академперіодика» НАН України, 2024. Стаття опублікована за умовами відкритого доступу за ліцензією CC BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/) https://doi.org/10.15407/dopovidi2024.03.003 УДК 519.21 А.А. Дороговцев 1, https://orcid.org/0000-0003-0385-7897 Д.М. Калитюк 2 І.І. Ніщенко 2, https://orcid.org/0000-0001-7373-2286 1 Інститут математики НАН України, Київ, Україна 2 Національний технічний університет України “Київський політехнічний інститут ім. Ігоря Сікорського”, Київ, Україна E-mail: adoro@imath.kiev.ua, darkal-ipt22@lll.kpi.ua, nishchenkoii-ipt@lll.kpi.ua Асимптотична поведінка індексу складності зростаючих випадкових дерев Представлено членом-кореспондентом НАН України М.І. Портенком Запропоновано означення індексу складності зростаючого випадкового ациклічного графа. Цю величину можна розглядати як модифікацію індексу Вінера, який було введено в якості міри компактності молекули і який визначається як сума відстаней між усіма парами вершин графа. Так само як і індекс Вінера, запро- понований у статті індекс складності характеризує форму графа, його розгалуженість, але, на відміну від індексу Вінера, його можна обчислити не лише для зв’язного графа, але й для випадкового лісу. Завдяки мультиплікативній властивості, яку має запропонована характеристика, вдалося оцінити знизу мате- матичне сподівання індексу складності випадкового дерева, що отримується в результаті коалесценції випадкового лісу. Встановлено також асимптотичну поведінку не тільки математичного сподівання індексу складності, але й самого індексу складності рекурсивного рівномірного випадкового дерева. Запро- понований підхід може бути використаний для обчислення складності широкого класу графів з марковсь- кою динамікою зростання. Ключові слова: випадкове дерево, рекурсивне випадкове дерево, індекс Вінера, складність графа. Вступ. Для того, щоб кількісно описати складність структур, які можуть бути змодельовані графами, необхідно розвинути поняття міри складності самого графа. Прикладом струк- тури, опис і вивчення якої природним чином опирається на поняття графа, є молекула: її атоми інтерпретують як вершини графа, а зв’язки між атомами — як його ребра. Намага- ючись задати міру компактності молекули гідрокарбону, Г.Вінер у 1947 р. ввів у розгляд [1] величину, яка дорівнює сумі відстаней між усіма невпорядкованими парами вершин графа, що задає структуру молекули. Як зазначено в роботі [2], запропонована Вінером 4 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2024. No. 3 А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко величина корелює з такими хіміко-фізичними характеристиками органічних речовин як теплота утворення, точка кипіння, критичний тиск тощо. Згодом з’явилося чимало інших топологічних індексів графів, які отримали назву індексів вінерового типу, оскільки так чи інакше були пов’язані з величиною, запропонованою Г. Вінером. Методи обчислення таких індексів, встановлення взаємозв’язків між ними та виявлення зв’язків з іншими характе- ристиками графа розглянуті в роботах [2—4]. Для випадкового графа граничний розподіл індексу Вінера та асимптотична поведін- ка його математичного сподівання залежать від способу побудови графа. В роботі [5] ви- вчаються властивості індексу Вінера для випадкових рекурсивних дерев [6], а в роботі [7] розглядається аналог індексу Вінера для неперервних випадкових дерев, конструкцію яких було запропоновано у [8]. Мета. В цій статті ми пропонуємо в якості індексу складності випадкового дерева T розглядати величину – ( . ) ( , ) E ) d u v u v (T e  , де ( , )d u v — відстань між вершинами u, v , а під- сумовування ведеться за всіма впорядкованими парами вершин дерева. Таке означення дозволяє розглянути також складність лісу — незв’язного графа без циклів, поклавши ( , )d u v   для вершин, які належать до різних компонент зв’язності. Своєю чергою це дало нам можливість дослідити зміну складності випадкового лісу при випадковому до- даванні до нього ребра, що пов’язує дві різні компоненти зв’язності і таким чином пере- творює їх на одну. Крім цього ми встановили асимптотичні властивості запропонованого індексу складності для зростаючих рекурсивних дерев. Означення індексу складності. Нехай Tn ( , )T V E є деревом — зв’язним ациклічним графом на множині вершин V і множиною ребер E , де \| \| 3, \| \| 1V n E n   . Означення 1. Індексом складності дерева Tn назвемо величину – ( . ) ( , ) E( ) d u v n u v V V T e     , (1) де ( , )d u v — кількість ребер в єдиному шляху, що сполучає вершини ,u v у дереві. Зауважимо, що суму в правій частині (1) можна записати у вигляді ( ) – ( . ) – ( , ) 0 ( ) ndiam T d u v i n u v V V i e e K i       , (2) де ( )ndiam T — діаметр дерева, тобто кількість ребер у найдовшому шляху дерева Tn, а ( )nK i — кількість впорядкованих пар вершин дерева Tn, відстань між якими дорівнює i . Рівність (2) дозволяє легко обчислити складність дерева-ланцюжка Сn діаметр якого до- рівнює 1n , та складність дерева-зірки nS , діаметр якого дорівнює 2, а саме: – – 2 1 –1 –2 1 2E( ) 2 ( ) (1 ), 1 ( 1) E( ) 2 ( 1) ( 1)( 2). n i n n i n e eC n n i e n e e e S n e n e n n                     (3) Наступна теорема демонструє, що індекс складності дерева, як і індекс Вінера, є харак- теристикою форми дерева, його розгалуженості. 5ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2024. № 3 Асимптотична поведінка індексу складності зростаючих випадкових дерев Теорема 1. Для довільного дерева Tn E( ) E( ) E( )n n nC T S  . (4) Теорема доводиться методом математичної індукції за кількістю вершин n у дереві. Нехай тепер 1\| \| \| \|( , , ) kV VF T T  — ліс на множині V , тобто незв’язний ациклічний граф, компоненти зв’язності 1\| \| \| \|, , kV VT T якого є деревами на неперетинних множинах вершин 1, , kV V таких, що 1 k i i V V   . Означимо індекс складності лісу за формулою (1), вважаючи, що ( . )d u v   для вер- шин ,u v , які належать різним компонентам зв’язності лісу. З такого означення випли- ває, що індекс складності лісу 1\| \| \| \|( , , ) kV VF T T  дорівнює сумі індексів складності дерев 1\| \| \| \|, , kV VT T , які є його компонентами зв’язності. Далі ми будемо цікавитися асимптотичною поведінкою індексу складності випадко- вого дерева. Ми розглянемо дві моделі випадкових дерев, що відрізняються способом по- будови, а саме — модель зростаючого випадкового лісу та модель рекурсивного випадко- вого дерева. Модель зростаючого випадкового лісу. Розглянемо наступний алгоритм побудови дерева на множині вершин {1, 2, , }V n  . Нехай E — множина всеможливих ребер на множині 2, \| \| nV E C . Означимо (0) \| \| ( , )VF F V  як початковий тривіальний ліс без ребер. Якщо ( ) \| \| ( , )k kVF F V E — випадковий ліс на V з множиною ребер E , \| \|k kÅ E k , то для побу- дови ( 1) \| \| k VF  навмання рівноймовірно обирається ребро з множини E 1 \k kÅ E E   тих ребер з множини \ kE E , додавання яких до ( ) \| \| k VF не призводить до утворення циклу. Зрозуміло, що ліс ( ) \| \| k VF має n k компонент зв’язності, а ( 1) \| \| n VF  вже є деревом. Зауважимо також, що якщо 1 ( ) \| \| \| \|\| \| ( , , ) n k k V VVF T T    , то потужність множини E 1kÅ  , з якої обирається ребро для побудови ( 1) \| \| ,k VF  дорівнює 1 \| \| \| \|i j i j n k V V      . Описаний алгоритм побудови випадкового дерева ( 1) \| \| n n VT F  є однією з різноманітних модифікацій узагальненої моделі Ердеша—Реньї випадкового графа. Дослідженню випад- кових дерев такого типу присвячені роботи [9—11]. Виявляється, що в такій моделі неперетинні підмножини випадкового лісу є неза- лежними. Щоб сформулювати відповідне твердження, введемо деякі позначення. Нехай 1\| \| \| \| \| \|( , , ) kV V VF T T  — ліс на множині 1 k i i V V   і нехай {1, 2, , }I k  — деяка множина ін- дексів. Сукупність дерев \| \|( ) iV i IT  назвемо підлісом лісу \| \|VF на множині i i I U V   і позна- чимо \| \|( ),m VSF U де (\| \| 1)i i I m V    — кількість ребер в підлісі. Теорема 2. Нехай 1 ( ) \| \| \| \| \| \|( , , ) n k k V V VF T T    — випадковий ліс з k ребрами, що з’явився на k -му кроці побудови дерева ( 1) \| \| n VF  на множині V . Тоді умовний розподіл пари неперетин- них підлісів – \| \| \| \|( ( ), ( \ ))m k m V VSF U SF V U за умови, що ( ) – \| \| \| \|\| \| ( ( ), ( \ )),k m k m V VVF SF U SF V U збігається 6 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2024. No. 3 А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко з розподілом пари ( ) ( ) \| \| \| \ \|( , )m k m U V UF F  незалежних лісів ( ) \| \| m UF та ( – ) \| \ \| :k m V UF ( ) –– \| \| 1 \| \| 2 \| \| \| \| \| \|( ( ) , ( \ ) \| ( ( ), ( \ )))k m k mm k m V V V V VP SF U D SF V U D F SF U SF V U    ( ) ( ) 1 2\| \| \| \ \|( ) ( ),m k m U V UP F D P F D    де 1D — довільний заданий ліс з m ребрами на множині ,U 2D — довільний заданий ліс з k m ребрами на множині \ .V U Наступна теорема задає оцінку знизу для математичного сподівання ( ) [E( )]n nH T M T індексу складності випадкового фінального дерева ( –1) \| \| n n VT F . Теорема 3. 2 2 –1lim 1 ( ) 1 2 2 12n b bH T e a n n             , (5) де числа 1 1 ea e    та 2 2 ( 1) eb e   є константами, що входять у вираз –E( ) (1 )n nC n a b e    для індексу складності дерева-ланцюжка. Для доведення теореми зауважимо, що якщо (1) ( ) , \| \| \| \|{ , , }k n k V VF F   — сигма-алгебра, породжена випадковими лісами, побудованими за k кроків, і 1 – ( ) \| \| \| \|\| \| ( , , ) n k k V VVF T T  , то для умовного математичного сподівання можемо записати j –1 ( )( 1) \| \| , \| \| \| \|\| \| 11 2(E( ) ) E( ) E( )E( ) \| \| i kk V n k V VV ki j n k eM F F T T E        \|    . Згідно з теоремою 1 індекс складності будь-якого дерева не перевищує індекс склад- ності дерева-ланцюжка на тій самій множині вершин, а отже               –\| \| \| \| \| \| 2 2 1 2 1 2E( ) E( ) \| \| (1 ) \| \| \| \| 1 1( 1) ( 1) i i i V V V i i i e e e eT C V e V V a b e ee e   . Враховуючи, що 1 1 \| \| \| \| \| \|k i j i j n k E V V       і що 1 \| \| \| \| n k i i V V n     для довільного 0, 1k n  , отримуємо оцінку 2 2 1 \| \|k n k nE C n k         . Тоді j 2\| \| \| \| 2 2 2 11 E( )E( ) ( ) 2( ) \| \| iV V ki j n k T T k ka b a b b b E n n            , 7ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2024. № 3 Асимптотична поведінка індексу складності зростаючих випадкових дерев а отже для безумовного математичного сподівання ( 1) ( 1) \| \| \| \|( ) (E( ))k k V VH F M F  отримуємо нерівність 2 ( 1) ( ) –1 2 2 \| \| \| \| 2( ) ( ) 2 ( ) 2( )k k V V k kH F H F e a b a b b b n n                 , з якої випливає, що 2 ( 1) (0) –1 2 2 \| \| \| \| 2 1 1 2( )( ) ( ) 2 ( 1)( ) k k k V V j j a b b bH F H F e k a b j j n n                  . Поклавши в останній нерівності 2k n  і прийнявши до уваги, що (0) \| \|( )VH F n , отри- муємо оцінку для математичного сподівання індексу складності дерева nT –1 2 2 2 ( 2)( 1) ( 2)( 1)(2 3)( ) 2 ( 1)( ) ( ) 6n n n n n nH T n e n a b a b b b n n                  , з якої випливає твердження теореми. Модель рекурсивного випадкового дерева. Рекурсивне випадкове дерево nT на мно- жині з n точок будується наступним чином [6]. Дерево 1T складається з однієї вершини з номером 1, яка називається коренем дерева. Рівномірне рекурсивне дерево 1nT  утворю- ється з дерева nT додаванням до нього вершини з номером 1n , яка з’єднується з однією з вершин 1, , n з ймовірністю 1 n . Властивості індексу Вінера для рекурсивних дерев ви- вчались, зокрема, в роботі [5]. Означимо індекс складності рекурсивного дерева nT так: – ( , 1) 1 E( ) n d i n i T e   , (6) де ( ,1)d i — відстань від вершини з номером i до кореня дерева. Має місце наступне твердження про асимптотику математичного сподівання ( ) (E( ))n nH T M T індексу складності. Теорема 4. –1 ( ) lim ( ) n en H T e en   . (7) Доведення теореми ґрунтується на зауваженні того, що суму в правій частині (6) мож- на подати у вигляді – ( , 1) – 1 0 ( ) n d i r n i r e e k r       , де ( )nk r — кількість вершин у дереві nT , від- стань від яких до кореня дорівнює r , і ( ) 0nk r  при r n . Для випадкової величини ( )nk r можемо записати таку рекурентну формулу: 1 1( ) ( ) ( ( 1))n n nk r k r A r   1 , (8) 8 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2024. No. 3 А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко де подія 1( 1)nA r  означає, що ( 1)n -ша вершина приєдналася ребром до однієї з вершин дерева nT , відстань від якої до кореня дорівнює 1r  . Для умовних математичних споді- вань відносно  -алгебри 1( , , )n nT T   , тоді можемо записати: 1 1( ( ) \| ) ( ) ( 1)n n n nM k r k r k r n     , і тоді –1 –1 1(E( ) \| ) E( ) E( ) 1 E( )n n n n n e eM T T T T n n             . (9) З останньої рівності випливає, що –1 1( ) 1 ( )n n eH T H T n         . Враховуючи, що 1( ) 1H T  , отримуємо –1 1 1 ( ) 1 n n k eH T k           . Асимптотика добутку –1 1 1 n k e k         при n визначає асимптотику математичного сподівання в (7). На завершення наведемо теорему про асимптотику самого індексу складності випад- кового рекурсивного дерева. Теорема 5. Існує випадкова величина X така, що E( )n e T X n  м. н. і 2 E( ) ,Ln e T X n n   , причому –1( ) ( ) eM X e   . Зауважимо, що з рівності (9) випливає, що послідовність –1 1 1 1 E( ) 1 n n k n eT k              утворює мартингал. Переконавшись, що для довільного 1n 21 1 1 E( ) 1 2 n n k eM T k                , за теоремою про збіжність квадратично обмеженого мартингала робимо висновок про іс- нування границі майже напевне та в середньому квадратичному послідовності випадко- вих величин 1 1 1 1 E( ) 1 n n k n eT k                . Зауваживши, що –1 –1 –1 1 (1 ) ( )1 ! n k e e n e k n               9ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2024. № 3 Асимптотична поведінка індексу складності зростаючих випадкових дерев і що за формулою Ейлера !(0,1] ( ) lim (1 ) ( )n n n n              , отримуємо таку асимптотику при n нормуючого множника –1 1 1 : n k e k         –1 1 1 1 ~ , ( ) n e k e en n k e           . ЦИТОВАНА ЛІТЕРАТУРА 1. Wiener H. Structural determination of paraffin boiling points. J. of the Amer. Chem. Society. 1947. 69, № 1. P. 17—20. 2. Diudea M.V., Gutman I. Wiener-type topological indeces. Croatica Chem. Acta. 1998. 71, № 1. P. 21—51. 3. Dobrynin A.A., Entringer R., Gutman I. Wiener index of trees: theory and application. Acta Appl.Math. 2001. 66. P. 211—249. https://doi.org/10.1023/A:1010767517079 4. Rada J. Variation of the Wiener index under tree transformation. Discrete Appl. Math. 2005. 148, Iss. 2. P. 135—146. https://doi.org/101016/j.dam2004.07.008 5. Neininger R. The Wiener index of random trees. Combinatorics, Probability and Computing. 2002. 11, № 6. P. 587—597. 6. Smythe R., Mahmoud H. A survey of recursive trees. Theory Probab. Math. Statist. 1995. 51. P. 1—27. 7. Janson S. The Wiener index of simply generated random trees. Random structures and algorithms. 2003. 22, № 4. P. 337—358. https://doi.org/10.1002/rsa.10074 8. Aldous D. The continuum random tree I. The Annals of Probability. 1991. 19, Iss. 1. P. 1—28. https://doi. org/10.1214/aop/1176990534 9. Pitman J. Coalescent Random Forests. J. Combinatorial Theory. 1999. A85. P. 165—193. https://doi.org/10.1006/ jcta.1998.2919 10. Aldous D.J. A random tree model associated with random graphs. Random Structures and Algorithms. 1990. 1, Iss. 4. P. 383—402. https://doi.org/10.1002/rsa.324001042 11. Buffet E., Pulé J.V. Polymers and random graphs. J.Statist. Phys. 1991. 64. P. 87—110. https://doi.org/10.1007/ BF01057869 Надійшло до редакції 18.03.2024 REFERENCES 1. Wiener, H. (1947). Structural determination of paraffin boiling points. J. the Amer. Chem. Society, 69, No. 1, pp.17-20. 2. Diudea, M. V. & Gutman, I. (1998). Wiener-type topological indeces. Croatica Chem. Acta, 71, № 1, pp. 21-51. 3. Dobrynin, A. A., Entringer, R. & Gutman, I. (2001). Wiener index of trees: theory and application. Acta Appl. Math., 66, pp. 211-249. https://doi.org/10.1023/A:1010767517079 4. Rada, J. (2005). Variation of the Wiener index under tree transformation. Discrete Appl. Math., 148, pp. 135- 146. https://doi.org/101016/j.dam2004.07.008 5. Neininger, R. (2002). The Wiener index of random trees. Combinatorics, Probability and Computing, 11, No. 6, pp. 587-597. 6. Smythe, R. & Mahmoud, H. (1995). A survey of recursive trees. Theory Probab. Math. Statist., 51, pp. 1-27. 7. Janson, S. (2003). The Wiener index of simply generated random trees. Random structures and algorithms., 22, Iss. 4, pp. 337-358. https://doi.org/10.1002/rsa.10074 8. Aldous, D. (1991). The continuum random tree I. The Annals of Probability, 19, Iss. 1, pp. 1-28. https://doi. org/10.1214/aop/1176990534 10 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2024. No. 3 А.А. Дороговцев, Д.М. Калитюк, І.І. Ніщенко 9. Pitman, J. (1999). Coalescent Random Forests. J. Combinatorial Theory, A85, pp. 165-193. https://doi. org/10.1006/jcta.1998.2919 10. Aldous, D. J. (1990). A random tree model associated with random graphs. Random Structures and Algorithms, 1, Iss. 4, p. 383-402. https://doi.org/10.1002/rsa.324001042 11. Buffet, E. & Pulé, J. V. (1991). Polymers and random graphs. J. Statist. Phys., 64, pp. 87-110. https://doi. org/10.1007/BF01057869 Received 18.03.2024 A.А. Dorogovtsev 1, https://orcid.org/0000-0003-0385-7897 D.М. Кalytiuk 2 І.І. Nishchenko 2, https://orcid.org/0000-0001-7373-2286 1 Institute of Mathematics of the NAS of Ukraine, Kyiv, Ukraine 2 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine E-mail: adoro@imath.kiev.ua, darkal-ipt22@lll.kpi.ua, nishchenkoii-ipt@lll.kpi.ua ASYMPTOTIC BEHAVIOUR OF THE COMPLEXITY INDEX OF GROWING RANDOM TREES 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. Keywords: random tree, recursive tree, coalescent random forest, Wiener index, graph complexity.

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

Institution

Ähnliche Einträge