Обобщённый индекс Загреба для непланарных и планарных рекурсивных деревьев

Основная информация

• ID статьи: 2510.10569
• Название: The Generalized Zagreb Index for Non-Plane and Plane Recursive Trees
• Авторы: Qunqiang Feng (Университет науки и технологии Китая), Michael Fuchs (Национальный университет Чэнчи), Tsan-Cheng Yu (Католический университет Фужэнь)
• Классификация: math.PR (Теория вероятностей), math.CO (Комбинаторика)
• Дата публикации: 14 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.10569

Аннотация

Индекс Загреба определяется как сумма квадратов степеней всех вершин дерева. Предыдущие исследования с использованием техники мартингалов изучали случайные непланарные рекурсивные деревья и близкие классы планарных рекурсивных деревьев. Эти методы сложно применять непосредственно к обобщённому индексу Загреба, который заменяет квадрат на более высокие степени. В данной работе применяется метод передачи моментов для: (i) получения асимптотики первого порядка моментов, (ii) доказательства предельных законов для (надлежащим образом нормализованного) обобщённого индекса Загреба случайных непланарных и планарных рекурсивных деревьев. Для первых мы доказываем, что предельный закон является нормальным для всех высших степеней; для вторых мы доказываем, что предельный закон является ненормальным для третьей и четвёртой степеней.

Исследовательский контекст и мотивация

Фоновая информация о проблеме

1. Важность индекса Загреба: Индекс Загреба является одним из наиболее широко изучаемых топологических индексов в химической теории графов, введённый Гутманом и Тринайстичем в 1970-х годах. Широко используется для прогнозирования физико-химических свойств соединений, имеет важное применение в количественных исследованиях структура-свойство (QSPR) и структура-активность (QSAR).
2. Обобщённый индекс Загреба: Для графа G=(V,E) индекс Загреба k-го порядка определяется как: $Z_G^{(k)} = \sum_{v \in V} D_v^k = \sum_{uv \in E} (D_u^{k-1} + D_v^{k-1})$ где $D_v$ обозначает степень вершины v. При k=2 соответствует первому индексу Загреба, при k=3 называется забытым топологическим индексом.
3. Ограничения существующих методов:
   • Предыдущие исследования первого индекса Загреба (k=2) в основном использовали технику мартингалов и метод Стейна
   • Эти методы сложно расширяются на общие значения k
   • Требуются новые подходы для анализа обобщённого индекса Загреба
4. Объекты исследования:
   • Случайные непланарные рекурсивные деревья: дочерние узлы неупорядочены
   • Случайные планарные рекурсивные деревья: дочерние узлы имеют левый и правый порядок

Основные вклады

1. Методологическое новшество: Впервые применён метод передачи моментов к анализу обобщённого индекса Загреба, преодолевая ограничения традиционной техники мартингалов
2. Теоретические результаты:
   • Для случайных непланарных рекурсивных деревьев: доказано, что надлежащим образом нормализованный обобщённый индекс Загреба сходится к стандартному нормальному распределению для всех k≥2
   • Для случайных планарных рекурсивных деревьев: доказано, что при k=3,4 сходится к ненормальному распределению
3. Асимптотический анализ: Получены асимптотические выражения первого порядка для всех порядков моментов, обеспечивая полную теоретическую базу для понимания статистических свойств этих индексов
4. Единая схема: Предоставлен единый метод для работы с различными степенями k, расширяя существующую теорию

Подробное описание методов

Определение задачи

Исследование асимптотического поведения обобщённого индекса Загреба $Z_n^{(k)} = \sum_{v} D_v^k$ в случайных рекурсивных деревьях, где:

• Входные данные: случайное рекурсивное дерево размера n
• Выходные данные: предельное распределение обобщённого индекса Загреба
• Ограничения: требуется надлежащая нормализация для существования предельного распределения

Основной метод: метод передачи моментов

1. Рекурсивные соотношения распределений

Для случайного рекурсивного дерева размера n обобщённый индекс Загреба удовлетворяет рекурсивному соотношению: $Z_n^{(k)} \stackrel{d}{=} Z_{I_n}^{(k)} + \tilde{Z}_{n-I_n}^{(k)} - R_{I_n}^k + (R_{I_n}+1)^k - \tilde{R}_{n-I_n}^k + (\tilde{R}_{n-I_n}+1)^k$

где $I_n$ — размер крайнего левого поддерева корня, $R_n$ — степень корня.

