Некоторые задачи перечисления помеченных связных графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР имени А.А.Дородницына

На правах рукописи ВОБЛЫЙ Виталий Антониевич

НЕКОТОРЫЕ ЗАДАЧИ ПЕРЕЧИСЛЕНИЯ ПОМЕЧЕННЫХ СВЯЗНЫХ ГРАФОВ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

□03470642

Москва - 2009

003470642

Работа выполнена в отделе математических проблем распознавания и методов комбинаторного анализа Вычислительного центра имени А.А.Дородницына РАН

Научный консультант:

Доктор физ.-мат. наук, профессор ЛЕОНТЬЕВ В.К. Официальные оппоненты:

Доктор физ.-мат. наук, профессор САПОЖЕНКО А.А.

Доктор физ.-мат. наук, профессор ГОРДЕЕВ Э.Н.

Доктор физ.-мат. наук СМЕТАНИН Ю.Г.

Ведущая организация: Институт системного программирования РАН

Защита состоится " ^ ^ " 2009 г. в час.

на заседании диссертационного совета Д 002.017.02 при Вычислительном центре имени А.А.Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д.40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан " " _2009 г.

Ученый секретарь

диссертационного совета, д.ф.-м.н., профессор

В.В. Рязанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

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

В классической статистической механике неидеальных газов давление и плотность выражаются степенными рядами, коэффициенты, которых являются суммами по всем помеченным связным графам или по всем помеченным двусвязным графам с данным числом вершин [2,3]. При этом возникает задача генерации соответствующих графов. Для обозримости и систематизации структур таких графов используется эволюционная точка зрения [4]. В этом случае граф рассматривается не как статический объект, а как развивающийся с течением времени живой организм. Роль времени играет цикломатическое число графа. Таким образом, задача перечисления помеченных связных графов с заданным цикломатическим числом возникла из потребностей теоретической физики и она привлекает исследователей до настоящего времени [5].

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

унициклические графы. Г.Н.Багаев [8] в 1973 г. перечислил помеченные связные бициклические графы. В 1977 г. Райт [9] вывел разностное уравнение для производящей функции помеченных связных графов с заданным цикломатическим числом.

Селков [13] в 1998 г. вывел функциональное уравнение с частными производными для производящей функции помеченных связных графов по числу вершин и точек сочленения и нашел асимптотику для числа таких графов с большим количеством вершин и фиксированным числом точек сочленения. Решение уравнения Селкова в общем случае было неизвестно и оставался открытым вопрос о нахождении асимптотики для числа помеченных связных графов с большим количеством вершин и большим числом точек сочленения.

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

Рид [14] в 1970 г. вывел разностное уравнение для числа помеченных связных графов с заданными числами вершин и висячих вершин. Однако явные формулы им не были получены и оставался открытым вопрос об асимптотике числа таких графов с большим количеством вершин.

При исследовании структуры связного графа применяется его упрощение с помощью удаления вершин степени 2. Графы без вершин

степени 2 называются гомеоморфно несводимыми. Помеченные гомео-морфно несводимые деревья перечислил Рид [14] в 1970 г. В 1975 г.

Джексон и Рейли [15] нашли производящую функцию для числа помеченных гомеоморфно несводимых графов. Отсюда с помощью теоремы Риддела-Гилберта можно получить производящую функцию для числа таких же связных графов.

В то же время были неизвестны формулы для числа помеченных связных гомеоморфно несводимых графов с заданным цикломатическим числом, а также соответствующая асимптотика для графов с большим числом вершин (аналог результатов Райта [11]).

Таким образом, несмотря на многочисленные работы зарубежных исследователей, ряд важных вопросов современной теории перечисления помеченных связных графов оставался открытым, что и обусловило актуальность темы диссертации.

Цель работы состоит в развитии теории перечисления помеченных связных графов и в расширении ее связей с теорией специальных функций.

Методы исследований. В работе использованы методы теории графов, комбинаторного анализа, теории функций комплексного переменного и теории специальных функций.

Научная новизна. Все основные результаты диссертации являются новыми.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты могут найти применение для генерации помеченных графов и анализа эффективности алгоритмов, а также в статистической физике.

