Авторефераты диссертаций >> Авторефераты - Разное

Pages: |

| 2 |

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

-- [ Страница 1 ] --

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК

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

На правах рукописи

ВОБЛЫЙ Виталий Антониевич

НЕКОТОРЫЕ ЗАДАЧИ ПЕРЕЧИСЛЕНИЯ

ПОМЕЧЕННЫХ СВЯЗНЫХ ГРАФОВ

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. Рид получил для числа помеченных общих (допускаются петли и кратные ребра) -регулярных графов выражение в виде скалярного произведения цикловых индексов композиций симме-трических групп: .