Перечисление помеченных эйлеровых пентациклических графов

Воблый, Виталий Антониевич

Перечисление помеченных эйлеровых пентациклических графов

Дата публикации: 2020

Дата публикации в реестре: 2021-01-19T20:04:00Z

Аннотация:

Эйлеров граф - это связный граф, у которого все степени вершин - чётные числа. Пентациклическим графом называется связный граф с n вершинами и n + 4 рёбрами. Получена явная формула для числа помеченных эйлеровых пентациклических графов с заданным числом вершин, а также найдена соответствующая асимптотика для числа таких графов с большим числом вершин. Доказано, что при равномерном распределении вероятностей вероятность того, что помеченный эйлеров пентациклический граф является блоком (кактусом), асимптотически равна 53/272 (63/272 соответственно).

Ключевые слова:
помеченные графы, эйлеров граф, пентациклические графы, блоки графов, перечисления графов, асимптотика, вероятность

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2020. № 50. С. 87-92