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

Размещено на http://www.allbest.ru/

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

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

АВТОРЕФЕРАТ

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

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

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-й доле. Получено интегральное представление

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

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

, ,

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

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

Пусть - регулярный граф степени с вершинами, а - число его остовных деревьев. Для максимального числа остовных деревьев графа известна простая оценка Кельманса -Бигса:

Известна также точная оценка Маккея [22]:

где

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

где .

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

В шестой главе рассматриваются задачи перечисления карт. Комбинаторные карты имеют приложения в теоретической физике (дискретная квантовая гравитация)[23], а также в стереохимии. В работе упрощены некоторые формулы для числа карт на поверхностях, полученные другими исследователями, и найдена соответствующая асимптотика.

Выведены два комбинаторных тождества

,

, ,

отсутствующие в известных сборниках таких тождеств.

Пусть - число общих корневых кубических планарных карт (допускаются петли и кратные ребра) с некорневыми вершинами, Лью [24] получил формулу:

С помощью первого тождества формула для существенно упрощена

,

затем из нее при с помощью формулы Стирлинга найдена асимптотика

.

Пусть

соответственно, производящие функции по числу ребер карты для числа - существенных карт на проективной плоскости, 1-существенных карт на торе и 1-существенных карт на бутылке Клейна. Хао, Каи и Лью [25] вывели следующие формулы:

где .

Обозначим через - производящую функцию по числу ребер карты для числа 2-существенных карт на бутылке Клейна. В. Лью и У. Лью [26] вывели формулу:

где .

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

, ,

Кроме того из этих формул найдена асимптотика числа рассматриваемых карт при .

, , ,

Большинство перечислительных задач, связанных с раскрасками графов, относятся к числу нерешенных задач. Однако еще Татт при исследовании хроматических сумм корневых планарных триангуляций нашел, что их энумерант является предельным случаем ( при ) производящей функции хроматических сумм. Эту связь использовали также Ли и Лью для перечисления общих простых карт на плоскости [27]. Поскольку коэффициентами в хроматических суммах графов служат их хроматические многочлены, важно исследовать условия хроматичности многочлена.

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

, .

Полученные необходимые условия хроматичности многочлена в ряде случаев оказываются сильнее уже известных условий Котляра и Хватала.

Основные результаты диссертации

1. Найдена явная формула для энумератора помеченных связных графов по числу вершин с заданным количеством точек сочленения. Получена асимптотика для числа помеченных связных графов с большим количеством вершин и большим количеством точек сочленения.

2. Выведена формула для энумератора помеченных связных гомеоморфно несводимых графов по числу вершин с заданным цикломатическим числом. Получена асимптотика для числа помеченных связных разреженных гомеоморфно несводимых графов с большим количеством вершин и фиксированным цикломатическим числом.

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

4. Получена асимптотика чисел, удовлетворяющих квадратичному разностному уравнению типа свертки. Найдены предельные значения для коэффициентов Райта и Степанова-Райта.

5. Найдены интегральные представления и асимптотика для числа помеченных кубических графов. Выведены явные формулы для числа помеченных -бирегулярных графов.

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

ЛИТЕРАТУРА

1. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

2. Иванчик И.И. Проблемы теории графов в статистической физике. Труды ФИАН, т. 106. М.: Наука, 1979, с. 3-89.

3. Калмыков Г.И. Древесная классификация помеченных графов. М.: Физматлит, 2003.

4. Калмыков Г.И. Каркасная классификация помеченных графов. М.: Научный мир, 2006.

5. 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.

6. Bodirsky M., Grцpl C., Kang M. Generating labeled planar graphs uniformly at random. In ICALP 2003, pp. 1095-1107, Springer, Berlin, 2003.

7. Flajolet P., Salvy B., Schaeffer G. Airy phenomena and analitic combina-torics of connected graphs. Electron. J. Combin. 11(2004), #34.

