WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

 

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

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

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

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

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

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

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

  АВТОРЕФЕРАТ

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

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

Москва - 2009

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

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

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

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

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

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

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

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

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

Защита состоится  18 июня 2009 г.  в 14-00  час.

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

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

по адресу: 119333, г. Москва, ул. Вавилова, д.40.

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

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

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

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

д.ф.-м.н., профессор  В.В. Рязанов

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

Актуальность темы.

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

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

  КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

  Во введении обосновывается актуальность темы и дается краткое содержание работы.

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

Обозначим через  – число помеченных связных графов с вершинами, из которых   точки сочленения, а через - соответствующую экспоненциальную производящую функцию:  .

Пусть  , а , где    – число помеченных блоков  с  вершинами. Очевидно,  .

  Йинг-Ли Джин [16] и Селков [13]  нашли, что

  .

  Кроме того, Селков [13]  вывел следующее  дифференциально-функциональное уравнение для :

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

ТЕОРЕМА 1.1. Производящая функция при   удовлетворяет обыкновенному дифференциальному уравнению

,

где – многочлены разбиений Белла  и .

  СЛЕДСТВИЕ 1.1. Справедлива формула

  .

  После замены переменной

уравнение Селкова приобретает вид:

.

Это уравнение назовем модифицированным уравнением  Cелкова.

ТЕОРЕМА 1.3.  Функция , где

удовлетворяет модифицированному уравнению Селкова .

Очевидно, .

ТЕОРЕМА 1.4. При   верна формула 

В диссертации дано комбинаторное доказательство этой формулы, независимое от уравнения Селкова.

ТЕОРЕМА 1.5. При и верна асимптотика . 

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

асимптотика Селкова: .

  Основным результатом первой главы являются теоремы 1.4 и 1.5, они опубликованы в работе [40].

  Во второй главе рассматриваются связные гомеоморфно несво-димые графы. Сначала излагается метод сжатия-разжатия Г.Н.Багаева [31]. Следует отметить, что прием, идейно близкий методу сжатия-разжатия встречаются  у Муна, а также у В.Н.Сачкова. В последнее время метод сжатия-разжатия находит применение за рубежом [17].

Суть метода состоит в следующем.

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

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

  Затем во второй главе перечисляются помеченные связные гомео-морфно несводимые разреженные графы, а также находится соответ-ствующая  асимптотика. При этом используются результаты Райта [10, 18] о перечислении помеченных гладких графов.

Вершину графа степени больше или равной 3 назовем узлом.

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

из которых – узлы, и ребрами. Введем  производящую  функцию

 

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

   

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

  ,

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

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

  .

ТЕОРЕМА 2.5. При фиксированном , и справед­лива асимптотическая формула

где ,

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

  Основным результатом второй главы являются теоремы 2.4 и 2.5,  опубликованные в работе [30].

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

Назовем вершину связного графа внутренней, если она принадлежит его ядру. Обозначим через – число помеченных связных графов с вершинами, из которых висячих, а внутренних. Обозначим через – число помеченных  связных  графов  с вершинами,  среди  которых  нет висячих (число помеченных гладких графов с вершинами).

ТЕОРЕМА 3.1. При  любых и верна  формула

  , 

где обобщенные числа Стирлинга 2-го рода по базе   .

  Пусть  –  число помеченных связных  графов с вер-шинами и    ребрами, причем  вершин –  висячие.

ТЕОРЕМА 3.3. При фиксированных , и справедлива асимптотическая формула  ,

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

  При доказательстве теоремы используется выведенное автором  ком-бинаторное тождество:

Графом-гусеницей или колючим графом назовем граф, который ста-новится гладким после однократного удаления висячих вершин вместе

с инцидентными им ребрами.

ТЕОРЕМА 3.5. Пусть – число помеченных графов-гусениц с вершинами и ребрами, тогда при фиксированном и получена асимптотическая формула

,

где – корень уравнения , а – коэффициенты Степанова-Райта.

Основным результатом третьей главы являются теорема 3.3, она опубликована в работе [27].

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

  В работах многих авторов асимптотика числа помечен­ных связ-ных разреженных графов выражается с помощью коэффициентов, зада-ваемых квадратичным рекуррентным соотношением. Эти коэффициенты названы Г.Н. Багаевым коэффи­циентами Степанова-Райта. Они опре-деляются следующим образом

 

Коэффициенты Степанова-Райта  называются за рубежом констан-тами Райта и числами Райта-Лушара-Такача, они применяются также в теории броуновского блуждания [20] и теории хэширования [21].

  Райт  нашел при­ближенное значение предела, к которому стремятся эти коэффициенты при , а Г.Н. Багаев и Е.Ф. Дмитриев [19] пред-положили, что при .