2. Рекурсивные уравнения для моментов

Все центральные моменты удовлетворяют рекурсивным уравнениям вида: $a_n = \sum_{j=1}^{n-1} \pi_{n,j}(a_j + a_{n-j}) + b_n$

где $\pi_{n,j} = P(I_n = j)$, $b_n$ — функция, зависящая от моментов низшего порядка.

3. Результаты асимптотической передачи

Использование установленных лемм асимптотической передачи для вывода асимптотики $a_n$ из асимптотики $b_n$:

Непланарные рекурсивные деревья (леммы 2.5-2.6):

• Если $b_n = \hat{O}(n^α)$ и $0 ≤ α < 1$, то $a_n = μn + \hat{O}(n^α)$
• Если $b_n \sim cn^α$ и $α > 1$, то $a_n \sim c(α+1)n^α/(α-1)$

Планарные рекурсивные деревья (леммы 2.8-2.9):

• Если $b_n \sim c\sqrt{n}$, то $a_n \sim cn\log n/\sqrt{π}$
• Если $b_n \sim cn^α$ и $α > 1/2$, то $a_n \sim c\Gamma(α-1/2)n^{α+1/2}/\Gamma(α)$

Технические инновации

1. Анализ смешанных моментов: Поскольку рекурсивное соотношение включает степень корня $R_n$, необходимо одновременно анализировать смешанные моменты $Z_n^{(k)}$ и $R_n$
2. Стратегия доказательства по индукции: Использование лексикографического порядка для пар $(r,s)$, где $r$ — степень $Z_n$, $s$ — степень $R_n$
3. Различные нормализации:
   • Непланарные деревья: $(Z_n^{(k)} - μ_k n)/(σ_k\sqrt{n})$
   • Планарные деревья: $Z_n^{(k)}/n^{k/2}$

Экспериментальная установка

Теоретическая схема анализа

Данная работа представляет собой в основном теоретический анализ без численных экспериментов. Схема анализа включает:

1. Вероятностная модель:
   • Непланарные рекурсивные деревья: $I_n$ равномерно распределено на $\{1,...,n-1\}$
   • Планарные рекурсивные деревья: $P(I_n = j) = \frac{2(n-j)C_jC_{n-j}}{nC_n}$
2. Вычисление моментов: Расчёт асимптотических выражений различных порядков моментов через рекурсивные соотношения
3. Проверка предельных теорем: Использование метода моментов для доказательства сходимости

Вычислительные примеры

Для случая k=2 в работе приводятся точные вычисления:

• Непланарные деревья: $μ_2 = 6$
• Планарные деревья: $E(Z_n^{(2)}) = 2n\log n + (4\log 2 + 2γ - 2)n + O(\sqrt{n})$

Результаты экспериментов

Основные теоретические результаты

Непланарные рекурсивные деревья (теорема 3.1)

Для всех k≥2: $\frac{Z_n^{(k)} - μ_k n}{σ_k\sqrt{n}} \stackrel{d}{\rightarrow} N(0,1)$

где $μ_k, σ_k > 0$ — явно определённые константы.

Планарные рекурсивные деревья (теорема 4.1)

Для k=3 или k=4: $\frac{Z_n^{(k)}}{n^{k/2}} \stackrel{d}{\rightarrow} Z^{(k)}$

где $Z^{(k)}$ — ненормальная случайная величина, однозначно определяемая последовательностью моментов.

Результаты асимптотического анализа

Асимптотическое поведение моментов:

• Непланарные деревья: $E(\bar{Z}_n^r) \sim g_r σ_k^r n^{r/2}$, где $g_r$ — моменты стандартного нормального распределения
• Планарные деревья: $E(Z_n^r R_n^s) \sim g_{r,s} n^{(kr+s)/2}$

Условия сходимости:

• При k=3,4 последовательность моментов удовлетворяет условию Карлемана, обеспечивая единственность распределения
• При k≥5 рост моментов слишком быстрый, метод моментов неприменим

Ключевые находки

1. Явление фазового перехода: Непланарные и планарные деревья демонстрируют совершенно различное предельное поведение
2. Эффект степени: Значение k существенно влияет на способ нормализации и тип предельного распределения
3. Ограничения метода: Метод передачи моментов неприменим для случая k≥5

Связанные работы

Основные направления исследований

1. Исследования индекса Загреба:
   • Gutman & Trinajstić (1972): первое введение индекса Загреба
   • Широкое применение в исследованиях QSPR/QSAR
   • Исследования экстремальных задач и границ