Анробацня работы. Основные результаты диссертации докладывались и обсуждались на семинаре отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного

Центра имени А.А.Дородницына РАН, на семинаре кафедры математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета, а также были представлены на Международных конференциях «Вероятностные методы в дискретной математике» (Петрозаводск, 1988, 2000, 2004), на Международных семинарах «Дискретная математика и ее применения»(Москва, 2001, 2004, 2007), на Всероссийских симпозиумах по прикладной и промышленной математике (Сочи, 2005, 2007).

Публикации. По теме диссертации опубликовано 16 работ, из них 12 - в журналах из списка ВАК (список работ приводится в конце автореферата). В единственной совместной работе Г.Н. Багаеву принадлежит общая схема метода сжатия-разжатия, а автору диссертации - конкретные результаты его применения.

Структура и объем работы. Диссертация состоит из введения, 6 глав и списка литературы, содержащего 121 название. Общий объем диссертации 138 страниц.

Во введении обосновывается актуальность темы и дается краткое содержание работы.

В первой главе исследуются помеченные связные графы с заданным числом вершин и точек сочленения.

Обозначим через - число помеченных связных графов с п вершинами, из которых т точки сочленения, а через Бт (г) -соответствующую экспоненциальную производящую функцию:

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

со

п

Пусть г) = £ (2)хт , а В (г) = £ Вп ; где 5п - ЧИСло

т=0 п=2

помеченных блоков с п вершинами. Очевидно, - В(г),

Йинг-Ли Джин [16] и Селков [13] нашли, что = 1). Кроме того, Селков [13] вывел следующее дифференциально-функциональное уравнение для 5(х, г) :

дБ дБ / 55

г--х— = гВ г + хг— + х(1 -х) —

дг дх \ дг дх

и получил асимптотику для £тл при и ® и фиксированном т.

ТЕОРЕМА 1.1. Производящая функция (г) при т > 1 удовлетворяет

обыкновенному дифференциальному уравнению

<(*) - тад = -Ут{/ах,Г- 2\а2,...,/т\ат) , т\

где (_/£,,•••> /§т) - многочлены разбиений Белла и

г г

СЛЕДСТВИЕ 1.1. Справедлива формула

= 1)2 .

После замены переменной 5(х, г) = Р[хг, г)

уравнение Селкова приобретает вид:

дР _/ ЭР ЭР — = 5 2 + ы — + м — & V Эм Эг

Это уравнение назовем модифицированным уравнением Селкова.

ТЕОРЕМА 1.3. Функция Hu>z) = Е^У", где

tr) = 0

