Авторефераты по всем темам >>
Авторефераты по разное
УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК
ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР имени А.А.Дородницына РАН
На правах рукописи
ВОБЛЫЙ Виталий Антониевич
НЕКОТОРЫЕ ЗАДАЧИ ПЕРЕЧИСЛЕНИЯ
ПОМЕЧЕННЫХ СВЯЗНЫХ ГРАФОВ
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. При верны формулы
, ,
где - многочлен Лагерра.
СЛЕДСТВИЕ 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. 13th 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.
Авторефераты по всем темам >>
Авторефераты по разное