В теореме 4.3 эта гипотеза доказана. Кроме того, для коэффициентов Степанова - Райта выведено линейное разностное уравнение.

  Райт [12] выразил асимптотику числа помеченных блоков с помо-щью следующих чисел, которые назовем коэффициентами Райта :    и при выполнено

 

ТЕОРЕМА 4.5. При верна асимптотическая формула

.

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

  , , ,

обобщающее разностное уравнение для коэффициентов Степанова-Райта.

  Найдена асимптотическая формула при  и 

.

Как следствие этой формулы получается асимптотика для коэффи-циентов Степанова-Райта.

  Основным результатом четвертой главы являются теоремы 4.3 и 4.5, они опубликованы в работе [28].

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

,

,

,

где .

ТЕОРЕМА 5.1. Числа , и имеют, соответственно, интегральные представления

,

,

.

Следуя Риду, назовем  (p,q) – бирегулярным графом двудольный граф, у которого все вершины из 1-й доли имеют степень р, а из 2-й доли – степень q. Рид получил для числа помеченных общих (допускаются петли и кратные ребра) -регулярных графов выражение в виде скалярного произведения цикловых индексов композиций симме-трических групп:  .

Пусть  - число помеченных общих  (2,k)-бирегулярных графов с  kn  вершинами  в 1-й доле и 2n вершинами во 2-й доле. 

ТЕОРЕМА 5.3. При число имеет интегральное представление

где    -  многочлен  Эрмита,  а  i – мнимая единица .

СЛЕДСТВИЕ 5.1. При верны формулы

, , 

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

СЛЕДСТВИЕ 5.2. При верна формула

где  –  гипергеометрическая  функция Лауричеллы  n  переменных

2-го рода.

Пусть – число помеченных без кратных ребер (2,k)-бирегу-лярных графов с  kn  вершинами  в 1-й доле и 2n вершинами во 2-й доле. ТЕОРЕМА 5.4. При число имеет интегральное представ-ление:

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

СЛЕДСТВИЕ 5.3. При верны формулы

  ,  , 

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

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

ТЕОРЕМА 5.6. Для числа остовов регулярного графа   степени с вершинами  верна оценка сверху

, где . 

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

  Основным результатом пятой главы являются теорема 5.3 и  следст-вие  5.2,  они опубликованы в работах [34,35].

В шестой главе рассматриваются задачи перечисления карт.

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

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

Пусть – производящая функция по числу ребер карты 

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

где .

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

  ,

  , ,

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

ТЕОРЕМА 6.6.  При верна формула

  . .

Отсюда следует асимптотика числа рассматриваемых карт :

  , при .

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

ТЕОРЕМА  6.11.  Пусть ­– хроматический многочлен связного графа с помеченными вершинами. Тогда для любого выполняется неравенство: .

ТЕОРЕМА 6.12. Пусть ­– хроматический многочлен связного графа с помеченными вершинами. Тогда для любого выполняется неравенство

  .

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

  Основными результатами шестой главы являются теоремы  6.2-6.7 и 6.9, 6.10,  они опубликованы в работах [36,39].

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

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

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

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

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

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

6. Доказаны формулы для числа карт различных типов на поверхностях и получена соответствующая асимптотика.

Л И Т Е Р А Т У Р А

1. Read R.C. Chemistry and discrete mathematics. Discrete Appl. Math. 67(1996), 1-4.

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

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

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

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

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

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

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

9.  Wright E.M. The number of connected sparsely edged graphs.

J. Graph Theory, 1(1977), 317-330.

10. Wright E.M. The number of connected sparsely edged graphs. II. Smooth graphs and blocks. J. Graph Theory, 2(1978), 299-305.

11. Wright E.M. The number of connected sparsely edged graphs. III .

J. Graph Theory. 4(1980), N 4, 393-407.

12. Wright E.M. The number of connected sparsely edged graphs. IV .

J. Graph Theory. 7(1983), N 2, 219-229.

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

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

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

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

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

16.Ying-Lie Jin, Enumeration of labeled connected graphs and Euler graphs with only one cut vertex. Yokohama Math. J. 45(1997), 125-134.

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

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

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

19. Багаев Г.Н., Дмитриев Е.Ф. Перечисление связных  отмеченных двудольных графов // ДАН БССР. 1984. Т. 28, № 12, с. 1061 – 1063.

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

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

22. Read R.C.  The  enumeration  of  locally  restricted  graphs.  I 

J. London  Math  Soc., 1959. v. 34,  417-436.

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

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

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. Li Z., Liu Y. Chromatic sums of general simple maps on the plane. Utilitas Math. 68(2005), 223-237.

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

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

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

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

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

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

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

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

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

33. Воблый  В.А. Некоторые необходимые условия хроматичности многочлена. Дискретная математика, т. 13, вып. 1, 2001, с. 73-77.

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

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

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

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

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

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

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

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

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

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






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.