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

Дискретн. анализ и исслед. опер., 2023, том 30, выпуск 4, страницы 24–34 (Mi da1332)

Перечисление помеченных графов библоков

В. А. Воблый

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

Аннотация: Граф библоков  — это связный граф, у которого все блоки являются полными двудольными графами. В статье перечислены по числу вершин точно и асимптотически помеченные графы библоков и графы библоков без мостов. Доказано, что почти все помеченные связные графы библоков не имеют мостов. Кроме того, перечислены помеченные планарные графы библоков и найдена асимптотическая оценка для числа таких графов. Табл. 1, библиогр. 12.

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

УДК: 519.175.3

Статья поступила: 12.07.2023
Переработанный вариант: 04.08.2023
Принята к публикации: 20.08.2023

DOI: 10.33048/daio.2023.30.778


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2023, 17:4, 901–907


© МИАН, 2024