RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2023, номер 59, страницы 72–79 (Mi pdm794)

Прикладная теория графов

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

В. А. Воблый

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

Аннотация: Cвязный граф c цикломатическим числом равным $k$ называется $k$-циклическим графом. Получена формула для числа помеченных непланарных пентациклических графов с заданным числом вершин, а также найдена асимптотика числа помеченных связных планарных тетрациклических и пентациклических графов с $n$ вершинами при $n\to\infty$. Доказано, что при равномерном распределении вероятностей на множестве рассматриваемых графов вероятность того, что помеченный тетрациклический граф является планарным, асимптотически равна 1089/1105, а вероятность того, что помеченный пентациклический граф является планарным, асимптотически равна 1591/1675.

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

УДК: 519.175.3

DOI: 10.17223/20710410/59/4



© МИАН, 2024