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

Важным разделом теории графов является теория их перечисления, имеющая многочисленные приложения не только в математической кибернетике, но и в таких областях естествознания, как например, структурная химия и статистическая физика [30]. У истоков теории графов лежат работы А. Кэли по перечислению помеченных деревьев и связанных с ними химических структур, опубликованные в 1857—1889 гг. Однако только во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики и в том числе теории перечисления графов.

Комбинаторика тесно связана с теорией вероятностей. В настоящее время теория вероятностей далеко ушла от своих комбинаторных истоков, превратившись в могучую математическую реку со своим мощным аппаратом исследования. Однако «комбинаторные ключи» постоянно подпитывают эту реку. Во многих работах по теории случайных графов используются комбинаторные построения [22, 52,66].

Если на множестве исследуемых графов задано равномерное распределение вероятностей, то числовые характеристики этих графов можно рассматривать как случайные величины и анализировать их с помощью хорошо развитого аппарата теории вероятностей. Однако возможен и другой подход, когда, как в начале развития теории вероятностей, с помощью комбинаторики получаются утверждения для случайных графов. Во многих случаях из решения перечислительной задачи теории графов можно вывести следствия, характеризующие свойства и структуру соответствующих случайных графов.

Перечисление помеченных графов необходимо при непосредственном перечислении непомеченных графов с помощью леммы Бернсайда [26], а также используется для получения асимптотики непомеченных графов [105]. Результаты перечисления помеченных графов применяются для их случайной генерации и анализа эффективности алгоритмов^].

Хотя теория перечисления помеченных связных графов интенсивно развивается уже в течение 50 лет, интерес к этой области перечислительной комбинаторики не пропал, о чем говорят многочисленные работы зарубежных исследователей последних лет [58, 70, 82, 54, 59].

Помеченные графы используются в ряде физических задач [17−20] и поэтому перечисление таких графов является актуальной задачей.

Диссертация состоит из введения, шести глав и списка литературы. Ссылки в тексте за пределами главы содержат в качестве первого индекса номер главы, а второй индекс — номер утверждения или формулы. Ссылки внутри главы содержат только номер утверждения (формулы).

1. Багаев Г. Н. Случайные графы со степенью связности 2. Дискретный анализ (1973) 22, 3−14.

2. Багаев Г. Н. Предельные распределения метрических характеристик случайного неразложимого отображения. Комбинаторный и асимптотический анализ. КГУ, Красноярск, 1977, 55−61.

3. Багаев Г. Н., Дмитриев Е. Ф. Перечисление связных двуцветных графов. Комбинаторный анализ (1983) 6, 58—64.

4. Багаев Г. Н. Распределение числа вершин в слоях случайного многоцветного дерева. Вероятностные процессы и их прилоэюения. МИЭМ, Москва, 1984, 12−16.

5. Багаев Г. Н., Дмитриев Е. Ф. Перечисление связных отмеченных двудольных графов // ДАН БССР. 1984. Т. 28, № 12,1061 1063.

6. Багаев Г. Н., К перечислению связных гиперграфов. Комбинаторный анализ, (1980), вып. 5, 59−61.

7. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции, т. 1, М: Наука, ГРФМЛ, 1965.

8. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции, т. 2, М: Наука, ГРФМЛ, 1966.

9. Бендер Э. А. Асимптотические методы в теории перечислений. Перечислительные задачи комбинаторного анализа. М., Мир, 1979, с. 266−310.

10. Гельфонд А. О. Исчисление конечных разностей. М.: Наука, 1967.

11. Градштейн И. С., Рыжик И. М. Таблицы интегралов, сумм, рядов, произведений. М.: Наука, 1971.

12. Гульден Я. и Джексон Д., Перечислительная комбинаторика. Наука, М. 1990.

13. Дмитриев Е. Ф. Перечисление отмеченных связных и гладких гомеоморфных графов. Деп. ВИНИТИ 8.07.85 4957−85, 10 стр.

14. Евграфов М. А. Аналитические функции. М.: Наука, 1968.

15. Егорычев Г. П., Интегральное представление и вычисление комбинаторных сумм. Наука, Новосибирск. 1977.

16. Зайцев В. Ф., Полянин А. Д. Справочник по нелинейным дифференциальным уравнениям. Наука, М., 1993.

17. Иванчик И. И. О бесповторном перечислении связных помеченных графов. Сб. Комбинаторный анализ, вып. 4, М.: Изд-во МГУ, 1976, 78—87.

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

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

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

