Том 24, номер 2, 2017 г., Стр. 18-31

УДК 519.175.3
Воблый В. А., Мелешко А. К.
Перечисление помеченных внешнепланарных бициклических и трициклических графов

Аннотация:
Класс внешнепланарных графов используется для тестирования средней сложности алгоритмов на графах. Случайный помеченный внешнепланарный граф может быть сгенерирован полиномиальным алгоритмом, базирующимся на результатах перечисления таких графов. Под бициклическим (трициклическим) графом понимается связный граф с цикломатическим числом равным 2 (соответственно 3). Для чисел помеченных связных внешнепланарных бициклических и трициклических графов с $n$ вершинами получены явные формулы, а также асимптотика для чисел этих графов при большом $n$. Кроме того, найдены явные формулы для числа помеченных внешнепланарных бициклических и трициклических $n$-вершинных блоков и выведена соответствующая асимптотика при большом $n$.
Табл. 1, ил. 4, библиогр. 15.

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

DOI: 10.17377/daio.2017.24.544

Воблый Виталий Антониевич ¹
Мелешко Анна Константиновна ¹
1. Московский государственный технический университет им. Н. Э. Баумана,
2-я Бауманская ул., д. 5, стр. 1, 105005 Москва, Россия
е-mail: vitvobl@yandex.ru, akmeleshko@gmail.com

Статья поступила 10 мая 2016 г.
Исправленный вариант — 11 октября 2016 г.

Литература

[1] Воблый В. А. Асимптотическое перечисление графов некоторых типов: Автореф. дис. канд. физ.-мат. наук: 01.01.09, Москва, ВЦ АН, 1985. 12 c.

[2] Воблый В. А. Об одной формуле для числа помеченных связных графов // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 4. C. 48–59.

[3] Воблый В. А., Мелешко А. К. Перечисление помеченных графов розы // Мат. XVI Междунар. науч.-практ. семинара «Комбинаторные конфигурации и их приложения» (Кировоград, 11–12 апреля 2014 г.). Кировоград: Кировоград. нац. тех. университет, 2014. C. 27–29.

[4] Дмитриев Е. Ф. Перечисление отмеченных двуцветных связных графов с небольшим цикломатическим числом. Деп. в ВИНИТИ, № 4959-85.

[5] Прудников А. П., Брычков Ю. А., Маричев О. И. Интегралы и ряды: Элементарные функции. М.: Наука, 1981. 800 с.

[6] Степанов В. Е. О некоторых особенностях строения случайного графа вблизи критической точки // Теория вероятностей и её применения. 1987. Т. 32, вып. 4. C. 633–657.

[7] Харари Ф. Теория графов. М.: Мир, 1973. 300 c.

[8] Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 326 c.

[9] Bodirsky M., Kang M. Generating outerplanar graphs uniformly at random // Comb. Probab. Computing. 2006. Vol. 15, No. 3. P. 333–343.

[10] Bodirsky M., Gimenez O., Kang M., Noy M. Enumeration and limit laws of series-parallel graphs // Eur. J. Comb. 2007. Vol. 28, No. 8. P. 2091–2105.

[11] Ford G. W., Uhlenbeck G. E. Combinatorial problems in the theory of graphs. IV // Proc. Nat. Acad. Sci. USA. 1957. Vol. 43, No. 1. P. 163–167.

[12] Knuth D. E., Pittel B. A recurrence related to trees // Proc. Amer. Math. Soc. 1989. Vol. 105, No. 2. P. 335–349.

[13] Read R. C. Some unusual enumeration problems // Ann. New York Acad. Sci. 1970. Vol. 175. P. 314–326

[14] Wright E. M. The number of connected sparsely edged graphs // J. Graph Theory. 1977. Vol. 1, No. 4. P. 317–330.

[15] Wright E. M. The number of connected sparsely edged graphs. II // J. Graph Theory. 1978. Vol. 2, No. 4. P. 299–305.