Математика/4.Прикладная математика.

 

                                                 К.п.н. Баранова Н. А.

                                                  Банникова Т. М.

Удмуртский государственный университет, Россия

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

Важным разделом теории графов является теория их перечисления. У истоков теории графов лежат работы А. Кэли по перечислению помеченных деревьев и связанных с ними химических структур, опубликованные в 1857-1889 гг. Однако только в пятидесятых годах прошлого века Кац [1] и Реньи [2] независимо перечислили помеченные связные унициклические графы. Г.Н.Багаев [3] в 1973 г. перечислил помеченные связные бициклические графы. В 1977 г. Райт [4] вывел разностное уравнение для производящей функции помеченных связных графов с заданным цикломатическим числом.

Селков [6] в 1998 г. вывел функциональное уравнение с частными производными для производящей функции помеченных связных графов по числу вершин и точек сочленения и нашел асимптотику для числа таких графов с большим количеством вершин и фиксированным числом точек сочленения. Решение уравнения Селкова в общем случае было неизвестно и оставался открытым вопрос  о нахождении асимптотики для числа помеченных связных графов с большим количеством вершин и большим числом точек сочленения.

При исследовании структуры связного графа применяется его упрощение  с помощью удаления вершин степени 2. Графы без вершин степени 2 называются гомеоморфно несводимыми. Помеченные гомеоморфно несводимые деревья перечислил  Рид   в 1970 г. В 1975 г.

 Джексон и Рейли   нашли производящую функцию для числа помеченных гомеоморфно несводимых графов. Отсюда с помощью теоремы Риддела-Гилберта можно получить производящую функцию для числа таких же связных графов.

 В диссертационном исследовании Воблого В.А.   рассматриваются связные гомеоморфно несводимые графы и использование метода сжатия-разжатия Г.Н.Багаева для их перечисления [3].  Воблый В. А. определяет суть метода следующим образом.

       Для перечисления графов заданного вида в каждом графе выделяется порожденный подграф с определенными структурными свойствами, который сжимается в особую вершину. Образовавшиеся графы, содержащие фиксированную (особую) вершину с заданной степенью, а также сжатые подграфы независимо перечисляются известными методами перечисления. Пе­речисление исходных графов завершается суммированием по всем возможным степеням особой вершины произведений числа сжатых подграфов, числа гра­фов, образовавшихся после сжатия, и числа способов     восстановления (разжа­тия) исходного графа.    Далее   он вводит понятия узла, называя узлом вершину графа степени большей или равной 3. Остановимся более подробно на формулировках теорем необходимых для использования данного метода.

Пусть   — число помеченных глад­ких графов с р вершинами,  из которых  – узлы, и ребрами. Введем  производящую  функцию

                       

 

 

ТЕОРЕМА 1. При    производящая функция                     

                                                                            

для числа связных гомеоморфно несводимых графов с  помеченными вершинами и  ребрами удовлетворяет со­отношению

                                     ,

где  — производящая функция чисел помеченных корневых деревьев:                          .

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

             .              

ТЕОРЕМА 2. При фиксированном , и  справед­лива асимптотическая формула      становления (разжа­тия) исходного графа.

            

 где  ,                          

а  – коэффициенты Степанова-Райта.

Литература:

1.                Katz L. Probability of indecomposability of a random mapping function. Annals of Math. Statistics 26(1955), 512-517.

2.                Renyi A. On connected graphs. I. –  Publ. Math. Inst. Hungar. Acad. Sci. 4(1959), 385-388.

3.                Багаев Г.Н. Случайные графы со степенью связности 2 – В сб.: Дис-кретный анализ, Новосибирск, 1973, вып. 22, 3-14.

4.                 Selkow S.M.  The enumeration of labeled graphs by number of cutpoints. Discrete Math. (1998), 185, 183-191.

5.                Воблый В.А.  О перечислении помеченных -бирегулярных графов – Материалы VII  Международного семинара  «Дискретная  математика  и  ее  приложения»,  М., МГУ,  ч. II,  2001,  с. 212.  J. Graph Theory, 1(1977), 317-330.

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