21. Камке Э. Справочник по обыкновенным дифференциальным уравнениям. М.: Наука, 1971. <

22. Колчин В. Ф. Случайные графы. М.: Физматлит, 2000.

23. Котляр Б. Д. Об одном необходимом условии хроматичности многочлена— Кибернетика и системный анализ, 1998, № 5, 176−178.

24. Лаврентьев М. А., Шабат Б. В. Методы теории функций комплексного переменного. М.: Физматлит, 1965.

25. Леонтьев В. К. Избранные задачи комбинаторного анализа. М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.

26. Лисковец В. А. Некоторые результаты комбинаторной теории перечисления графов. I. В сб.: Комбинаторный и асимптотический анализ, Красноярск, Издат. Красноярского университета, 1975, с. 9−36.

27. Лямин В. Н., Селиванов Б. И. Гипердеревья с заданным числом концевых вершин и ребер. Комбинаторный анализ, (1974), вып. 3, 68−71.

28. Маренич A.C. Решения уравнения w = -exp (z + w), их свойства и применения. Вычислительная математика и математическая физика. М., 1985, 32−42.

29. Медведев Ю. И., Ивченко Г. И. Асимптотическое представление конечных разностей от степенной функции в произвольной точке. -Теория вероятностей и ее применения, 1965, т. 10, № 1, 151−156.

30. О некоторых тенденциях теории перечисления. Гаврилов Г. П., Лисковец В. А., Пермяков П. П., Селиванов Б. И. В сб.: Перечислительные задачи комбинаторного анализа, Мир, М., 1979, с. 336−362.

31. Олвер Ф.

Введение

в асимптотические методы и специальные функции-М.: Наука, 1978. «.

32. Ope О. Теория графов. М, Наука, 1968.

33. Платонов М. Л. Комбинаторные числа класса отображений и их приложения. М.: Наука, 1979.

34. Прудников А. П. и др. Интегралы и ряды, т. 1. -М: Наука ГРФМЛ, 1981.

35. Прудников А. П. и др. Интегралы и ряды, т. 2. -М: Наука ГРФМЛ, 1983.

36. Прудников А. П. и др. Интегралы и ряды, т. 3. -М: Наука ГРФМЛ, 1986.

37. Риордан Дж., Введение в комбинаторный анализ. ИЛ, М. 1963.

38. Риордан Дж., Комбинаторные тождества. Наука, ГРФМЛ, М. 1982.

39. Сачков В. Н., Введение в комбинаторные методы дискретной математики. МЦНМО, М. 2004.

40. Степанов В. Е. Несколько теорем относительно случайных графов. Вероятностные методы в дискретной математике. Петрозаводск, 1983, с. 90−92.

41. Уиттекер Э. Т., Ватсон Дж. Курс современного анализа, т. 1, ГИФМЛ, М.: 1963.

42. Федорюк М. В. Метод перевала. Наука. ГРФМЛ, М., 1977.

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

44. Цветкович Д., Дуб М., Захс X. Спектры графов. Теория и применение. Киев, Наукова думка, 1984.

45. Adam A. A., Broere J. Chromatic polynomials of graphs in terms of trees. J. Math. Phys. Sci. 27(1993), 231−240.

46. Bender E.A. Central and local limits theorems applied to asymptotic enumeration. J. Combin. Theory, A15(1973), 91−111.

47. Bender E.A. An asymptotic expansion for the coefficients of some formal power series // J. London Math. Soc. (2). 1975. V. 9. 451−458.

48. Bender E.A., Richmond L.B. Central and local limits theorems applied to asymptotic enumeration II. Multivariate generating functions. J. Combin. Theory, A34(1983), 255−265.

49. Bender E.A., Richmond L.B. An asymptotic expansion for the coefficients of some power series. II // Discrete Math. 1984. V. 50, N2/3, 135−141.

50. Biggs N. Algebraic graph theory. London, Cambridge univ. press, 1974.

51. Bodirsky M., Gropl C., Kang M. Generating labeled planar graphs uniformly at random, in ICALP 2003, pp. 1095−1107, Springer, Berlin, 2003.

52. Bollobas B. Random graphs, London a.o., Academic Press, 1985.

53. Brown T.J.N., Mallion R.B., Pollak P., Roth A. Some methods for counting in labelled molecular graphs, examined in relation to certain fullerenes. Discrete Appl. Math. 67(1996), 51−66.

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

