RUS  ENG
Полная версия
ЖУРНАЛЫ // Итоги науки и техники. Современная математика и ее приложения. Тематические обзоры // Архив

Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз., 2020, том 177, страницы 132–136 (Mi into607)

Эта публикация цитируется в 4 статьях

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

В. А. Воблый

Всероссийский институт научной и технической информации РАН, г. Москва

Аннотация: Последовательно-параллельный граф — это граф, не содержащий в качестве минора полный граф с четырьмя вершинами. Получена явная формула для числа помеченных последовательно-параллельных трициклических графов с заданным числом вершин, а также найдена асимптотика для числа таких графов с большим количеством вершин. Доказано, что при равномерном распределении вероятностей вероятность того, что помеченный трициклический граф является последовательно-параллельным графом, асимптотически равна $13/15$.

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

УДК: 519.175.3

MSC: 05C30

DOI: 10.36535/0233-6723-2020-177-132-136



© МИАН, 2024