Введение к работе
Актуальность темы.
Важным разделом теории графов является теория их перечисления, имеющая многочисленные приложения не только в математической кибернетике, но и в таких областях естествознания, как структурная химия и статистическая физика.
В химии важной является задача перечисления структур сложных соединений. В настоящее время перечислены только ациклические соединения, а также соединения, состоящие из простых циклических структур, с прикрепленными к ним древесными фрагментами. Однако общая проблема перечисления изомеров, содержащих блоки произ-вольной структуры, остается нерешенной [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 страниц.
Похожие диссертации на Некоторые задачи перечисления помеченных связных графов
