WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

Исаев Михаил Исмаилович

АНАЛИТИЧЕСКИЙ ПОДХОД К ЗАДАЧАМ

ПЕРЕЧИСЛЕНИЯ ГРАФОВ СО

СПЕКТРАЛЬНЫМИ ОГРАНИЧЕНИЯМИ

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.





Похожие работы:

«АКИМОВ ВАСИЛИЙ ВЛАДИМИРОВИЧ КОНСТРУКТОРСКО-ТЕХНОЛОГИЧЕСКИЙ СИНТЕЗ КОНИЧЕСКИХ ПЕРЕДАЧ С КРУГОВЫМИ ЗУБЬЯМИ Специальность 05.02.02 – Машиноведение, системы приводов и детали машин АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва 2009 г. Работа выполнена в ГОУ ВПО МГТУ Станкин на кафедре Теоретическая механика Научный руководитель : Доктор технических наук, доцент Волков Андрей Эрикович Официальные оппоненты : Доктор технических наук,...»

«АБЛЯЗОВ Эмиль Кемалович ЛАЗЕРНАЯ СИСТЕМА ДЛЯ ДИСТАНЦИОННОГО ЗОНДИРОВАНИЯ МОЛЕКУЛ УГЛЕВОДОРОДОВ В АТМОСФЕРЕ Специальность 05.11.13 – Приборы и методы контроля природной среды, веществ, материалов и изделий АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Краснодар - 2011 2 Работа выполнена в Новороссийском политехническом институте (филиал ГОУ ВПО Кубанский Государственный Технологический Университет. Шеманин Валерий Геннадьевич, доктор Научный...»

«КУЛЬКОВ ИГНАТ АЛЕКСАНДРОВИЧ МЕТОДЫ И МОДЕЛИ МАРКЕТИНГА ТОРГОВОПОСРЕДНИЧЕСКИХ ОРГАНИЗАЦИЙ 08.00.13 – Математические и инструментальные методы экономики АВТОРЕФЕРАТ Диссертации на соискание ученой степени кандидата экономических наук Санкт-Петербург 2007 Работа выполнена на кафедре Информационные системы в экономике и менеджменте Государственного образовательного учреждения высшего профессионального образования Санкт-Петербургский государственный политехнический университет...»

«КОЛЬЧЕНКО Владимир Петрович ДОПРОС КАК СПОСОБ ДОКАЗЫВАНИЯ И СРЕДСТВО ОБЕСПЕЧЕНИЯ ПРАВ ЛИЧНОСТИ В УГОЛОВНОМ СУДОПРОИЗВОДСТВЕ 12.00.09 - уголовный процесс; криминалистика и судебная экспертиза; оперативно-розыскная деятельность АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата юридических наук Саратов 2003 Диссертация выполнена в Государственном образовательном учреждении высшего профессионального образования Саратовская государственная академия права Научный...»

«ЗАХАРЯН НОРАЙР ГРАЙРОВИЧ ВЫВИХИ ПОСЛЕ ТОТАЛЬНОГО ЭНДОПРОТЕЗИРОВАНИЯ ТАЗОБЕДРЕННОГО СУСТАВА 14.00.22. – травматология и ортопедия Автореферат диссертации на соискание ученой степени кандидата медицинских наук МОСКВА 2008 2 Работа выполнена на кафедре травматологии и ортопедии ГОУ ВПО Российский университет дружбы народов Научный руководитель : Заслуженный деятель науки РФ, доктор медицинских наук, профессор ЗАГОРОДНИЙ Николай Васильевич Официальные оппоненты : доктор...»

«ЦЕЛИЩЕВ Антон Владимирович МЕТОДИКА РАСЧЕТА И МОДЕЛИРОВАНИЯ ПРОЦЕССА ФАЗОРАЗДЕЛЕНИЯ ГАЗОЖИДКОСТНОГО ПОТОКА В ПРОТИВОТОЧНОЙ ВИХРЕВОЙ ТРУБЕ Специальность 05.04.13 - Гидравлические машины и гидропневмоагрегаты АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Уфа – 2012 Работа выполнена в ФГБОУ ВПО Уфимский государственный авиационный технический университет на кафедре сопротивления материалов. заслуженный деятель науки РФ, Научный руководитель :...»

«Семенова Ольга Сергеевна Математическое моделирование в задачах оптимизации движения городского пассажирского транспорта с учетом наложения маршрутных схем 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Новокузнецк 2009 2 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования “Кузбасский государственный технический...»

«Логинова Екатерина Валентиновна ОСНОВНЫЕ ТЕНДЕНЦИИ РАЗВИТИЯ РЫНКОВ ЖИЛОЙ НЕДВИЖИМОСТИ ЗАРУБЕЖНЫХ СТРАН И РОССИИ В УСЛОВИЯХ ГЛОБАЛИЗАЦИИ 08.00.14. – Мировая экономика Автореферат диссертации на соискание ученой степени кандидата экономических наук Москва - 2008 2 Работа выполнена на кафедре Мировая экономика ГОУ ВПО Государственный университет управления. Научный руководитель : доктор экономических наук, профессор Хейфец Борис Аронович Официальные оппоненты : доктор...»

«ЛЕПИХОВ Андрей Валерьевич МЕТОДЫ ОБРАБОТКИ ЗАПРОСОВ В СИСТЕМАХ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ ДЛЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ С ИЕРАРХИЧЕСКОЙ АРХИТЕКТУРОЙ 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2008 Работа выполнена на кафедре системного программирования Южно-Уральского государственного университета. доктор...»

«Еремийчук Александр Сергеевич Синтез и исследование новых производных 6-(2,6дигалогенбензил)-5-алкил-2-(алкилсульфанил)-4(3Н)пиримидинона 02.00.03 – Органическая химия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата химических наук Волгоград - 2008 Работа выполнена на кафедре Аналитической, физической химии и физикохимии полимеров Волгоградского государственного технического университета. чл.-корр. РАН, доктор химических наук, профессор, Научный руководитель...»

«ПОПОВ АНДРЕЙ АЛЕКСАНДРОВИЧ РАСЧЕТ ТЕРМОГАЗОДИНАМИЧЕСКИХ ПРОЦЕССОВ И ОПРЕДЕЛЕНИЕ К.П.Д. ХОЛОДИЛЬНОГО ЦЕНТРОБЕЖНОГО КОМПРЕССОРА, СЖИМАЮЩЕГО РЕАЛЬНЫЕ РАБОЧИЕ ВЕЩЕСТВА, МЕТОДОМ ОБОБЩЕННОЙ ПОЛИТРОПЫ Специальность 05.04.03 – Машины и аппараты, процессы холодильной и криогенной техники, систем кондиционирования и жизнеобеспечения АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург – 2008 Работа выполнена в ГОУ ВПО Санкт-Петербургский...»

«САМКАЕВ Игорь Мирвахисович ФОРМИРОВАНИЕ ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКОГО МЕХАНИЗМА УПРАВЛЕНИЯ ИННОВАЦИОННОЙ И ИНВЕСТИЦИОННОЙ ДЕЯТЕЛЬНОСТЬЮ СТРОИТЕЛЬНОГО ПРЕДПРИЯТИЯ Специальность 08.00.05 - Экономика и управление народным хозяйством: экономика, организация и управление предприятиями, отраслями, комплексами (строительство); управление инновациями и инвестиционной деятельностью АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Санкт-Петербург Работа...»

«Сергеев Сергей Александрович ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ЦЕПНЫХ МУФТ НА ОСНОВЕ СОЗДАНИЯ ИХ МАТЕМАТИЧЕСКОЙ МОДЕЛИ Специальность 05.13.06 – Автоматизация и управление технологическими процессами и производствами (технические системы) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Курск 2007 2 Работа выполнена на кафедре Машиностроительные технологии и оборудование ГОУ ВПО Курский государственный технический...»

«ДМИТРИЕВА ОЛЬГА АЛЕКСАНДРОВНА МЕТОДИКА РАЗВИТИЯ ПРОФЕССИОНАЛЬНОПЕДАГОГИЧЕСКОЙ КОМПЕТЕНТНОСТИ В ОБЛАСТИ ПРОЕКТИРОВАНИЯ УЧЕБНЫХ МАТЕРИАЛОВ ПО ИНФОРМАТИКЕ У УЧИТЕЛЯ НАЧАЛЬНЫХ КЛАССОВ 13.00.02 – теория и методика обучения и воспитания (информатика) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата педагогических наук Челябинск – 2009 Работа выполнена на кафедре информатики и методики преподавания информатики Государственного образовательного учреждения высшего...»

«ЮЛЬМЕТОВ Айдар Рафаилевич СТРУКТУРА И МАГНИТНОРЕЗОНАНСНЫЕ ПАРАМЕТРЫ МОЛЕКУЛЯРНЫХ СИСТЕМ НА ОСНОВЕ МЕТОДОВ МОЛЕКУЛЯРНОЙ МЕХАНИКИ, КВАНТОВОЙ ХИМИИ И СПЕКТРОСКОПИИ ЯМР 01.04.07 — физика конденсированного состояния АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Казань — Работа выполнена на кафедре...»

«Столяров Алексей Михайлович ИСТОРИЯ ВЕЛИКОГО КНЯЖЕСТВА ЛИТОВСКОГО В ОТЕЧЕСТВЕННОЙ ИСТОРИОГРАФИИ XIX – НАЧАЛА XX ВЕКА Специальность: 07.00.09 – историография, источниковедение и методы исторического исследования АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата исторических наук Казань 2008 Работа выполнена на кафедре истории России ГОУ ВПО Татарский государственный гуманитарно-педагогического университет кандидат исторических наук, доцент Научный руководитель :...»

«Силаева Зоя Владимировна ИНСТИТУЦИОНАЛИЗАЦИЯ СПОРНЫХ ГОСУДАРСТВ В УСЛОВИЯХ ПОЛИТИЧЕСКОЙ ТРАНСФОРМАЦИИ ПОСТСОЦИАЛИСТИЧЕСКОГО ПРОСТРАНСТВА Специальность 23.00.02 – политические институты, процессы и технологии АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата политических наук Казань – 2012 2 Работа выполнена на кафедре политологии Федерального государственного автономного образовательного учреждения высшего профессионального образования Казанский (Приволжский)...»

«УДК: 621.382: 621.3.011.7: 621.314.1: 514.8 ПЕНИН АЛЕКСАНДР АНАТОЛЬЕВИЧ МОДЕЛИРОВАНИЕ ЭЛЕКТРОННЫХ ХАРАКТЕРИСТИК СИЛОВЫХ ТРАНЗИСТОРОВ И ФОТОЭЛЕКТРИЧЕСКИХ ПРЕОБРАЗОВАТЕЛЕЙ В ЛИНЕЙНО-ГИПЕРБОЛИЧЕСКОЙ АППРОКСИМАЦИИ 05. 27. 01 – ЭЛЕКТРОНИКА ТВЕРДОГО ТЕЛА, МИКРОЭЛЕКТРОНИКА, НАНОЭЛЕКТРОНИКА Автореферат диссертации на соискание ученой степени доктора технических наук КИШИНЕВ Работа выполнена в лаборатории...»

«Живаев Александр Петрович РАЗВИТИЕ ИНФОРМАЦИОННОКОНСУЛЬТАЦИОННЫХ УСЛУГ В АГРАРНОМ СЕКТОРЕ ЭКОНОМИКИ Специальность 08.00.05 – экономика и управление народным хозяйством (экономика, организация и управление предприятиями, отраслями, комплексами – сфера услуг) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Екатеринбург - 2009 Диссертационная работа выполнена на кафедре предпринимательства и агробизнеса Федерального государственного...»

«ОСИНЦЕВА НАДЕЖДА ВЛАДИМИРОВНА ТАНЕЦ В АСПЕКТЕ АНТРОПОЛОГИЧЕСКОЙ ОНТОЛОГИИ Специальность 09.00.01 – онтология и теория познания АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата философских наук Тюмень - 2006 Работа выполнена на кафедре гуманитарных дисциплин Тюменского государственного института искусств и культуры Научный руководитель : доктор философских наук, профессор Селиванов Федор Андреевич Официальные оппоненты : доктор философских наук, профессор Губанов...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

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