DisCollection.ru

Авторефераты и темы диссертаций

Поступления 19.07.2009

Материалы

загрузка...

Некоторые задачи перечисления помеченных связных графов

Воблый Виталий Антониевич, 19.07.2009

 

1. Найдена явная формула для энумератора помеченных связных графов по числу вершин с заданным количеством точек сочленения. Получена асимптотика для числа помеченных связных графов с большим количеством вершин и большим количеством точек сочленения.

2. Выведена формула для энумератора помеченных связных гомео-морфно несводимых графов по числу вершин с заданным циклома-тическим числом. Получена асимптотика для числа помеченных связных разреженных гомеоморфно несводимых графов с большим количеством вершин и фиксированным цикломатическим числом.

3. Выведена асимптотика для числа помеченных связных разреженных графов с большим числом вершин и фиксированным количеством вися-чих вершин.

4. Получена асимптотика чисел, удовлетворяющих квадратичному разностному уравнению типа свертки. Найдены предельные значения для коэффициентов Райта и Степанова-Райта.

-бирегулярных графов.

6. Выведены два комбинаторных тождества, с помощью которых упро-щены некоторые формулы для числа карт на поверхностях и получена соответствующая асимптотика для карт с большим количеством вершин или

Л И Т Е Р А Т У Р А

1. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

2. Иванчик И.И. Проблемы теории графов в статистической физике. Труды ФИАН, т. 106. М.: Наука, 1979, с. 3-89.

3. Калмыков Г.И. Древесная классификация помеченных графов. М.: Физматлит, 2003.

4. Калмыков Г.И. Каркасная классификация помеченных графов. М.: Научный мир, 2006.

5. Ravelomanana V., Thimonier L. Enumeration of the first multicyclic isomorphism-free labelled graphs. Proc. 13th internat. conf. on Formal Power Series and Algebraic Combinatorics (FPSAC01), 2001, 411-420.

6. Bodirsky M., Groepl C., Kang M. Generating labeled planar graphs uniformly at random. In ICALP 2003, pp. 1095-1107, Springer, Berlin,

7. Flajolet P., Salvy B., Schaeffer G. Airy phenomena and analitic combina-torics of connected graphs. Electron. J. Combin. 11(2004), #34.

8. Leroux P. Enumerative problems inspired by Mayer`s theory of cluster integrals . Electron. J. Combin. 11(2004), #32.

9. Chae G.-B., Palmer E.M., Robinson R.W. Computing the number of labeled general cubic graphs. Discrete Math. 307(2007), 2979-2992.

10. Selkow S.M. The enumeration of labeled graphs by number of cutpoints.

Discrete Math. (1998), 185, 183-191.

11. Багаев Г.Н., Воблый В.А. Метод сжатия-разжатия для перечисления графов. – Дискретная математика, т. 10, вып. 4, 1998, с. 82-87.

12. Jackson D.M., Reilly J.W. The enumeration of homeomorphically irredu-cible labeled graphs. J. Combin. Theory(B), 19(1975), 272-286.

13 Read R.C. Some unusual enumeration problems. – Ann. N.-Y. Acad.

1970, V. 175, Art. 1, 314-326.

14. Wright E.M. Enumeration of smooth labelled graphs. Proc. Roy. Soc.

Edinburgh, 1981. A91, N 3/4, 205-212.

15. Багаев Г. Н., Дмитриев Е. Ф. Перечисление связных двуцветных

графов. Комбинаторный анализ (1983), вып. 6, 58–64.

16. Janson S. Brownian excursion area, Wright`s constants in graph enumeration, and other Brownian areas. Probability Surveys, 4(2007),

17. Flajolet P., Poblete P., Viola A. On the analysis of linear probing hashing. Algorithmica 22(1998), 490-515.

18. Wright E.M. The number of connected sparsely edged graphs. IV

J. Graph Theory. 1983. V. 7. N 2. P. 219-229.

19. Wormald N.C. Enumeration of labelled graphs II: Cubic graphs with given connectivity. J. London Math. Soc. (2), 20(1979), 1-7.

20. Read R.C. The enumeration of locally restricted graphs. I

J. London Math Soc., 1959. v. 34, 417-436.

21. Bender E.A. An asymptotic expansion for the coefficients of some

power series // J. London Math. Soc. (2). 1975. V. 9. 451-458.

22. McKay B.D. Spanning trees in regular graphs. Europ. J. Combinatorics, 4(1983), 149-160.

23. Malyshev V.A. Combinatorics and probability of maps. In Asymptotic combinatotics with application to mathematical physics, Dordrecht a.o., Kluwer, 2002, 71-95.

24. Liu Y.P. A note on the number of cubic planar maps, Acta Mathematica Scintia, 12(1992), 282-285.

25. Hao R., Cai Y., Liu Y. Counting g-essential maps on surfaces with small genera. – Korean J. Comput. and Appl. Math., v. 9 (2002), №2,

26. Liu W., Liu Y. Enumeration of three kinds of rooted maps on the Klein bootle. J. Appl. Math. & Computing 24(2007), 411-419.