55. Comtet L. Analyse combinatoire. I. Paris: Presses Universitaires de France, 1970.

56. Fan Chung, Yau S.-T. Coverings, heat kernels and spanning trees. Electronic J. Combin. 6(1999), #R12.

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

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

59. Flajolet Ph., Sedgewick R. Analytic combinatorics, Web edition, 2008.

60. Ford G.W., Uhlenbeck G.E., Combinatorial problems in the theory of graphs. I. Proc. Nat. Acad. Sci. USA, (1956), 42, 122−128.

61. Gould H.W. Combinatorial identities. Morgantown, West Wirg. Univ., 1972.

62. 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, 451−463.

63. Harary F., Manvel B. On the number of cycles in graph. Matematicky casopis, 1971, v. 21, No. l, 55−63.

64. Harary F., Schwenk A J. The number of caterpillars. Discrete Math. 6(1973), № 4, 359−365.

65. Jakobson D., Rivin I. On some extremal problems in graph theory. Preprint, arXiv: math/990 7050vl math.CO. 8 Jul 1999.

66. Janson S., Luczak T., Rucinski A. Random graphs, N.Y. a.o., Wiley, 2000.

67. Janson S. Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas. Probability Surveys, 4(2007), 80−145.

68. Jin Y.-L., Tazawa S., Shirakura T. Enumeration of connected graphs with cut vertices. J. Statistical Planning and Inference 106(2002), 409−418.

69. Koutras M. Non-central Stirlingnumbers and some applications. Discrete Math. 42(1982), 73−89.

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

71. Lewis R.P. The number of spanning trees of a complete multipartite graphs. Discrete Math., 197/198(1999), 537−541.

72. Li Z., Liu Y. Chromatic sums of general simple maps on the plane. Utilitas Math. 68(2005), 223−237. •.

73. Linial N. Graph coloring and monotone functions on posets. Discrete Math. 58(1986), 97−98.

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

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

76. Lord R.D. Some integrals involving Hermite polynomials // J. London Math Soc., 1949. v. 24, part 2, № 94, 101−112.

77. McKay B.D. Spanning trees in regular graphs. Europ. J. Combinatorics, 4(1983), 149−160. .-мок.

78. Meir A., Moon J.W. On nodes of degree two in random trees. Mathematika, 15(1968), 188−192.. v ,.

79. Moon J.W. Counting labeled trees. In: Graph Theory and Theoretical Physics. Academic Press. N.Y., 1967, 261−267.

80. Moon J.W. A problem on random trees. J. Comb. Theory (1971) 10, № 3, 201−205.

81. Myrvold W. Reliable network synthesis: some recent developments. Proc. 8th international confer, on graph theory, combinatorics, algorithms and applications, 1999, v.2, p. 650−660.

82. Pittel В., Wormald N.C. Counting connected graphs inside-out. -J. Combin. Theory, ser. B, 93(2005), № 2, 127−172.

83. 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.

84. Read R.C. The enumeration of locally restricted graphs. I // J. London Math Soc., 1959. v. 34, 417−436.

85. Read R.C. An introduction to chromatic polynomials. J. Combin. Theoiy, 4(1968), 52−71.

86. Read R.C. Some unusual enumeration problems. Ann. N.-Y. Acad. Sci., 1970, V. 175, Art. 1,314−326.

87. Ren H., Liu Y. Counting rooted eulerian maps on the projective plane. -Acta Mathematica Scintia, 20B (2) (2000), 169−174.

88. Selkow S.M. The enumeration of labeled graphs by number of cutpoints. Discrete Math. (1998), 185, 183−191.

89. Tan Z., Gao S., Niederhausen H. Enumeration of (0,l)-matrices with constant row and column sums. Appl. Math. J. Chinese Univ. Ser. B, 21(4)(2006), 479−486.

90. Tutte W.T. Chromatic sums for rooted planar triangulations. IV. The case /1 = oo. Canad. J. Math., 25(1979), 929−940.

91. WilfH.B. Which polynomials are chromatic? Colloq. Internaz. Sulle Teorie Combinatorie, Rome, 1976, 247−256.

92. Vukicevic D. Thorny graphs. I. Valence connectivities. MATCH Commun. Math.Comput.Chem., 55(2006), 73−82.

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

94. Wormald N.C. The asymptotic connectivity of labelled regular graphs. J. Combin. Theory, Ser. B, 31(1981), 156−187.

