Эта публикация цитируется в
1 статье
Об асимптотическом перечислении помеченных последовательно-параллельных $k$-циклических графов
В. А. Воблый Всероссийский институт научной и технической информации, ул. Усиевича, 20, 125190 Москва, Россия
Аннотация:
Получена асимптотика для числа помеченных связных последовательно-параллельных
$k$-циклических
$n$-вершинных графов при большом числе вершин и фиксированном числе
$k$. Найдена вероятность того, что при равномерном вероятностном распределении случайный помеченный связный
$n$-вершинный
$k$-циклический граф при фиксированном
$k$ и
$n\to\infty$ является последовательно-параллельным графом. Кроме того, определена вероятность того, что случайный помеченный связный последовательно-параллельный
$n$-вершинный
$k$-циклический граф при фиксированном
$k$ и
$n\to\infty$ является кактусом. Библиогр. 16.
Ключевые слова:
перечисление, помеченный граф, блок, последовательно-параллельный граф,
$k$-циклический граф, асимптотика, случайный граф.
УДК:
519.175.3 Статья поступила: 07.02.2022
Переработанный вариант: 17.04.2022
Принята к публикации: 19.04.2022
DOI:
10.33048/daio.2022.29.732