авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

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

ТЕОРЕМА 5.3. При число имеет интегральное представление

,

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

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

, ,

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



Pages:   || 2 |
 

Похожие работы:










 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.