О перечислении помеченных связных графов без мостов
- Авторы: Воблый В.А.1
-
Учреждения:
- Всероссийский институт научной и технической информации
- Выпуск: Том 223 (2023)
- Страницы: 138-147
- Раздел: Статьи
- URL: https://journals.rcsi.science/2782-4438/article/view/270841
- DOI: https://doi.org/10.36535/0233-6723-2023-223-138-147
- ID: 270841
Цитировать
Полный текст
Аннотация
Получены явные формулы и асимптотика для ряда классов помеченных графов без мостов: кактусов, графов блоков, полноблочно-кактусных графов и последовательно-параллельных графов. Доказано, что при равномерном распределении вероятностей почти все графы из рассматриваемых классов имеют мосты.
Об авторах
Виталий Антониевич Воблый
Всероссийский институт научной и технической информации
Автор, ответственный за переписку.
Email: vitvobl@yandex.ru
Россия, Москва
Список литературы
- Воблый В. А. Об одной формуле для числа помеченных связных графов // Дискрет. анал. иссл. опер. — 2012. — 19, № 4. — С. 48–59.
- Воблый В. А. Перечисление помеченных эйлеровых кактусов // Мат. XI Междунар. семин. «Дискретная математика и ее приложения» (Москва, 18–23 июня 2012 г.). — М.: МГУ, 2012. — С. 275–277.
- Воблый В. А. О перечислении помеченных связных бициклических и трициклических графов без мостов // Мат. заметки. — 2012. — 91, № 2. — С. 308–311.
- Воблый В. А. О перечислении помеченных связных графов с заданными числами вершин и ребер // Дискр. анал. иссл. опер. — 2016. — 23, № 2. — С. 5–20.
- Воблый В. А. Второе соотношение Риддела и следствия из него // Дискр. анал. иссл. опер. — 2019. — 26, № 1. — С. 20–32.
- Воблый В. А. О числе помеченных внешнепланарных k-циклических графов без мостов // Дискр. анал. иссл. опер. — 2020. — 27, № 1. — С. 5–16.
- Воблый В. А. Об асимптотическом перечислении помеченных связных k-циклических графов без мостов // Мат. заметки. — 2020. — 107, № 2. — С. 304–306.
- Воблый В. А. Асимптотическое перечисление помеченных последовательно-параллельных k-циклических графов без мостов // Дискр. анал. иссл. опер. — 2021. — 28, № 4. — С. 61–69.
- Воблый В. А. Уточнение асимптотики для числа помеченных последовательно-параллельных графов // Мат. заметки. — 2021. — 109, № 6. — С. 944–947.
- Воблый В. А., Мелешко А. К. Новая формула для числа помеченных кактусов с заданным числом вершин // Тез. докл. Междунар. науч. конф. «Дискретная математика, теория графов и их приложения» (Минск, 11–14 ноября 2013 г.). — Минск, 2013. — С. 9–11.
- Воблый В. А., Мелешко А. К. Перечисление помеченных полноблочно-кактусных графов // Дискр. анал. иссл. опер. — 2014. — 21. — С. 24–32.
- Воблый В. А., Мелешко А. К. Асимптотическое перечисление помеченных эйлеровых кактусов // Мат. XVII Междунар. конф. «Проблемы теоретической кибернетики» (Казань, 16-20 июля 2014 г.). — Казань, 2014. — С. 58–60.
- Гульден Я., Джексон Д. Перечислительная комбинаторика. — М.: Наука, 1990.
- Прудников А. П. и др. Интегралы и ряды. Т. 1. — М.: Наука, 1981.
- Харари Ф. Теория графов. — М.: Мир, 1973.
- Харари Ф., Палмер Э. Перечисление графов. — М.: Мир, 1977.
- Bodirsky M., Gimenez O., Kang M., Noy M. Enumeration and limit laws of series-parallel graphs // Eur. J. Combin. — 2007. — 28, № 8. — P. 2091–2105.
- Carlitz L. Single variable Bell polynomials // Collect. Math. — 1962. — 14. — P. 13–25.
- Flajolet P., Sedgewick G. E. Analytic Combinatorics. — Cambridge: Cambridge Univ. Press, 2009.
- Hanlon P., Robinson R. W. Counting bridgeless graphs // J. Combin. Theory. Ser. B. — 1982. — 33, № 1. — P. 276–305.
- Leroux P. Enumerative problems inspired by Mayer’s theory of cluster integrals // Electron. J. Combin. — 2004. — 11. — R32.
- McDiarmid C., Scott A. Random graphs from a block stable class // Eur. J. Combin. — 2016. — 58. — P. 96–106.
Дополнительные файлы
