Асимптотическое перечисление некоторых помеченных геодезических графов
- Авторы: Воблый В.А.1
-
Учреждения:
- Всероссийский институт научной и технической информации Российской академии наук
- Выпуск: Том 215 (2022)
- Страницы: 58-67
- Раздел: Статьи
- URL: https://journal-vniispk.ru/2782-4438/article/view/269982
- DOI: https://doi.org/10.36535/0233-6723-2022-215-58-67
- ID: 269982
Цитировать
Полный текст
Аннотация
Асимптотически перечислены помеченные геодезические k-циклические кактусы. Получена асимптотика для числа помеченных связных геодезических унициклических, бициклических и трициклических n-вершинных графов. Доказано, что при равномерном распределении вероятностей вероятность того, что случайный помеченный связный унициклический, бициклический и трициклический граф является геодезическим графом, асимптотически равна 1/2, 3/20 и 1/30, соответственно. Найдена также вероятность того, что случайный помеченный связный k-циклический граф является геодезическим кактусом. Кроме того, доказано, что почти все помеченные связные геодезические трициклические графы являются кактусами.
Ключевые слова
Об авторах
Виталий Антониевич Воблый
Всероссийский институт научной и технической информации Российской академии наук
Автор, ответственный за переписку.
Email: vitvobl@yandex.ru
Россия, Москва
Список литературы
- Воблый В. А. Перечисление помеченных геодезических планарных графов// Мат. заметки. — 2015. —97, № 3. — С. 336–341.
- Воблый В. А. Перечисление помеченных геодезических графов с малым цикломатическим числом//Мат. заметки. — 2017. — 101, № 5. — С. 684–689.
- Воблый В. А. Асимптотическое перечисление помеченных последовательно-параллельных тетрациклических графов// Итоги науки техн. Сер. Совр. мат. прилож. Темат. обзоры. — 2020. — 187.—С. 31–35.
- Воблый В. А. Перечисление помеченных последовательно-параллельных трициклических графов//Итоги науки техн. Сер. Совр. мат. прилож. Темат. обзоры. — 2020. — 177. — С. 132–136.
- Воблый В. А. О перечислении помеченных связных графов с заданными числами вершин и ребер//Дискр. анал. иссл. опер. — 2016. — 23, № 2. — С. 5–20.
- Воблый В. А. Второе соотношение Риддела и следствия из него// Дискр. анал. иссл. опер. — 2019. —26, № 1. — С. 20–32.
- Воблый В. А. Об асимптотическое перечислении помеченных последовательно-параллельных k-циклических графов// Дискр. анал. иссл. опер. — 2022. — 29, № 4. — С. 5–14.
- Воблый В. А., Мелешко А. К. Перечисление помеченных геодезических k-циклических кактусов//Мат. XVIII Междунар. конф. «Проблемы теоретической кибернетики». — Пенза, 2017. — С. 56–57.
- Гульден Я., Джексон Д. Перечислительная комбинаторика. — М.: Наука, 1990.
- Кудрявцев Л. Д. Краткий курс математического анализа. — М.: Наука, 1989.
- Риордан Дж. Комбинаторные тождества. — Наука, 1982.
- Харари Ф. Теория графов. — М.: Мир, 1973.
- Харари Ф., Палмер Э. Перечисление графов. — М.: Мир, 1977.
- Frasser C. E. k-Geodetic graphs and their application to the topological design of computer networks//Proc. Argentinian Workshop on Theoretical Computer Science, 28 JAIIO-WAIT’99, 1999. — P. 187–203.
- Mc Diarmid C., Scott A. Random graphs from a block stable class// Eur. J. Combin. — 2016. — 58.— P. 96–106.
- NIST Handbook of Mathematical Functions. — New York: Cambridge Univ. Press, 2010.
- Stemple J. G., Watkins M. E. On planar geodetic graphs// J. Combin. Theory. — 1968. — 4. — P. 101–117.
- Temme N.M., Veling E.J.M. Asymptotic expansions of Kummer hypergeometric functions with three parameters a, b and z/ arXiv: 2202.12857v3 [math.CA].
- Wright E. M. The number of connected sparsely edged graphs// J. Graph Theory. — 1977. — 1, № 4. — P. 317–330.
Дополнительные файлы