P0(z)=B(4 Pt(z)=e^-B'(z)~ 1

Р = m > 2 ,

и m\dzm~2 V V ' >

удовлетворяет модифицированному уравнению Селкова .

Очевидно, Sm(z) = zmPm(z) .

ТЕОРЕМА 1.4. При m >2 верна формула

m 1т-2 ( . \

Sn{z) = (B\z)(eB'U -1Y , m > 2

mV ' ml dz V V ' >

В диссертации дано комбинаторное доказательство этой формулы,

независимое от уравнения Селкова.

ТЕОРЕМА 1.5. При и со и m = о(п) верна асимптотика

S (и-2) ( п\\(п-т)(п-т-1)

(и - /и - 2)! \т)

Отсюда при фиксированном m и п —> со получается

П2т 1)

асимптотика Селкова: ¿>т--- 2

т\

Основным результатом первой главы являются теоремы 1.4 и 1.5, они опубликованы в работе [40].

Во второй главе рассматриваются связные гомеоморфно несводимые графы. Сначала излагается метод сжатия-разжатия Г.Н.Багаева [31]. Следует отметить, что прием, идейно близкий методу сжатия-разжатия встречаются у Муна, а также у В.Н.Сачкова. В последнее время метод сжатия-разжатия находит применение за рубежом [17]. Суть метода состоит в следующем. Для перечисления графов заданного вида в каждом графе выделяется порожденный подграф с определенными структурными свойства-

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

Затем во второй главе перечисляются помеченные связные гомео-морфно несводимые разреженные графы, а также находится соответствующая асимптотика. При этом используются результаты Райта [10, 18] о перечислении помеченных гладких графов.

Вершину графа степени больше или равной 3 назовем узлом... Пусть У^(р,р + ц) — число помеченных гладких графов с р вершинами, из которых т - узлы, и (р + д) ребрами. Введем производящую функцию

ТЕОРЕМА 2.4. При д > 0 производящая функция

для числа ЯС(я, и+ <?) связных гомеоморфно несводимых графов с п ' помеченными вершинами и (п + д) ребрами удовлетворяет соотношению

п

где С('И') — производящая функция чисел помеченных корневых дере-

00 /1-1 II

вьев:

Пусть Нир(п) - число помеченных связных гомеоморфно несводимых унициклических графов с п вершинами, из которых р циклических,, тогда при п > 2р , как следствие, получена формула

ТЕОРЕМА 2.5. При фиксированном д, д>0, и и-><» справедлива асимптотическая формула

а ¿1Ч - коэффициенты Степанова-Райта.

Основным результатом второй главы являются теоремы 2.4 и 2.5, опубликованные в работе [30].

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

Назовем вершину связного графа внутренней, если она принадлежит его ядру. Обозначим через Ср{п,к) - число помеченных связных графов с

п вершинами, из которых к висячих, а р внутренних. Обозначим через Ур=Ср(р, 0) - число помеченных связных графов с р вершинами, среди которых нет висячих (число помеченных гладких графов с р вершинами).

ТЕОРЕМА 3.1. При любых р>Ъ и 0 <к<п-р верна формула

где Л" СО обобщенные числа Стирлинга 2-го рода по базе {к + .

Пусть с(п,п + ц,к) — число помеченных связных графов с п вершинами и п + д ребрами, причем к вершин - висячие.

ТЕОРЕМА 3.3. При фиксированных к> 0, д > 0 и и -» со справедлива

При доказательстве теоремы используется выведенное автором комбинаторное тождество:

Графом-гусеницей или колючим графом назовем граф, который становится гладким после однократного удаления висячих вершин вместе с инцидентными им ребрами.

ТЕОРЕМА 3.5. Пусть СС{п,п + ц) - число помеченных графов-гусениц с п вершинами и я + ^ ребрами, тогда при фиксированном д > 0 и п —> оо получена асимптотическая формула

где Ь = 0.5671... - корень уравнег я ге1 = 1, а - коэффициенты

Степанова-Райта.

Основным результатом третьей главы являются теорема 3.3, она опубликована в работе [27].

В четвертой главе находится асимптотика чисел, удовлетворяющих частному квадратичному разностному уравнению типа свертки, и рассматриваются ее приложения.

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

асимптотическая формула с(п, п + д,к)~ Ркцпгк*"] 'л!,

Райта.

(2к + д-2).\ (*-1)?!!

названы Г.Н. Багаевым коэффициентами Степанова-Райта. Они определяются следующим образом

4 =¿2—, <+,=4+1

36 -'(« + !)

п

Коэффициенты Степанова-Райта называются за рубежом константами Райта и числами Райта-Лушара-Такача, они применяются также в теории броуновского блуждания [20] и теории хэширования [21].

Райт нашел приближенное значение предела, к которому стремятся эти коэффициенты при л -»со , а Г.Н. Багаев и Е.Ф. Дмитриев [19] пред-1

положили, что ап -» — при п —> оо. 1п

В теореме 4.3 эта гипотеза доказана. Кроме того, для коэффициентов Степанова - Райта выведено линейное разностное уравнение.

Райт [12] выразил асимптотику числа помеченных блоков с помощью следующих чисел, которые назовем коэффициентами Райта :

I. 1 I. 5 '

о, =—, О, = — и при к> 2 выполнено 12 2 48 Р

2(к + 1К+, = (3к + 2\кЪк + 32>(* - *У>,Ьк„ •

V 1=1 /

ТЕОРЕМА 4.5. При п со верна асимптотическая формула

В заключение рассматривается квадратичное разностное уравнение типа свертки

п

а„+| =(п + а)а„ ,п>0,а0=а,

1=0

обобщающее разностное уравнение для коэффициентов Степанова-Райта.

Найдена асимптотическая формула при 2 уа0 + а -1 > 0 и п —> х> а„--.

Как следствие этой формулы получается асимптотика для коэффициентов Степанова-Райта.

Основным результатом четвертой главы являются теоремы 4.3 и 4.5, они опубликованы в работе [28].

В пятой главе исследуются регулярные и бирегулярные графы . Пусть СР„ , СМ„ и С, - соответственно, число кубических псевдографов, число кубических мультиграфов и число простых кубических графов с 2п помеченными вершинами. Рид [22] получил формулы

6" t¿f¿(3¡-jy.(2i-jy.j\{n-iyл&l ' {2„)\ " " {-\У(61~2])\6'

6" t¿pй(Зi-j)K2i-jУj\(n-iУA8■ с =(2пУ у f {-\У{Ы-2])\У Л, (у)

" А" ¿-'¿-41; . ;

б" яи^-мп-л^мп^ум''

где =

ТЕОРЕМА 5.1. Числа С„, СМ„ и С/'„ имеют, соответственно, интегральные представления

/ 1

3/

3 2Шг-1

л,

/ 1

3?

3 2ДЗ* + 1

3/

А,

Л .

ч3 2ЛЗ/ + 1^

Следуя Риду, назовем (р,ц) - бирегулярным графом двудольный граф, у которого все вершины из 1-й доли имеют степень р, а из 2-й доли

- степень q. Рид получил для числа помеченных общих (допускаются петли и кратные ребра) (р, q) -регулярных графов выражение в виде скалярного произведения цикловых индексов композиций симметрических групп: N{Z(Eqnlh[Sp]yZ(Ep„/l<[Sq])} .

Пусть Ln (&)- число помеченных общих (2,к)-бирегулярных графов с кп вершинами в 1-й доле и 2п вершинами во 2-й доле.

ТЕОРЕМА 5.3. При к > 2 число Ln(k) имеет интегральное представление где

- многочлен Эрмита, a i - мнимая единица. СЛЕДСТВИЕ 5.1. При п > 2 верны формулы 4<2) = (2„„2„„С-»(1) , Ц ».Wy'fg) ,

где L" (х) - многочлен Лагерра. СЛЕДСТВИЕ 5.2. При к > 2 верна формула

* (*)= FH--,Ы,...,!^;!-^;-!,... ,.1

п\ ) 2 ы^уп ^ 2 2 2 2 2

где Fgn)- гипергеометрическая функция Лауричеллы п переменных 2-го рода.

Пусть Мл(к)~ число помеченных без кратных ребер (2,к)-бирегу-лярных графов с кп вершинами в 1-й доле и 2п вершинами во 2-й доле. ТЕОРЕМА 5.4. При к> 2 число Мп(к) имеет интегральное представление:

(кп)\ °°г 2

М (к)= ,_ , „ \е~х Hl"(x)dx, где НЛх) - многочлен Эрмита. 4ж2 (к\) _*, * *

СЛЕДСТВИЕ 5.3. При п> 2 верны формулы

M„(2) = (2«)!(2«)!L-—(4) , ,

где La„(x) - многочлен Лагерра.

Число остовных деревьев графа является важной характеристикой его надежности как сети для передачи информации. В химии число остовных деревьев молекулярного графа связано с физическими свойствами сложного соединения.

ТЕОРЕМА 5.6. Для числа остовов T(G) регулярного графа G степени к с п вершинами верна оценка сверху

T(G) <—к"~* ехр п

( 2кг+2к-\ А --5-п

„ „ 137/60

, где с = е

4 к'

Эта оценка является асимптотически точной для бесконечной последовательности полных 5 -дольных графов.

Основным результатом пятой главы являются теорема 5.3 и следствие 5.2, они опубликованы в работах [34,35].

В шестой главе рассматриваются задачи перечисления карт. Картой называется связный граф в, вложенный в поверхность 5 так, что все компоненты 5-в гомеоморфны открытым дискам. Карта М на поверхности 5 называется g -существенной, если для любого ребра е карта м-е либо не является картой, либо эта карта не может быть уложена на поверхности . Карты имеют приложения в теоретической физике [24], а также в стереохимии.

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

со

Пусть - производящая функция по числу ребер карты

п=2

1-существенных карт на бутылке Клейна. Хао, Каи и Лью [25] вывели следующую формулу:

■*кУ> ^5! ("-'") (и + 2)(и + 1)

гдеЛ1.(п) = 50п2- 8и(/ -18)-г2 - 21г + 82 .

Автором доказаны два комбинаторных тождества : , -/т -2л + Г

I

г '2п + Т

—2"' = 2'"'

/ + 1

я > 0,

С помощью первого из этих тождеств вычислена сумма в формуле для кп .

ТЕОРЕМА 6.6. При п > 3 верна формула

= (5,-2)(2,)!_и22„_З " 12(и - \)\п\

Отсюда следует асимптотика числа рассматриваемых карт :

5 3

и2 2 , при да

Большинство перечислительных задач, связанных с раскрасками графов, относятся к числу нерешенных задач. Однако еще Татт при исследовании хроматических сумм корневых планарных триангуляций нашел, что их энумерант является предельным случаем ( при Я = °о ) производящей функции хроматических сумм. Эту связь использовали также Ли и Лью для перечисления общих простых карт на плоскости [26]. Поскольку коэффициентами в хроматических суммах графов служат их хроматические многочлены, важно исследовать условия хрома-тичности многочлена.

р

ТЕОРЕМА 6.11. Пусть Р((},Х) - ^а/-' - хроматический многочлен

у-о

связного графа вер помеченными вершинами. Тогда для любого

у' = 1 ,...,р выполняется неравенство: (-1 ) > ак> 0 .

р

ТЕОРЕМА 6.12. Пусть = - хроматический многочлен

1=0

связного графа Ос р помеченными вершинами. Тогда для любого / = 1 ,...,р выполняется неравенство

Р(С,з) .

Доказано, что полученные необходимые условия хроматичности многочлена в ряде случаев сильнее уже известных условий Котляра и Хватала.

Основными результатами шестой главы являются теоремы 6.2-6.7 и 6.9, 6.10, они опубликованы в работах [36,39].

Основные результаты диссертации

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

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

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

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

5. Выведены интегральные представления, а также явные формулы для числа помеченных (2,£)-бирегулярных графов.

6. Доказаны формулы для числа карт различных типов на поверхностях и получена соответствующая асимптотика.

ЛИТЕРАТУРА

1. Read R.C. Chemistry and discrete mathematics. Discrete Appl. Math. 67(1996), 1-4.

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

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

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

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

6. Katz L. Probability of indecomposability of a random mapping function. Annals of Math. Statistics 26(1955), 512-517.

7. Renyi A. On connected graphs. I. - Publ. Math. Inst. Hungar. Acad. Sci. 4(1959), 385-388.

8. Багаев Г.Н. Случайные графы со степенью связности 2 - В сб.: Дискретный анализ, Новосибирск, 1973, вып. 22, 3-14.

9. Wright Е.М. The number of connected sparsely edged graphs. J. Graph Theory, 1(1977), 317-330.

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

11. Wright E.M. The number of connected sparsely edged graphs. Ill. J. Graph Theory. 4(1980), N 4, 393-407.

12. Wright E.M. The number of connected sparsely edged graphs. IV. J. Graph Theory. 7(1983), N 2, 219-229.

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

14. Read R.C. Some unusual enumeration problems. - Ann. N.-Y. Acad. Sci.,

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

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

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

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

18. Wright E.M. Enumeration of smooth labelled graphs. Proc. Roy. Soc. Edinburgh, 1981. A91, N 3/4, 205-212.

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

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

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

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

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

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

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

26. Li 2, Liu Y. Chromatic sums of general simple maps on the plane. Utilitas Math. 68(2005), 223-237.

Публикации по теме диссертации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подписано в печать 02.04.2009 Формат бумаги 60x84 1/16 Уч.-изд. л.0,9 Усл.-печ. 1,25 Тираж 100 экз. Заказ 8

Отпечатано на ротапринтах в Учреждении Российской академии наук Вычислительный центр им. A.A. Дородницына РАН 119991, Москва, ул. Вавилова, 40