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

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

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР имени

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

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

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

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

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

АВТОРЕФЕРАТ

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

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

Москва - 2008

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

д. ф.-м. н., профессор

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

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

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

Обычно задачам перечисления помеченных графов уделяется мало внимания, так как они считаются более простыми по сравнению с непо-меченным случаем [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. , Springer, Berlin, 2003.

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

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

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

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. bin. 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. (V.

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

23. Malyshev V. binatorics 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 put. and Appl. Math., v, №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.

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

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

7. Воблый необходимые условия хроматичности много-

члена. Дискретная математика, т. 13, вып. 1, 2001, с. 73-77. Исправление опечаток: Дискретная математика, т. 13, вып. 2, с. 159.

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.

13. Воблый некоторых формул для числа карт на поверхностях. – Математические заметки, т.83, вып.1, 2008, с. 14-23.

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

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

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

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