2. Топологические индексы на случайных деревьях:
   • Feng & Hu (2011, 2013): использование техники мартингалов для изучения первого индекса Загреба
   • Zhang (2020): исследования планарных рекурсивных деревьев
   • Исследования на случайных графах Эрдёша-Рени
3. Метод передачи моментов:
   • Neininger & Hwang (2002): установление базовой схемы
   • Hwang (2006): применение к планарным рекурсивным деревьям
   • Chen & Fuchs (2011): совершенствование метода

Преимущества данной работы

1. Методологическое новшество: Впервые применён метод передачи моментов к обобщённому индексу Загреба
2. Полнота результатов: Охватывает все возможные значения k
3. Теоретическая глубина: Предоставляет полную схему асимптотического анализа

Выводы и обсуждение

Основные выводы

1. Эффективность метода: Метод передачи моментов успешно решает проблему обобщённого индекса Загреба, которую не могла решить техника мартингалов
2. Различия в распределениях:
   • Непланарные рекурсивные деревья: сходятся к нормальному распределению для всех k≥2
   • Планарные рекурсивные деревья: сходятся к ненормальному распределению при k≥3
3. Теоретическая полнота: Предоставляет полную предельную теорию для k=3,4

Ограничения

1. Ограничения метода:
   • Для планарных рекурсивных деревьев метод моментов неприменим при k≥5
   • k=2 требует специальной обработки
2. Технические вызовы:
   • Анализ смешанных моментов сложен
   • Применение результатов асимптотической передачи требует точного контроля ошибок
3. Область применимости:
   • Применимо только к моделям рекурсивных деревьев
   • Другие модели случайных деревьев требуют различных результатов передачи

Будущие направления

1. Расширение методов:
   • Поиск новых методов для случаев k≥5
   • Расширение на другие модели случайных деревьев
2. Прикладные исследования:
   • Практическое применение в химической теории графов
   • Взаимосвязь с другими топологическими индексами

Глубокая оценка

Достоинства

1. Теоретический вклад:
   • Решение важной открытой проблемы
   • Предоставление новых аналитических инструментов и схем
   • Результаты имеют сильную теоретическую ценность
2. Методологическое новшество:
   • Умелое применение метода передачи моментов к новой проблеме
   • Техника обработки смешанных моментов имеет общий характер
3. Глубина анализа:
   • Полный асимптотический анализ
   • Строгие математические доказательства
   • Ясная техническая схема
4. Качество изложения:
   • Ясная структура, логичное построение
   • Полные технические детали
   • Всестороннее рассмотрение связанных работ

Недостатки

1. Ограничения практичности:
   • Чисто теоретическое исследование, отсутствие численной проверки
   • Недостаточная связь с практическими приложениями
2. Ограничения метода:
   • Невозможность обработки некоторых диапазонов параметров
   • Зависимость от конкретной модели рекурсивных деревьев
3. Представление результатов:
   • Отсутствие конкретных численных примеров
   • Недостаточно подробное описание свойств предельного распределения

Влияние

1. Научный вклад:
   • Предоставление новых инструментов для междисциплинарных исследований теории вероятностей и комбинаторики
   • Возможное вдохновение для исследований других топологических индексов
2. Методологическая ценность:
   • Новое применение метода передачи моментов
   • Предоставление аналитической схемы для аналогичных проблем
3. Теоретическое значение:
   • Обогащение теории случайных деревьев
   • Углубление понимания асимптотических свойств топологических индексов

Применимые сценарии

1. Теоретические исследования: Исследования в области теории вероятностей, комбинаторики, теории графов
2. Методология: Справочный материал для асимптотического анализа других параметров
3. Прикладной контекст: Исследования топологических индексов в химической теории графов и анализе сетей

Библиография

Статья цитирует 25 важных работ, охватывающих основные исследования в области индекса Загреба, случайных деревьев, метода передачи моментов и связанных областей, обеспечивая прочную теоретическую базу для исследования.

Общая оценка: Это высокачественная теоретическая работа, успешно решающая проблему асимптотического анализа обобщённого индекса Загреба на случайных рекурсивных деревьях. Метод инновационен, результаты полны и глубоки, имеют важное теоретическое значение для соответствующей области. Хотя практическая применимость ограничена, теоретический вклад и методологическое значение делают её важным прогрессом в данной области.