8. Leroux P. Enumerative problems inspired by Mayer`s theory of cluster integrals . Electron. J. Combin. 11(2004), #32.

9. Chae G.-B., Palmer E.M., Robinson R.W. Computing the number of labeled general cubic graphs. Discrete Math. 307(2007), 2979-2992.

10. Selkow S.M. The enumeration of labeled graphs by number of cutpoints.

Discrete Math. (1998), 185, 183-191.

11. Багаев Г.Н., Воблый В.А. Метод сжатия-разжатия для перечисления графов. - Дискретная математика, т. 10, вып. 4, 1998, с. 82-87.

12. Jackson D.M., Reilly J.W. The enumeration of homeomorphically irredu-cible labeled graphs. J. Combin. Theory(B), 19(1975), 272-286.

13 Read R.C. Some unusual enumeration problems. - Ann. N.-Y. Acad. Sci.,

1970, V. 175, Art. 1, 314-326.

14. Wright E.M. Enumeration of smooth labelled graphs. Proc. Roy. Soc.

Edinburgh, 1981. A91, N 3/4, 205-212.

15. Багаев Г. Н., Дмитриев Е. Ф. Перечисление связных двуцветных

графов. Комбинаторный анализ (1983), вып. 6, 58-64.

16. Janson S. Brownian excursion area, Wright`s constants in graph enumeration, and other Brownian areas. Probability Surveys, 4(2007), 80-145.

17. Flajolet P., Poblete P., Viola A. On the analysis of linear probing hashing. Algorithmica 22(1998), 490-515.

18. Wright E.M. The number of connected sparsely edged graphs. IV J. Graph Theory. 1983. V. 7. N 2. P. 219-229.

19. Wormald N.C. Enumeration of labelled graphs II: Cubic graphs with given connectivity. J. London Math. Soc. (2), 20(1979), 1-7.

20. Read R.C. The enumeration of locally restricted graphs. I J. London Math Soc., 1959. v. 34, 417-436.

21. Bender E.A. An asymptotic expansion for the coefficients of some formal power series // J. London Math. Soc. (2). 1975. V. 9. 451-458.

22. McKay B.D. Spanning trees in regular graphs. Europ. J. Combinatorics, 4(1983), 149-160.

23. Malyshev V.A. Combinatorics and probability of maps. In Asymptotic combinatotics with application to mathematical physics, Dordrecht a.o., Kluwer, 2002, 71-95.

24. Liu Y.P. A note on the number of cubic planar maps, Acta Mathematica Scintia, 12(1992), 282-285.

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. Liu W., Liu Y. Enumeration of three kinds of rooted maps on the Klein bootle. J. Appl. Math. & Computing 24(2007), 411-419.

27. Li Z., Liu Y. Chromatic sums of general simple maps on the plane. Utilitas Math. 68(2005), 223-237.

Публикации по теме диссертации

1. Воблый В. А. Асимптотическое перечисление помеченных связных

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

анализ , Новосибирск, 1985. вып. 42, с. 3-14.

2. Воблый В.А. О коэффициентах Райта и Степанова-Райта. - Матем. заметки, т. 42, вып. 6, 1987, с. 854-862.

3. Воблый В.А. О вероятности появления графа-гусеницы среди случайных разреженных графов. - Вероятностные методы в дискретной математике, Петрозаводск, 1988, с. 25-26.

4. Воблый В. А. О перечислении помеченных связных гомеоморфно несводимых графов. - Матем. заметки 49(1991), №3, с. 12-22.

6. Воблый В.А. Асимптотика числа общих кубических графов с помеченными вершинами и ребрами - «Обозрение прикладной и промышленной математ.», 2000, т. 7, вып. 1, с. 92 .

8. Воблый В.А. О перечислении помеченных - бирегулярных графов - Материалы VII Международного семинара «Дискретная математика и ее приложения», М., МГУ, ч. II, 2001, с. 212.

9. Воблый В.А. Интегральное представление и асимптотика для числа помеченных общих - бирегулярных графов - Материалы VIII Международного семинара «Дискретная математика и ее прило-жения», М., МГУ, 2004, с. 329-330.

10. Воблый В.А. Упрощение формул для числа g-существенных карт на поверхностях с малым родом. - Обозрение прикладной и промыш-ленной математики, 2004, т.11, вып. 2, с. 236-237.

11 . Воблый В.А. Асимптотика числа кубических планарных карт. - Обозрение прикладной и промышленной математики, 2005, т. 12, вып. 4, с. 850-851.

12. Воблый В.А. Решение уравнения Селкова для энумератора помечен-ных связных графов по числу точек сочленения. - Материалы IX Международного семинара «Дискретная математика и ее приложения», М., МГУ, 2007, с. 265-268.

14. Воблый В.А. О перечислении помеченных связных графов по числу точек сочленения. Дискретная математика, т.20, вып.1, 2008, с. 52-63.

15. Воблый В.А. Асимптотика числа помеченных 3-связных графов. -

Обозрение прикладной и промышленной математики, 2008, т.15, вып.2, с.237.

16. Воблый В.А. Простая верхняя оценка для числа основных деревьев регулярных графов. Дискретная математика, т. 20, вып. 3, 2008 , с. 47-50.

Размещено на Allbest.ur

...