95. Wright E.M., A relationship between two sequences. Proc. London Math. Soc.,(3), (1967), 17, 296−304.

96. Wright E.M., The number of connected sparsely edged graphs. J. Graph Theory, 1(1977),' 317−330.

97. Wright E.M., The number of connected sparsely edged graphs. II. Smooth graphs and blocks. J. Graph Theory, 2(1978), 299−305.

98. Wright E.M. The number of connected sparsely edged graphs. Ill. J. Graph Theory. 1980. V. 4. N 4. P. 393−407.

99. Wright E.M. The number of connected sparsely edged graphs. IV. J. Graph Theory. 1983. V. 7. N 2. P. 219−229.i iii.

100. Wright E.M. Enumeration of smooth labelled graphs. // Proc. Roy. Soc. Edinburgh, 1981. A91, N ¾, 205−212.

101. Wright E.M. A quadratic recurrence of Faltung type. Math. Proc. Camb. Phil. Soc. 88(1980), 193.

102. Xiao-Dong Zhang A new bound for the complexity of a graph. Utilitas Mathematica 67(2005), 201−203.

103. Yang Ling-ling, Li Song-chen, Enumeration of special kind of labeled connected graphs. Trans. Tianjin Univ. (2004), 10, 233−235.

104. Ying-Lie Jin, Enumeration of labeled connected graphs and Euler graphs with only one cut vertex. Yokohama Math. J. (1997), 45, 125−134.

105. Воблый B.A. Асимптотическое перечисление графов некоторых типов. Дис. к.ф.-м.н. М., ВЦАН, 1985.

106. Воблый В. А. Асимптотическое перечисление помеченных связных разреженных графов с заданным числом висячих вершин. — Дискретный анализ, Новосибирск, 1985. Вып. 42, 3—14. Исправление опечатки: Дискретный анализ, вып. 44, с. 71.

107. Воблый В. А. О коэффициентах Райта и Степанова-Райта. Матем. заметки, т. 42, вып. 6, 1987, 854−862.

108. Воблый В. А. О вероятности появления графа-гусеницы среди случайных разреженных графов, тВероятностные методы в дискретной математике, Петрозаводск, 1988, с. 25−26.

109. Воблый В. А. О перечислении помеченных связных гомеоморфно несводимых графов. Матем. заметки 49(1991), № 3, 12−22.

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

111. Воблый В. А. Асимптотика числа общих кубических графов с помеченными вершинами и. ребрами Обозрение прикладной и промышленной математ., 2000, т. 7, вып. 1, с. 92 .

112. Воблый В. А. О перечислений" помеченных (2,4) бирегулярных графов — Материалы VII Международного семинара «Дискретная математика и ее приложения», М., МГУ, ч. II, 2001, с. 212.

113. Воблый В. А. Некоторые необходимые условия хроматичности многочлена. Дискретная математика, т. 13, вып. 1, 2001, 73−77. Исправление опечаток: Дискретная математика, т. 13, вып. 2, 159.

114. Воблый В. А. Интегральное представление и асимптотика для числа помеченных общих (2,к) бирегулярных графов — Материалы VIII Между-народного семинара «Дискретная математика и ее приложения», М., МГУ, 2004, с. 329−330.

115. Воблый В. А. Упрощение формул для числа g-существенных карт на поверхностях с малым родом. Обозрение прикладной и промышленной математики, 2004, т.11, вып. 2, 236−237.

116. Воблый В. А. Асимптотика числа кубических планарных карт. -Обозрение прикладной и промышленной математики, 2005, т. 12, вып. 4, 850−851.

117. Воблый В. А. Решение уравнения Селкова для энумератора помеченных связных графов по числу точек сочленения. Материалы IX Международного семинара «Дискретная математика и ее приложения», М., МГУ, 2007, 265−268.

118. Воблый В. А. Упрощение некоторых формул для числа карт на поверхностях. Математические заметки, т.83, вып.1, 2008, 14−23.

119. Воблый В. А. О перечислении помеченных связных графов по числу точек сочленения. Дискретная математика, т.20, вып.1, 2008, 52−63.

120. Воблый В. А. Асимптотика числа помеченных 3-связных графов. -Обозрение прикладной и промышленной математики, 2008, т. 15, вып.2, 237.

121. Воблый В. А. Простая верхняя оценка для числа остовных деревьев регулярных графов. Дискретная математика, т. 20, вып. 3, 2008, 1−4.