Введение
Глава 1. Некоторые задачи перечисления графов: проблемы и методы их решения 10
1.1. Проблемы алгоритмического решения задач перечисления . 10
1.2. Эйлеровы ориентации 14
1.2.1. Постановка задачи 14
1.2.2. Приближенный вероятностный алгоритм 15
1.2.3. Случай полного графа. Представление в виде интеграла 18
1.3. Эйлеровы циклы 20
1.3.1. Постановка задачи. Случай полного графа 20
1.3.2. Ориентированные графы. Представление в виде интеграла 21
1.3.3. Вероятностные интерпретации 23
1.4. Подграфы с заданной последовательностью степеней вершин . 25
1.4.1. Постановка задачи. Представление в виде интеграла . 25
1.4.2. Случай полного графа 26
1.4.3. Случай произвольного графа. Наивная гипотеза 28
1.5. Общая схема доказательства основных результатов 30
Глава 2. Асимптотические оценки многомерных интегралов гаус-совского типа 33
2.1. Интегралы гауссовского типа. Обозначения и предположения . 33
2.2. Матрицы с асимптотическим диагональным доминированием . 35
2.2.1. Свойства обратной матрицы 35
2.2.2. Определитель возмущенной матрицы 37
2.2.3. Главные миноры 39
2.3. Некоторые функции над полиномами 40
2.3.1. Высота и четная высота 40
2.3.2. Функция ХА 42
2.4. Асимптотические оценки 43
2.4.1. Формулировка результатов 43
2.4.2. Вспомогательные утверждения. Основная лемма 45
2.4.3. Редукция полиномов 48
2.4.4. Доказательство асимптотических оценок 51
Глава 3. Графы со спектральными ограничениями 55
3.1. Класс графов с сильными перемешивающими свойствами . 55
3.1.1. Перемешивающие свойства графов 55
3.1.2. Доказательство эквивалентности 58
3.1.3. Примеры 62
3.1.4. Пути и разрезы 64
3.1.5. Свойства матрицы Лапласа 67
3.2. Класс существенно недвудольных графов 70
3.2.1. Недвудольность и апериодичность 70
3.2.2. Примеры 73
3.2.3. Нечетные пути 76
3.2.4. Свойства беззнаковой матрицы Лапласа 78
3.3. Сильная перемешиваемость и существенная недвудольность случайного графа 79
3.4. Комбинаторный смысл миноров матрицы Лапласа и определителя Q-матрицы 82
Глава 4. Аналитический подход на примере некоторых задач перечисления графов 85
4.1. Эйлеровы ориентации 85
4.1.1. Асимптотическая формула 85
4.1.2. Основная часть интеграла 87
4.1.3. Оценка незначительных частей 91
4.2. Эйлеровы циклы 96
4.2.1. Асимптотическая формула 96
4.2.2. Приведение к интегралу гауссовского типа 98
4.2.3. Основная часть интеграла 102
4.2.4. Оценка незначительных частей 105
4.3. Подграфы с заданной последовательностью степеней вершин 111
4.3.1. Асимптотическая формула 111
4.3.2. Основная часть интеграла 113
4.3.3. Оценка незначительных частей 117
4.3.4. Наивная гипотеза 122
Заключение 124
Литература 126
ПриложениеA.Доказательство Леммы4 136
