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

Abstract

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