RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2021, том 28, выпуск 1, страницы 5–14 (Mi da1271)

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

О перечислении помеченных последовательно-параллельных $k$-циклических $2$-связных графов

В. А. Воблый

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

Аннотация: Получена явная формула для числа помеченных последовательно-параллельных $k$-циклических $n$-вершинных $2$-связных графов, а также найдена соответствующая асимптотика при большом числе вершин и фиксированном числе $k$. При равномерном распределении вероятностей найдена асимптотическая формула для вероятности того, что случайный $k$-циклический $n$-вершинный $2$-связный граф с большим числом вершин при фиксированном числе $k$ является последовательно-параллельным графом. Табл. 1, библиогр. 11.

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

УДК: 519.175.3

Статья поступила: 11.06.2020
Переработанный вариант: 20.10.2020
Принята к публикации: 22.10.2020

DOI: 10.33048/daio.2021.28.693


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2021, 15:1, 169–174

Реферативные базы данных:


© МИАН, 2024