На правах рукописи
Исаев Михаил Исмаилович
АНАЛИТИЧЕСКИЙ ПОДХОД К ЗАДАЧАМ
ПЕРЕЧИСЛЕНИЯ ГРАФОВ СО
СПЕКТРАЛЬНЫМИ ОГРАНИЧЕНИЯМИ
01.01.09 Дискретная математика и
математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва 2013
Работа выполнена на кафедре математических основ управления Московского физико-технического института (государственного университета)
Научный руководитель: кандидат физико-математических наук Тарасов Сергей Павлович
Официальные оппоненты: доктор физико-математических наук, профессор Сапоженко Александр Антонович, кафедра математической кибернетики Московского государственного университета им. М.В. Ломоносова, профессор кандидат физико-математических наук Соболевский Андрей Николаевич, Институт проблем передачи информации им. А.А. Харкевича РАН, заместитель директора по научной работе
Ведущая организация: Центральный экономикоматематический институт РАН
Защита состоится 2013 года в часов минут на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.
С диссертацией можно ознакомиться в библиотеке Московского физикотехнического института (государственного университета).
Автореферат разослан 2013 г.
Ученый секретарь диссертационного совета Федько О.С.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы.
Перечисление графов является важным разделом теории графов, имеющим многочисленные приложения в химии, статистической физике, кибернетике и др. областях. Первые существенные шаги в теории перечисления графов были сделаны ещё в девятнадцатом столетии. В своих работах, опубликованных в 1857 1889 гг., Кэли А. получил формулы для количества деревьев трех типов: помеченных, корневых и обычных, а также связанных с ними химических структур. Еще ранее Кирхгоф Г. получил в неявной форме число различных остовных деревьев заданного графа, а значит, в частности, число помеченных деревьев.
В настоящее время перечисление графов представляет собой развитую теорию, занимающую существенное место в области комбинаторного анализа. В монографии Harary F. и Palmer E. приведено большое количество разнообразных задач перечисления непомеченных графов с определенными свойствами. Для задач такого типа используется алгебраический подход, основанный на теории перечисления Пойа. Принцип включения и исключения, обращение Мёбиуса, а также многие другие известные методы, подробно изложены в книгах Stanley R.P. по перечислительной комбинаторике.
Во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики, и, в частности, интерес к алгоритмическим аспектам теории графов. Стоит отметить вклад Valiant L.G., определившего понятие P -полноты, с помощью которого удалось объяснить вычислительную сложность некоторых проблем перечисления графов.
После 1970-х много внимания уделялось асимптотическим оценкам и взаимосвязи между задачами перечисления и теорией случайных графов. В работах Эрдеша П. и Bollobas B. можно найти более подробную информацию об этом вероятностном подходе.
Аналитические методы, безусловно, относятся к числу наиболее мощных методов комбинаторного анализа. Они основываются на точном описании перечисляемых комбинаторных объектов с помощью производящих функций. Эти функции интерпретируются как аналитические объекты, то есть как отображения комплексной плоскости в себя. Их особенности определяют (асимптотически) коэффициенты производящих функций и позволяют получить оценки членов исходных последовательностей. В книге Flajolet P., Sedqewick R. по аналитической комбинаторике тщательно изложены основные известные к настоящему времени аналитические методы решения задач комбинаторного анализа, а также рассмотрены различные приложения этого подхода.
Теория перечисления графов интенсивно развивается, и интерес к этой области перечислительной комбинаторики постоянно возрастает, о чем говорят многочисленные работы последних лет отечественных и зарубежных исследователей: Багаев Г.Н., Воблый В.А., Ландо С.К, Леонтьев В.К., Звонкин А.К., Barvinok A., Bezkov I., Brightwell G., Chebulu P., Creed P., Cryan M., Hartigan J., Greenhill C., Grohe M., Martin R., McKay B.D., Stefankovi D., Vazirani D., Vigoda E., Winkler P., Zhang J. и др.
Хотя аналитический подход достаточно хорошо изучен в литературе, он продолжает приносить новые интересные результаты даже в классических задачах. В рассмотренных задачах перечисления этот подход позволяет получить достаточно точные оценки при дополнительных спектральных ограничениях на исходный граф. Результаты диссертационной работы демонстрируют универсальность аналитического подхода для решения проблем перечисления графов.
Цели и задачи работы. Основной целью данной работы является получение асимптотических формул для следующих классических проблем перечисления графов:
• Подсчет числа различных эйлеровых ориентаций простого неориентированного графа (таких ориентаций ребер графа, для которых каждая вершина графа обладает одинаковым числом входящих и выходящих ребер).
• Подсчет числа различных эйлеровых циклов простого неориентированного графа (замкнутых путей, проходящих по каждому ребру графа ровно один раз).
• Подсчет числа различных помеченных остовных подграфов фиксированного графа, обладающих заданной последовательностью степеней вершин.
Важными задачами являются также исследование классов графов, для которых применим аналитический подход для решения вышеперечисленных проблем перечисления, и разработка универсальных инструментов для работы с подобными проблемами.
Общая методика исследования.
Доказательства асимптотических формул для рассматриваемых задач перечисления во многом аналогичны. Используемый метод является вариантом многомерного метода стационарной фазы. С помощью производящих функций ответ представляется в виде многомерного иннекоторая область в Rn, разтеграла, имеющего вид F ()d, где U мерность n совпадает с числом вершин графа, а подынтегральное выражение F () состоит из большого числа множителей fjk (), причем пары {j, k} соответствуют ребрам графа. Для каждой задачи строится некоторая небольшая область Box U такая, что вектора Box находятся в окрестности максимумов fjk (). Оценка интегралов происходит в два этапа:
1. Работа внутри коробки. При Box, используя разложение в ряд Тейлора для функций fjk () в окрестности максимумов, оцениваемый интеграл сводится к интегралу гауссовского типа:
где A некоторая матрица, ассоциированная с графом, T () является полиномом и константа > 0. При определенных ограничениях на спектр A и размер коробки такие интегралы удается аппроксимировать.
Упаковка. Если U \ Box, то найдется достаточно большое число множителей fjk (), значение которых существенно меньше, чем в коробке. В результате удается показать, что при n Научная новизна. В настоящей диссертационной работе результаты McKay B.D, Robinson R.W., Wormald N.C. об асимптотике числа эйлеровых ориентаций, эйлеровых циклов и помеченных подграфов с заданной последовательностью степеней вершин в полных графах распространяются на существенно более широкие классы графов со спектральными ограничениями.
Полученные в работе асимптотические формулы, являются новыми. Кроме того, получен ряд новых результатов, касающихся свойств классов графов со спектральными ограничениями и асимптотик интегралов гауссовского типа.
Теоретическая и практическая значимость. Работа носит теоретический характер.
Полученные результаты об асимптотике эйлеровых ориентаций, эйлеровых циклов и помеченных подграфов с заданной последовательностью степеней вершин в графах со спектральными ограничениями интересны по двум причинам:
• Рассмотренные задачи являются классическими задачами теории перечисления графов. Новые асимптотические формулы позволяют оценить искомый ответ почти для всех графов (в определенном вероятностным смысле).
• Рассмотренные задачи считаются трудными в теории сложности вычислений, поэтому полученные легковычислимые явные формулы представляют особый интерес с алгоритмической точки зрения.
Доказанная в работе теорема об асимптотике весьма распространенных в теоретических и практических иссследованиях интегралов гауссовского типа является важным инструментом, который может быть полезен для их анализа.
Апробация работы. Основные результаты работы докладывались на научных семинарах в следующих организациях:
- Вычислительный центр им. А.А. Дородницына РАН (Москва, 2010);
- кафедра теории функций и функционального анализа мехмата МГУ им. М.В. Ломоносова (Москва, 2011);
- кафедра математических основ управления МФТИ (ГУ) (Долгопрудный, 2010-2013);
- кафедра математической кибернетики МГУ им. М.В. Ломоносова (Москва, 2012);
а также на следующих научных конференциях:
- 36th Australasian conference on combinatorial mathematics and combinatorial computing (36ACCMC) (Сидней, Австралия, 2012);
- Международная конференция Алгебра и комбинаторика, посвященная 60-летию А.А. Махнева (Екатеринбург, 2013);
- Международная конференция Дискретная оптимизация и исследование операций (Новосибирск, 2013);
- XI Международный семинар Дискретная математика и ее приложения, посвященный 80-летию со дня рождения академика О.Б. Лупанова (Москва, 2012);
- 53 – 55 научные конференции МФТИ Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе (Москва, 2010 – 2012).
Публикации. По теме диссертации опубликовано 9 печатных работ, из которых 3 ([7, 8, 9]) в изданиях из списка, рекомендованного ВАК РФ.
Личный вклад автора в работы с соавторами. Все научные результаты, вынесенные на защиту, получены лично автором. Численные расчеты, сопоставляющие полученные формулы с точными значениями, проведены совместно с Исаевой К.В.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Основной текст работы состоит из 135 страниц, приложение занимает 12 страниц. Список литературы включает 91 наименование.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обсуждается актуальность работы, дается обзор существующих подходов к задачам перечисления графов, указываются положения, выносимые на защиту. Описывается структура диссертации и кратко излагается ее содержание. Кроме того, приводятся сведения об апробации работы.
Первая глава посвящена проблемам и известным методам решения исследуемых задач. Для каждой из рассматриваемых проблем приводится подробный обзор литературы.
В §1.1 рассматриваются алгоритмические аспекты проблем перечисления. Обсуждаются понятие P -полноты, параметризированные и приближенные алгоритмы. Приводятся некоторые важные результаты теории вычислительной сложности.
§1.2 работы посвящен задаче подсчета числа различных ориентаций ребер графа, для которых каждая вершина графа обладает одинаковым числом входящих и выходящих ребер. Такие ориентации называются эйлеровыми ориентациями.
В п. 1.2.1 приводится постановка задачи и обсуждается значимость задачи в различных научных областях. Кроме того, приводятся результаты Mihail M., Winkler P. о P -полноте перечисления эйлеровых ориентаций и существовании полиномиального приближенного вероятностного алгоритма для их подсчета. Этот алгоритм подробно обсуждается в п. 1.2.2.
В п. 1.2.3 рассматривается случай полного графа Kn. Даже в этом частном случае точное выражение числа эйлеровых ориентаций EO(Kn ) при нечетном n неизвестно (EO(Kn ) = 0 при четном n). McKay B.D.
доказал следующую асимптотическую формулу: при нечетном n для любого фиксированного > 0.
При доказательстве формулы (1) число эйлеровых ориентаций полного графа представлялось в виде многомерного интеграла. Аналогичное представление верно и в общем случае: пусть степени всех вершин графа G четные, тогда множество ребер графа, jk = j k. Это представление где EG используется для обобщения асимптотической формулы (1).
§1.3 работы посвящен задаче подсчета числа различных замкнутых путей, проходящих по каждому ребру графа ровно один раз. Такие пути называются эйлеровыми циклами.
В п. 1.3.1 приводится постановка задачи, обсуждаются алгоритмические аспекты и рассматривается случай полного графа. Отметим, что задача подсчета числа эйлеровых циклов остается -полной уже для графов с небольшими степенями вершин (для регулярных степени 4), но, в отличии от задачи подсчета числа эйлеровых ориентаций для нее эффективные приближенные алгоритмы известны только для графов с малой плотностью.
В случае полного графа точное выражение числа эйлеровых циклов EC(Kn ) при нечетном n неизвестно (EC(Kn ) = 0 при четном n).
McKay B.D., Robinson R.W. доказали следующую асимптотическую формулу: при нечетном n для любого фиксированного > 0.
При доказательстве формулы (2) число эйлеровых циклов полного графа представлялось в виде многомерного интеграла. В п. 1.3.2 получено аналогичное представление для общего случая: пусть степени графа G:
остовных деревьев G, ориентированных таким образом, чтобы корневая вершина v не имела выходящих ребер, а любая другая вершина имела ровно одно выходящее ребро. Это представление используется для обобщения асимптотической формулы (2).
В п. 1.3.3 обсуждаются вероятностные интерпретации перечисления эйлеровых циклов. Рассматриваются два следующих процесса: случайное блуждание по графу, используя ребра не более одного раза, и случайное спаривание ребер графа.
§1.4 работы посвящен задаче подсчета числа различных помеченных остовных подграфов фиксированного графа, обладающих заданной последовательностью степеней вершин s = (s1, s2,..., sn ). Такие естественным образом: f (vj ) = sj.
В п. 1.4.1 формулируется постановка задачи, обсуждаются алгоритмические аспекты, а также приводится представление ответа в виде интеграла:
где EG множество ребер графа, SG(s) число различных помеченных подграфов графа G с заданной последовательностью степеней вершин s = (s1, s2,..., sn )T Nn, вектор r Rn.
Вышеприведенное представление используется для обобщения следующей асимптотической формулы (случай полного графа), приведенной в п. 1.4.2:
Теорема (McKay B.D., Wormald N.C.). Пусть s = жим, что s N таково, что SKn (s) > 0, min{, n s 1} > an/ ln n рых фиксированных b, > 0. Тогда при n Совершенно другой подход, основанный на случайной деформации графа, используется для нахождения асимптотики в случае, когда степени s1,..., sn небольшие. Этот результат, полученный McKay B.D. и Wormald N.C., также приводится в п. 1.4.2. Обе асимптотические формулы сводятся к одинаковому выражению:
где SKn (s, ) обозначает наивную оценку, рассматриваемую в п. 1.4.3, которая определяется в общем случае следующим образом:
где d1,..., dn степени вершин графа G. Одним из результатов настоящей работы является обобщение формулы (4).
В §1.5 работы коротко излагается общая схема доказательства основных результатов.
Вторая глава посвящена асимптотическому анализу интегралов следующего типа:
В §2.1 работы приводятся необходимые понятия и предположения.
Используя покоординатное масштабирование вектора, интеграл всегда можно свести к случаю, когда диагональные элементы матрицы A равны 1. Поэтому полагается для простоты, что A = I + X, где I единичная n n матрица, а X некоторая симметрическая матрица с нулевыми диагональными элементами.
Для действительного p 1 и вектора x Rn определяется норма В случае p = пусть Векторной p-норме соответствует матричная норма Рассматриваются следующие предположения на матрицу A:
A положительно определенная симметрическая матрица Диагональные элементы матриц, удовлетворяющих (6), асимптотически доминируют над остальными элементами. Свойства таких матриц обсуждаются в §2.2.
В §2.3 работы определяются несколько специальных функций над полиномами, необходимые для формулировки основного результата второй главы.
где deg P обозначает степень полинома P. Функции h1 (высота полинома) и h2 (четная высота полинома) определяются в п. 2.3.1 следующим образом:
где 2d = (2d1, 2d2,..., 2dn ).
Функции 0, 1 и A = 0 + 1 определяется в п. 2.3.2 линейным образом, причем причем 5s < 1/2. Пусть n n матрица A удовлетворяет (6). Тогда для любых полиномов P, Q : Rn C таких, что deg P s, deg Q s, h1 (P ) c, h1 (Q) cn и h2 (Q) = 0, выполняется:
где и константа C > 0 зависит только от a, b, c, r, s,.
При выполненных предположениях Теоремы 1 показывается, в частности, что значение A (P + Q2 /2) ограничено по модулю некоторой константой, зависящей только от a, b, c, r, s,.
Третья глава посвящена исследованию свойств классов графов со спектральными ограничениями. Большинство результатов непосредственно следуют из известных в литературе свойств используемых спектральных параметров. Тем не менее некоторые из полученных в этой главе результатов, см., например, Предложения 5, 8, 10, являются новыми.
В §3.1 работы рассматривается класс графов, обладающих сильными перемешивающими свойствами. Различные эквивалентные определения этого класса приводятся в п. 3.1.1.
Для неориентированого простого графа G с множеством вершин V G = {v1, v2,..., vn } и множеством ребер EG определяется n n матрица L следующим образом:
где n = |V G| и dj обозначает степень vj V G. Матрица L = L(G) называется матрицей Лапласа графа G. Собственные значения матрицы L являются неотрицательными вещественными числами, причем кратность нулевого собственного значения совпадает с количеством компонент связности, в частности, 1 = 0. Число 2 = 2 (G) называется алгебраической связностью графа G.
Граф G называется -перемешивающим, если Этот класс графов называется в диссертации классом графов с сильными перемешивающими свойствами.
В п. 3.1.1 рассматриваются также другие классические параметры графов, которые отражают свойства перемешиваемости: константа Чигера (изопериметрическое число), спектральный зазор между и вторым по величине собственным значением матрицы вероятностей перехода случайного блуждания на графе. В п. 3.1.2 показано, что эти параметры позволяют эквивалентным образом определить класс графов, обладающих сильными перемешивающими свойствами. П. 3.1. посвящен обсуждению различных примеров и контрпримеров.
В п. 3.1.4 исследуются структурные свойства -перемешивающих графов. Рассматриваются S T пути в графе G, то есть пути, один конец которых принадлежит S, другой T, где S и T являются подмножествами множества вершин V G. Доказывается следующий результат:
Предложение 5. Пусть G простой -перемешивающий граф с n вершинами для некоторого > 0. Подмножества вершин S, T V G таковы, что S T =. Тогда существуют µ n min {|S|, |T |} попарно не пересекающихся по ребрам S T путей длины не превосходящей H, причем константы µ, H > 0 зависят только от.
В п. 3.1.5 исследуются свойства матриц Лапласа -перемешивающих графов. В частности, обсуждается сведение к матрицам, удовлетворяющим условиям (6).
В §3.2 работы рассматривается класс существенно недвудольных графов. Различные эквивалентные определения этого класса приводятся в п. 3.2.1.
Для неориентированого простого графа G с множеством вершин V G = {v1, v2,..., vn } и множеством ребер EG определяется n n матрица Q следующим образом:
где n = |V G| и dj обозначает степень vj V G. Матрица Q = Q(G) называется беззнаковой матрицей Лапласа или Q-матрицей графа G.
Собственные значения матрицы Q являются неотрицательными вещественными числами, причем кратность нулевого собственного значения равна числу двудольных компонент связности графа, в частности, qn = 0 тогда и только тогда, когда какая-то из компонент связности является двудольным графов. Число qn = q(G) называется алгебраической недвудольностью (англ. bipartiteness) графа G.
Граф G называется -недвудольным, если алгебраическая недвудольность q(G) |V G|.
Этот класс графов называется в диссертации классом существенно недвудольных графов.
В п. 3.2.1 рассматриваются также другие параметры графов: спектральный зазор между 1 и наименьшим собственным значением матрицы вероятностей перехода случайного блуждания на графе, аналог константы Чигера. Показано, что эти параметры позволяют эквивалентным образом определить класс существенно недвудольных графов.
П. 3.2.2 посвящен обсуждению различных примеров и контрпримеров.
В п. 3.2.3 исследуются структурные свойства -недвудольных графов. Рассматриваются S-пути нечетной длины в графе G, то есть пути, оба конца которых принадлежит S, где S V G. Доказывается следующий результат:
Предложение 8. Пусть G простой -недвудольный граф с n вершинами для некоторого > 0. Тогда для любого = S V G существует не менее µn|S| попарно не имеющих общих ребер S-путей нечетной длины, не превосходящей H, причем константы µ, H > зависят только от.
В п. 3.2.4 исследуются свойства матриц Лапласа -недвудольных графов. В частности, обсуждается сведение к матрицам, удовлетворяющим условиям (6).
В §3.3 рассматривается модель Эрдеша-Реньи случайного графа.
В этой модели каждое возможное ребро графа присутствует в графе независимо с некоторой фиксированной вероятностью 0 < p < 1. Доказывается следующий результат:
Предложение 10. Вероятность того, что случайный граф с n вершинами в модели Эрдеша-Реньи является одновременно и -перемешивающим, и -недвудольным, не менее 1 n, причем константы > 0, > 1 зависят только от p.
В §3.4 работы обсуждается комбинаторный смысл миноров матрицы Лапласа и определителя Q-матрицы. В частности, число остовных деревьев графа G, а матрица L(r) получается где t(G) удалением r-го столбца и r-й строки из матрица Лапласа L графа G.
Формула (7), известная также как матричная теорема о деревьях, была впервые получена неявным образом Кирхгофом Г. в 1847 г.
В четвертой главе доказываются основные результаты диссертационной работы.
§4.1 работы посвящен перечислению эйлеровых ориентаций простого неориентированного графа.
В п. 4.1.1 формулируется следующая теорема:
Теорема 3. Пусть G неориентированный простой граф с n вершинами v1, v2,..., vn, имеющими четную степень. Пусть для некоторого фиксированного > 0 граф G является -перемешивающим.
Тогда:
где dj степень вершины vj, t(G) число остовных деревьев G (эффективно вычисляется с помощью (7)), и для любого > где константа Ceo > 0 зависит только от и.
Доказательство Теоремы 3 приводится в п. 4.1.2 и п. 4.1.3.
§4.2 работы посвящен перечислению эйлеровых циклов в простом неориентированном связном графе.
В п. 4.2.1 формулируется следующая теорема:
Теорема 4. Пусть все предположения Теоремы 3 выполнены, тогда:
где dj степень вершины vj, t(G) число остовных деревьев G (эффективно вычисляется с помощью (7)), и для любого > где константа Cec > 0 зависит только от и.
Доказательство Теоремы 3 приводится в п. 4.2.2, п. 4.2.3 и п. 4.2.4.
Для случая полного графа G = Kn выполняется:
Результаты Теорем 3 и 4 для случая полного графа сводятся к формулам (1) и (2), соответственно.
§4.3 работы посвящен перечислению помеченных остовных подграфов фиксированного графа, обладающих заданной последовательностью степеней вершин.
Пусть вектор d = (d1, d2,..., dn )T соответствует степеням вершин графа G с n вершинами, а вектор s = (s1, s2,..., sn )T заданной последовательности степеней вершин подграфа. Число различных помеченных остовных подграфов графа G с заданными степенями вершин s1, s2,..., sn обозначается SG(s).
В п. 4.3.1 формулируется следующая теорема:
с n вершинами v1, v2,..., vn, причем константа Чигера (изопериметрическое число) i(G) n. Тогда для любых s = (s1,..., sn )T Nn и выполняется:
где E = (s1 +... + sn )/2, |EG| – число ребер графа G, причем для любого > где константа Csg > 0 зависит только от,,,,.
Доказательство Теоремы 5 приводится в п. 4.3.2 и п. 4.3.3.
В п. 4.3.4 обсуждается наивная оценка (5). Доказывается следующий результат:
Предложение 11. При выполненных предположениях Теоремы 5:
Для случая полного графа G = Kn выполняется: алгебраическая где Если выбрать = E/|EKn |, то a1 + a2 +... + an = 0 и поэтому:
Результаты Теоремы 4 и Предложения 11 для случая полного графа сводятся к формулам (3) и (4) при условии max |sj (n 1)| = O(1).
Основные результаты работы изложены в заключении.
В приложении приводятся доказательства некоторых вспомогательных лемм.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1. Аналитический подход, использованный McKay B.D, Robinson R.W., Wormald N.C. для случая полного графа, адаптирован для существенно более широких классов графов со спектральными ограничениями. Получены новые явные асимптотические формулы для эйлеровых ориентаций, эйлеровых циклов и помеченных подграфов с заданной последовательностью степеней вершин.2. Получены новые свойства классов графов со спектральными ограничениями. В частности, доказано, что в определенном вероятностном смысле почти все графы принадлежат рассматриваемым классам.
3. При условии асимптотического диагонального доминирования соответствующей матрицы квадратичной формы получена асимптотика интеграла гауссовского типа с полиномиальным возмущением в показателе экспоненты.
Автор выражает благодарность научному руководителю к.ф.-м.н.
Тарасову С.П. за постановки задач и постоянное внимание к работе, а также профессору McKay B.D. за обсуждение работы и ряд ценных замечаний.
Работа поддержана грантом РФФИ №11-01-00398а.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Исаев М.И. Асимптотика числа эйлеровых циклов в плотных графах// Труды 53-й научной конференции МФТИ Современные проблемы фундаментальной и прикладной математики, Управление и прикл. математика, М.:МФТИ, 2010, T. 1, C. 72–73.2. Исаев М.И. Свойства графов с большой алгебраической связностью// Труды 54-й научной конференции МФТИ Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе, Управление и прикладная математика, М.: МФТИ, 2011, T. 1, C. 53–54.
3. Исаев М.И. Асимптотическая формула для числа эйлеровых ориентаций в графах с большой алгебраической связностью// Материалы XI Международного семинара Дискретная математика и ее приложения, посвященного 80-летию со дня рождения академика О.Б. Лупанова, М.: МГУ, 2012, C. 288.
4. Исаев М.И. Задача перечисления эйлеровых циклов в графах// Труды 55-й научной конференции МФТИ Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе, Управление и прикладная математика, М.: МФТИ, 2012, T. 1, C. 155–156.
5. Исаев М.И. Асимптотика числа подграфов с заданными степенями вершин в недвудольных графах// Тезисы международной конференции Алгебра и комбинаторика, посвященной 60-летию А.А. Махнева, Екатеринбург: изд. УМЦ- УПИ, 2013, C. 58–60.
6. Исаев М.И. Оценка числа подграфов с заданными степенями вершин// Тезисы международной конференции Дискретная оптимизация и исследование операций, Новосибирск: изд. Ин-та математики, 2013, C. 106.
7. Исаев М.И. Асимптотическое поведение числа эйлеровых ориентаций в графах// Математические заметки, 2013, Т. 93, В. 6, C. 828–843.
8. Исаев М.И., Исаева К.В. О классе графов, обладающих сильными перемешивающими свойствами// Труды МФТИ, 2013, T. 5, № 3, C. 171–181.
9. Isaev M.I. Asymptotic behaviour of the number of Eulerian circuits// Electronic Journal of Combinatorics, 2011, V. 18(1), Pap. 219, 35 p.
АНАЛИТИЧЕСКИЙ ПОДХОД ДЛЯ ЗАДАЧ ПЕРЕЧИСЛЕНИЯ
ГРАФОВ СО СПЕКТРАЛЬНЫМИ ОГРАНИЧЕНИЯМИ
АВТОРЕФЕРАТ
Подписано в печать 03.09.2013 г. Формат 60 84 1 /16. Усл. печ. л. 1,0.Федеральное государственное бюджетное образовательное высшего профессионального образования Московский физико-технический институт Отдел оперативной полиграфии Физтех-полиграф 141700, Московская обл., г. Долгопрудный, Институтский пер., 9.