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

Размещено на http://www.Allbest.ru/

Размещено на http://www.Allbest.ru/

Учреждение российской академии наук вычислительный центр имени А.А. Дородницына РАН

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

АВТОРЕФЕРАТ

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

Тема:

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

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

Москва - 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 страниц.

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

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

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

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

Пусть , а ,

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

Йинг-Ли Джин [16] и Селков [13] нашли, что

Кроме того, Селков [13] вывел следующее дифференциально-функциональное уравнение для :

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

Теорема 1.1 Производящая функция при удовлетворяет обыкновенному дифференциальному уравнению

,

где - многочлены разбиений Белла и

Следствие 1.1 Справедлива формула

После замены переменной

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

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

Теорема 1.3 Функция , где

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

Очевидно,

Теорема 1.4 При верна формула

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

Теорема 1.5 При и верна асимптотика

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

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

Суть метода состоит в следующем.

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

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

Вершину графа степени больше или равной 3 назовем узлом.

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

Теорема 2.4 При производящая функция

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

,

где -- производящая функция чисел помеченных корневых деревьев:

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

Теорема 2.5 При фиксированном , и справедлива асимптотическая формула

где ,

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

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

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

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

Теорема 3.1 При любых и верна формула

,

где обобщенные числа Стирлинга 2-го рода по базе .

Пусть - число помеченных связных графов с вер-шинами и ребрами, причем вершин - висячие.

Теорема 3.3 При фиксированных , и справедлива асимптотическая формула

,

где ,

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

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

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

Теорема 3.5 Пусть - число помеченных графов-гусениц с вершинами и ребрами, тогда при фиксированном и получена асимптотическая формула

,

где - корень уравнения , а - коэффициенты Степанова-Райта.

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

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

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

интегральный асимптотика помеченный геоморфный граф

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

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

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

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

Теорема 4.5 При верна асимптотическая формула

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

, , ,

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

Найдена асимптотическая формула при и

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

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

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

,

,

,

где.

Теорема 5.1 Числа , и имеют, соответственно, интегральные представления

,

,

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

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

Теорема 5.3 При число имеет интегральное представление

,

где - многочлен Эрмита, а i - мнимая единица.

Следствие 5.1 При верны формулы

, ,

где - многочлен Лагерра.

Следствие 5.2. При верна формула

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

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

Теорема 5.4 При число имеет интегральное представление:

, где - многочлен Эрмита.

Следствие 5.3 При верны формулы

,

,

где - многочлен Лагерра

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

Теорема 5.6 Для числа остовов регулярного графа степени с вершинами верна оценка сверху

, где

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

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

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

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

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

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

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

Где

Автором доказаны два комбинаторных тождества: ,

, ,

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

Теорема 6.6 При верна формула

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

, при

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

Теорема 6.11 Пусть - хроматический многочлен связного графа с помеченными вершинами. Тогда для любого выполняется неравенство: .

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

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

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 E.M. 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. III. 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 irredu-cible 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. 13^th 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), 80-145.

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 Z., 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. Воблый В.А. О перечислении помеченных -бирегулярных графов - Материалы VII Международного семинара «Дискретная математика и ее приложения», М., МГУ, ч. II, 2001, с. 212.

35. Воблый В.А. Интегральное представление и асимптотика для числа помеченных общих - бирегулярных графов - Материалы 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.

Размещено на Allbest.ru

...