Некоторые задачи перечисления помеченных связных графов
УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК
ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР имени А.А.Дородницына РАН
На правах рукописи
ВОБЛЫЙ Виталий Антониевич
НЕКОТОРЫЕ ЗАДАЧИ ПЕРЕЧИСЛЕНИЯ
ПОМЕЧЕННЫХ СВЯЗНЫХ ГРАФОВ
01.01.09 - дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
доктора физико-математических наук
Москва - 2009
Работа выполнена в отделе математических проблем распознавания и методов комбинаторного анализа Вычислительного центра имени А.А.Дородницына РАН
Научный консультант:
Доктор физ.-мат. наук, профессор ЛЕОНТЬЕВ В.К.
Официальные оппоненты:
Доктор физ.-мат. наук, профессор САПОЖЕНКО А.А.
Доктор физ.-мат. наук, профессор ГОРДЕЕВ Э.Н.
Доктор физ.-мат. наук СМЕТАНИН Ю.Г.
Ведущая организация: Институт системного
программирования РАН
Защита состоится 18 июня 2009 г. в 14-00 час.
на заседании диссертационного совета Д 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 страниц.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы и дается краткое содержание работы.
В первой главе исследуются помеченные связные графы с задан-ным числом вершин и точек сочленения.
Обозначим через – число помеченных связных графов с
вершинами, из которых
точки сочленения, а через
- соответствующую экспоненциальную производящую функцию:
.
Пусть , а
, где
– число помеченных блоков с
вершинами. Очевидно,
.
Йинг-Ли Джин [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. При верны формулы
,
,
где – многочлен Лагерра.