|
Прикладная теория графов
Асимптотика числа помеченных планарных тетрациклических и пентациклических графов
В. А. Воблый Всероссийский институт научной и технической информации РАН, г. Москва, Россия
Аннотация:
Cвязный граф c цикломатическим числом равным $k$ называется $k$-циклическим графом. Получена формула для числа помеченных непланарных пентациклических графов с заданным числом вершин, а также найдена асимптотика числа помеченных связных планарных тетрациклических и пентациклических графов с $n$ вершинами при $n\to\infty$. Доказано, что при равномерном распределении вероятностей на множестве рассматриваемых графов вероятность того, что помеченный тетрациклический граф является планарным, асимптотически равна 1089/1105, а вероятность того, что помеченный пентациклический граф является планарным, асимптотически равна 1591/1675.
Ключевые слова:
помеченный граф, планарный граф, тетрациклический граф, пентациклический граф, блок, перечисление, асимптотика, вероятность.
Образец цитирования:
В. А. Воблый, “Асимптотика числа помеченных планарных тетрациклических и пентациклических графов”, ПДМ, 2023, № 59, 72–79
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm794 https://www.mathnet.ru/rus/pdm/y2023/i1/p72
|
Статистика просмотров: |
Страница аннотации: | 76 | PDF полного текста: | 35 |
|