|
Перечисление помеченных колючих графов
В. А. Воблый, Н. А. Архипова Всероссийский институт научной и технической информации РАН, г. Москва
Аннотация:
Колючим графом называется связный граф, который становится гладким после однократного удаления висячих вершин вместе с инцидентными им ребрами. Получена явная формула для числа помеченных колючих графов с заданными числами вершин и ребер, а также найдена соответствующая асимптотика для числа таких графов с большим числом вершин. Доказывается, что при равномерном распределении вероятностей почти все помеченные связные разреженные графы не являются колючими графами.
Ключевые слова:
перечисление, помеченный граф, колючий граф, асимптотика, вероятность.
Образец цитирования:
В. А. Воблый, Н. А. Архипова, “Перечисление помеченных колючих графов”, Геометрия, механика и дифференциальные уравнения, Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз., 210, ВИНИТИ РАН, М., 2022, 49–54
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/into1014 https://www.mathnet.ru/rus/into/v210/p49
|
|