Эйлеров граф - это связный граф, у которого все степени вершин - чётные числа. Пентациклическим графом называется связный граф с n вершинами и n + 4 рёбрами. Получена явная формула для числа помеченных эйлеровых пентациклических графов с заданным числом вершин, а также найдена соответствующая асимптотика для числа таких графов с большим числом вершин. Доказано, что при равномерном распределении вероятностей вероятность того, что помеченный эйлеров пентациклический граф является блоком (кактусом), асимптотически равна 53/272 (63/272 соответственно).
Скачать электронную версию публикации
Загружен, раз: 71
- Title Перечисление помеченных эйлеровых пентациклических графов
- Headline Перечисление помеченных эйлеровых пентациклических графов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 50
- Date:
- DOI 10.17223/20710410/50/6
Ключевые слова
помеченный граф, эйлеров граф, пентациклический граф, блок, перечисление, асимптотика, вероятностьАвторы
Ссылки
Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с.
Kumar A. A study on Euler graph and it’s applications // Int. J. Math. Trends Technol. 2017. V. 43. No. 1. P.9-14.
Pancoska P., Moravek Z., and Moll U. M. Rational design of DNA sequences for nanotechnology, microarrays and molecular computers using Eulerian graphs // Nucleic Acids Res. 2004. V.32. No. 15. P.4630-4645.
Amudha P., Sagayaraj A. C. C., and Sheela A.C.S. An application of graph theory in cryptography // Int. J. Pure Appl. Math. 2018. V. 119. No. 13. P.375-383.
Read R. C. Euler graphs on labelled nodes // Canad. J. Math. 1962. V. 14. P.482-486.
Tazawa S. Enumeration of labelled 2-connected Euler graphs // J. Combinat. Inform. System Sci. 1998. V. 23. No. 1-4. P. 407-414.
Воблый В. А. Перечисление помеченных связных бициклических и трициклических эйлеровых графов // Матем. заметки. 2012. Т. 92. №5. С. 678-683.
Воблый В. А., Мелешко А. К. Перечисление помеченных эйлеровых тетрациклических графов //Дискретн. анализ и исслед. операций. 2014. Т. 21. №5. С. 17-22.
Воблый В. А. О числе помеченных эйлеровых пентациклических блоков //Материалы заочного семинара XIX Международ. конф. «Проблемы теоретической кибернетики». Казань, 2020. С. 41-44.
Воблый В. А. О перечислении помеченных связных графов с заданными числами вершин и ребер //Дискретн. анализ и исслед. операций. 2016. Т. 3. №2. С. 5-20.
Гульден Я., Джексон Д. Перечислительная комбинаторика. М.: Наука, 1990. 504с.
Риордан Дж. Комбинаторные тождества. М.: Наука, 1981. 256 с.
Воблый В. А. Второе соотношение Риддела и следствия из него // Дискретн. анализ и исслед. операций. 2019. Т. 26. №1. С. 20-32.
Mc Diarmid C. and Scott A. A random graphs from a block stable class. II //Europ. J. Combin. 2016. V. 58. P. 96-106.
Воблый В. А., Мелешко А. К. Перечисление помеченных полноблочно-кактусных графов // Дискретн. анализ и исслед. операций. 2014. Т. 21. №2. С. 24-32.
Перечисление помеченных эйлеровых пентациклических графов | Прикладная дискретная математика. 2020. № 50. DOI: 10.17223/20710410/50/6
Скачать полнотекстовую версию
Загружен, раз: 192