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

Автор(и)

  • А.А. Дороговцев Інститут математики НАН України, Київ, Україна https://orcid.org/0000-0003-0385-7897
  • Д.М. Калитюк Національний технічний університет України “Київський політехнічний інститут ім. Ігоря Сікорського”, Київ, Україна
  • І.І. Ніщенко Національний технічний університет України “Київський політехнічний інститут ім. Ігоря Сікорського”, Київ, Україна

DOI:

https://doi.org/10.15407/dopovidi2024.03.003

Ключові слова:

випадкове дерево, рекурсивне випадкове дерево, індекс Вінера, складність графа

Анотація

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

Завантаження

Дані завантаження ще не доступні.

Посилання

Wiener, H. (1947). Structural determination of paraffin boiling points. J. the Amer. Chem. Society, 69, No. 1, pp.17-20.

Diudea, M. V. & Gutman, I. (1998). Wiener-type topological indeces. Croatica Chem. Acta, 71, № 1, pp. 21-51.

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

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

Neininger, R. (2002). The Wiener index of random trees. Combinatorics, Probability and Computing, 11, No. 6, pp. 587-597.

Smythe, R. & Mahmoud, H. (1995). A survey of recursive trees. Theory Probab. Math. Statist., 51, pp. 1-27.

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

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

Pitman, J. (1999). Coalescent Random Forests. J. Combinatorial Theory, A85, pp. 165-193. https://doi.org/10.1006/jcta.1998.2919

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

Buffet, E. & Pulé, J. V. (1991). Polymers and random graphs. J. Statist. Phys., 64, pp. 87-110. https://doi.org/10.1007/BF01057869

##submission.downloads##

Опубліковано

02.07.2024

Як цитувати

Дороговцев, А., Калитюк, Д., & Ніщенко, І. (2024). Асимптотична поведінка індексу складності зростаючих випадкових дерев. Reports of the National Academy of Sciences of Ukraine, (3), 3–10. https://doi.org/10.15407/dopovidi2024.03.003

Номер

№ 3 (2024): Доповіді Національної академії наук України

Розділ

Математика

Ліцензія

Авторське право (c) 2024 Reports of the National Academy of Sciences of Ukraine

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.