Исследование помеченных связных графов с заданным числом вершин и точек сочленения. Выведение формулы для энумератора разреженных гомеоморфно несводимых графов с заданным цикломатическим числом. Определение их асимптотики и интегральных представлений.
Важным разделом теории графов является теория их перечисления, имеющая многочисленные приложения не только в математической кибернетике, но и в таких областях естествознания, как структурная химия и статистическая физика. В классической статистической механике неидеальных газов давление и плотность выражаются степенными рядами, коэффициенты, которых являются суммами по всем помеченным связным графам или по всем помеченным двусвязным графам с данным числом вершин [2,3]. Таким образом, задача перечисления помеченных связных графов с заданным цикломатическим числом возникла из потребностей теоретической физики и она привлекает исследователей до настоящего времени [5]. Селков [13] в 1998 г. вывел функциональное уравнение с частными производными для производящей функции помеченных связных графов по числу вершин и точек сочленения и нашел асимптотику для числа таких графов с большим количеством вершин и фиксированным числом точек сочленения. Решение уравнения Селкова в общем случае было неизвестно и оставался открытым вопрос о нахождении асимптотики для числа помеченных связных графов с большим количеством вершин и большим числом точек сочленения.Обозначим через - число помеченных связных графов с вершинами, из которых точки сочленения, а через - соответствующую экспоненциальную производящую функцию: Пусть , а , где - число помеченных блоков с вершинами. Обозначим через - число помеченных связных графов с вершинами, из которых висячих, а внутренних. Обозначим через - число помеченных связных графов с вершинами, среди которых нет висячих (число помеченных гладких графов с вершинами). Теорема 3.5 Пусть - число помеченных графов-гусениц с вершинами и ребрами, тогда при фиксированном и получена асимптотическая формула Рид получил для числа помеченных общих (допускаются петли и кратные ребра)-регулярных графов выражение в виде скалярного произведения цикловых индексов композиций симметрических групп: Пусть - число помеченных общих (2,k)-бирегулярных графов с kn вершинами в 1-й доле и 2n вершинами во 2-й доле.
План
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
