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

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

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

Pages:   || 2 |

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

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

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

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

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

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

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

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

Москва - 2008

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

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

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

Официальные оппоненты:

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

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

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

Ведущая организация: Институт системного

программирования РАН

Защита состоится “ “ февраля 2009 г. в “ “ час.

на заседании диссертационного совета Д 002.017.02

при Вычислительном центре имени А.А.Дородницына РАН

по адресу: 119333, г. Москва, ул. Вавилова, д.40.

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

Автореферат разослан “ “ _____________ 2009 г.

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

диссертационного совета,

д.ф.-м.н., профессор В.В. Рязанов

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

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

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

Обычно задачам перечисления помеченных графов уделяется мало внимания, так как они считаются более простыми по сравнению с непо-меченным случаем [1]. Но в ряде физических задач, как например, в классической статистической механике [2-4] используются именно помеченные графы, поэтому перечисление таких графов является акту-альной задачей. Хотя теория перечисления помеченных связных графов развивается уже в течение 50 лет, интерес к этой области перечислитель-ной комбинаторики не пропал, о чем говорят работы зарубежных иссле-дователей последних лет [5-9].

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

Результаты перечисления помеченных графов применяются для их случайной генерации и анализа эффективности алгоритмов[6].



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

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

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

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

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

а также в статистической физике.

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

Публикации. Материал диссертации опубликован в 8 статьях (все опубликованы в журналах из списка ВАК) и 8 тезисах докладов. Все статьи написаны без соавторов. В одной статье использованы идеи

Г.Н. Багаева.

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

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

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

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

Пусть , а , где – число помеченных блоков с вершинами. Очевидно, .

Йинг-Ли Джин и Селков нашли, что .

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

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

В работе из уравнения Селкова при выведено обыкновенное дифференциальное уравнение для : ,

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

Как следствие получено выражение для

.

Далее в работе найдено явное решение уравнения Селкова в виде формулы, содержащей энумератор помеченных блоков по числу вершин.

Затем дано комбинаторное доказательство этой формулы и получена следующая асимптотика для при .

Во второй главе рассматриваются связные гомеоморфно несводи-мые графы. Сначала излагается метод сжатия-разжатия Багаева [11]. Суть метода состоит в следующем.

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

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

Как эпизод прием сжатия-разжатия графов встречается у Муна,

а также у В.Н.Сачкова. В последнее время метод сжатия-разжатия находит применение за рубежом [5].

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

,

где — нецентральные числа Стирлинга второго рода, которые определяются с помощью производящей функции

.

Затем во второй главе перечисляются точно и асимптотически поме-ченные связные гомеоморфно несводимые разреженные графы.

Обозначим через число помеченных простых (связных) гомеоморфно несводимых графов с вершинами и ребрами, а через

– соответствующую экспоненциальную производящую функцию. Джексон и Рейли [12] вывели формулу

.

Кроме того, в силу теоремы Гильберта, .

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

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

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

,

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

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

.

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

где ,

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

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

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

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

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

,

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

Так как числа совпадают с нецентральными числами Стирлинга второго рода , то эта формула совпадает с формулой, полученной





во второй главе методом сжатия-разжатия.

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

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

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

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

,

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

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

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

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

Автором при получена асимптотика: .

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

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

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

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

Пусть – число помеченных 3-связных кубических графов с вершинами. Вормальд [19] получил формулу

,

где и при верна рекуррентность .

Автором при доказана асимптотика

.

Она совпадает с асимптотикой для , полученной Вормальдом другим путем.

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

, , .

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

.

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

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

,

,

,

где.

В работе получены, интегральные представления

,

,

.

С помощью метода расщепления Егорычева вводятся числа

.

При этом . Затем найдена производящая функция

из которой методом Бендера [21] получена асимптотика при

.

Эта асимптотика совпадает с асимптотикой, полученной Ридом в его диссертации (доказательство не опубликовано).

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

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

,

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

В качестве следствия найдены формулы

, ,

где – многочлен Лагерра. Получена также общая формула

где – гипергеометрическая функция Лауричеллы n переменных 2-го рода. Из интегрального представления для методом Лапласа при фиксированном и найдена асимптотика

.

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

,

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

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

, ,

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



Pages:   || 2 |
 

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










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

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