Аналитический подход к задачам перечисления графов со спектральными ограничениями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

Ш

АНАЛИТИЧЕСКИИ ПОДХОД К ЗАДАЧАМ ПЕРЕЧИСЛЕНИЯ ГРАФОВ СО СПЕКТРАЛЬНЫМИ ОГРАНИЧЕНИЯМИ

01.01.09 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

005533872

Москва 2013

3 ОКТ 2013

005533872

Работа выполнена на кафедре математических основ управления Московского физико-технического института (государственного университета)

Научный руководитель: кандидат физико-математических наук

Тарасов Сергей Павлович

Официальные оппоненты: доктор физико-математических наук,

профессор

Сапоженко Александр Антонович, кафедра математической кибернетики Московского государственного университета им. М.В. Ломоносова, профессор

кандидат физико-математических наук Соболевский Андрей Николаевич, Институт проблем передачи информации им. A.A. Харкевича РАН, заместитель директора по научной работе

Ведущая организация: Центральный экономико-

математический институт РАН

Защита состоится 2013 года в -РЛ, часов ^Апшут

на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан -14 2013 г.

Ученый секретарь диссертационного совета

Федько О.С.

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

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

Перечисление графов является важным разделом теории графов, имеющим многочисленные приложения в химии, статистической физике, кибернетике и др. областях. Первые существенные шаги в теории перечисления графов были сделаны ещё в девятнадцатом столетии. В своих работах, опубликованных в 1857—1889 гг., Кэли А. получил формулы для количества деревьев трех типов: помеченных, корневых и обычных, а также связанных с ними химических структур. Еще ранее Кирхгоф Г. получил в неявной форме число различных остовных деревьев заданного графа, а значит, в частности, число помеченных деревьев.

В настоящее время перечисление графов представляет собой развитую теорию, занимающую существенное место в области комбинаторного анализа. В монографии Harary F. и Palmer Е. приведено большое количество разнообразных задач перечисления непомеченных графов с определенными свойствами. Для задач такого типа используется алгебраический подход, основанный на теории перечисления Пойа. Принцип включения и исключения, обращение Мёбиуса, а также многие другие известные методы, подробно изложены в книгах Stanley R.P. по перечислительной комбинаторике.

Во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики, и, в частности, интерес к алгоритмическим аспектам теории графов. Стоит отметить вклад Valiant L.G., определившего понятие ЦР-полноты, с помощью которого удалось объяснить вычислительную сложность некоторых проблем перечисления графов. После 1970-х много внимания уделялось асимптотическим оценкам и взаимосвязи между задачами перечисления и теорией случайных графов. В работах Эрдеша П. и Bollobas В. можно найти более подробную информацию об этом вероятностном подходе.

Аналитические методы, безусловно, относятся к числу наиболее мощных методов комбинаторного анализа. Они основываются на точном описании перечисляемых комбинаторных объектов с помощью производящих функций. Эти функции интерпретируются как аналитические объекты, то есть как отображения комплексной плоскости в себя. Их особенности определяют (асимптотически) коэффициенты производящих функций и позволяют получить оценки членов исходных последовательностей. В книге Flajolet P., Sedqewick R. по аналитической комбинаторике тщательно изложены основные известные к настоящему времени аналитические методы решения задач комбинаторного анализа, а также рассмотрены различные приложения этого подхода.

Теория перечисления графов интенсивно развивается, и интерес к этой области перечислительной комбинаторики постоянно возрастает, о чем говорят многочисленные работы последних лет отечественных и зарубежных исследователей: Багаев Г.Н., Воблый В.А., Ландо С.К, Леонтьев В.К., Звонкин А.К., Barvinok A., Bezâkovâ I., Brightwell G., Chebulu P., Creed P., Cryan M., Hartigan J., Greenhill C., Grohe M., Martin R., McKay B.D., Stefankovic D., Vazirani D., Vigoda E., Winkler P., Zhang J. и др.

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

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

• Подсчет числа различных эйлеровых ориентаций простого неориентированного графа (таких ориентаций ребер графа, для кото-

рых каждая вершина графа обладает одинаковым числом входящих и выходящих ребер).

• Подсчет числа различных эйлеровых циклов простого неориентированного графа (замкнутых путей, проходящих по каждому ребру графа ровно один раз).

• Подсчет числа различных помеченных остовных подграфов фиксированного графа, обладающих заданной последовательностью степеней вершин.

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

Общая методика исследования.

Доказательства асимптотических формул для рассматриваемых задач перечисления во многом аналогичны. Используемый метод является вариантом многомерного метода стационарной фазы. С помощью производящих функций ответ представляется в виде многомерного интеграла, имеющего вид f F(£)d£, где U — некоторая область в М™, рази

мерность п совпадает с числом вершин графа, а подынтегральное выражение F(£) состоит из большого числа множителей /,&(£), причем пары {j, к} соответствуют ребрам графа. Для каждой задачи строится некоторая небольшая область Box С U такая, что вектора £ € Box находятся в окрестности максимумов fjk(£)- Оценка интегралов происходит в два этапа:

1. Работа внутри «коробки». При £ £ Box, используя разложение в ряд Тейлора для функций fjk{£) в окрестности максимумов, оцениваемый интеграл сводится к интегралу гауссовского типа:

J F&d£= J exp

Box Box

где А — некоторая матрица, ассоциированная с графом, Т(£) является полиномом и константа и > 0. При определенных ограничениях на спектр А и размер «коробки» такие интегралы удается аппроксимировать.

2. «Упаковка». Если £ £ U \ Box, то найдется достаточно большое число множителей fjk{Q, значение которых существенно меньше, чем в «коробке». В результате удается показать, что при п —> оо

I \F(£)\d£ =0(1) J F(i)dC

U\Box Box

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

§1.2 работы посвящен задаче подсчета числа различных ориентаций ребер графа, для которых каждая вершина графа обладает одинаковым числом входящих и выходящих ребер. Такие ориентации называются эйлеровыми ориентациями.

В п. 1.2.1 приводится постановка задачи и обсуждается значимость задачи в различных научных областях. Кроме того, приводятся результаты Mihail M., Winkler Р. о jJP-полноте перечисления эйлеровых ориентации и существовании полиномиального приближенного вероятностного алгоритма для их подсчета. Этот алгоритм подробно обсуждается в п. 1.2.2.

В п. 1.2.3 рассматривается случай полного графа Кп. Даже в этом частном случае точное выражение числа эйлеровых ориентации ЕО(Кп) при нечетном п неизвестно (ЕО(Кп) = 0 при четном п). McKay B.D. доказал следующую асимптотическую формулу: при нечетном п —» оо

/оп+1 \ С™-1)/2

ЕО(Кп) = (L-\ п^е"1/2 (l + 0(п~^2+£)) (1)

для любого фиксированного е > 0.

При доказательстве формулы (1) число эйлеровых ориентации полного графа представлялось в виде многомерного интеграла. Аналогичное представление верно и в общем случае: пусть степени всех вершин графа G — четные, тогда

EO(G) = 2^TT~nS,

■к/2 7Г/2

S= J ••• J Д cos Ajk d£i. ..dÇn,

— 7Г/2 -tt/2 {vj.Vk}eEG

где EG — множество ребер графа, Ajk = Çj — Это представление используется для обобщения асимптотической формулы (1).

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

В п. 1.3.1 приводится постановка задачи, обсуждаются алгоритмические аспекты и рассматривается случай полного графа. Отметим, что задача подсчета числа эйлеровых циклов остается (j-полной уже для графов с небольшими степенями вершин (для регулярных степени 4), но, в отличии от задачи подсчета числа эйлеровых ориентации

для нее эффективные приближенные алгоритмы известны только для графов с малой плотностью.

В случае полного графа точное выражение числа эйлеровых циклов ЕС(Кп) при нечетном п неизвестно (ЕС(Кп) = 0 при четном п). McKay B.D., Robinson R.W. доказали следующую асимптотическую формулу: при нечетном п —» оо

ЕС(Кп) = е-^ + й n1-^1 (l + 0(n->/^)) =

= 2^п-^п^ ((П^А - (l + 0(n-№))

для любого фиксированного £ > 0.

При доказательстве формулы (2) число эйлеровых циклов полного графа представлялось в виде многомерного интеграла. В п. 1.3.2 получено аналогичное представление для общего случая: пусть степени всех вершин связного графа G — четные, тогда для любой вершины v графа G:

EC{G) = 2lEGl-"+17r-"5 П (f - l) !,

j=1 V '

71-/2 x/2

5= J ■■■ J Fv(0

-тг/2 -тг/2

Fv(i)= П cosAjkJ2 П (l + itanAj-fc),

{vj,vk}eEG Т6Г„ (Vj,vk)eET

где EG — множество ребер графа, Ajk = Çj — %, — множество остовных деревьев G, ориентированных таким образом, чтобы корневая вершина v не имела выходящих ребер, а любая другая вершина имела ровно одно выходящее ребро. Это представление используется для обобщения асимптотической формулы (2).

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

§1.4 работы посвящен задаче подсчета числа различных помеченных остовных подграфов фиксированного графа, обладающих заданной последовательностью степеней вершин s = (s\, S2, ■ ■ ■ ,sn). Такие подграфы называются также /-факторами, где / : VG —» N — функция, соответствующая заданной последовательности степеней вершин естественным образом: f(vj) = Sj.

В п. 1.4-1 формулируется постановка задачи, обсуждаются алгоритмические аспекты, а также приводится представление ответа в виде интеграла:

7Г 7Г

SGW=/ " 7 * • ■ ■

3 = 1

где EG — множество ребер графа, SG{s) — число различных помеченных подграфов графа G с заданной последовательностью степеней вершин s = (si,S2, • • • ,sn)T G Nn, вектор r G R".

Вышеприведенное представление используется для обобщения следующей асимптотической формулы (случай полного графа), приведенной в п. 1-4-2:

Теорема (McKay B.D., Wormald N.C.). Пусть s = . Предполо-

жим, что s € Nn таково, что SKn(s) > 0, min{s, п — s — 1} > an/ Inn для некоторого а > | и |sj — s| < 6п1//2+е при j = 1,... ,п для некоторых фиксированных b, е > 0. Тогда при п —> оо

SI<n{s) = V2 (2л"пЛ®+1(1 - A)n"s~)_t exp Qj _ 1д _ щп _ й)7з_

ч (3)

-R2ll + n(R2 - 1r3)74 + jj Д2( 1 - 2Л)п7з + O(n-C)) для любого ( < min{i, 5 — ¿Ь где

^ = ——Г) R = ^ттг—= —Г) • п — 1 2Л(1 - Л) р^ \ п — 1 у

Совершенно другой подход, основанный на случайной деформации графа, используется для нахождения асимптотики в случае, когда степени si,..., s„ небольшие. Этот результат, полученный McKay B.D. и Wormald N.C., также приводится в п. 1.4-2. Обе асимптотические формулы сводятся к одинаковому выражению:

SKn(s) ~ \/2exp Q - 4Л2Д ) SK^{s,X), (4)

где SKn(s, Л) обозначает «наивную» оценку, рассматриваемую в п. 1-4-3, которая определяется в общем случае следующим образом:

5С(5-,Л) = Лб(1-Л)1£С1-£П (dj), (5)

где di,... ,d,n — степени вершин графа G. Одним из результатов настоящей работы является обобщение формулы (4).

В §1.5 работы коротко излагается общая схема доказательства основных результатов.

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

J ехр (-(РАв + Т{в)) de,

где — некоторая область в К", А — симметрическая положительно определенная матрица, Т : К" —> С — полином.

В §2.1 работы приводятся необходимые понятия и предположения. Используя покоординатное масштабирование вектора в, интеграл всегда можно свести к случаю, когда диагональные элементы матрицы А равны 1. Поэтому полагается для простоты, что А = I + X, где I — единичная те х п матрица, а X — некоторая симметрическая матрица с нулевыми диагональными элементами.

Для действительного р > 1 и вектора fëR" определяется норма

1/р

IIxIL =

р ~ |

j=1

В случае р = оо пусть

;И1оо =тах|х^-|.

3

(6)

Векторной р-норме соответствует матричная норма

||л||Р = зир и •

х^О \\ЩР

Рассматриваются следующие предположения на матрицу А:

А — положительно определенная симметрическая матрица А = 1 + Х, < Х^=0, НЛ^На^б,

Диагональные элементы матриц, удовлетворяющих (6), асимптотически доминируют над остальными элементами. Свойства таких матриц обсуждаются в §2.2.

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

Р{х) = а^-ес,

||<*1|1<с1е8Р

где deg Р обозначает степень полинома Р. Функции 1г\ (высота полинома) и /¿2 (четная высота полинома) определяются в п. 2.3.1 следующим образом:

/ц(Р)= тах п|8ирр(Г||аг|,

|| 4 !<<1ецР

Н2{Р)= тах гг|5ирр2<г"1|а2(Г|,

||2<?||1<ае6Р

где 2(1= (2^,2^, •• -,2<1п). Пусть ко = 1 и

(2з - 1)!! Ш .

Функции х°1 Ха 11 Ха — Х° + Ха определяется в п. 2.3.2 линейным образом, причем

... = ка1/2ка2/2 ... кЛп/2, если все (13 — четные,

Х°(х11Х22 ■ ■ ■ %пп) = 0' в остальных случаях; к<1

где обозначет (к,1)-й элемент матрицы Л-1.

В §2.4 работы доказывается основной результат второй главы: Теорема 1. Пусть константы а,Ъ,с,г,е > 0, 5 6 N зафиксированы, причем 5э£ < 1/2. Пусть п х п матрица А удовлетворяет (6). Тогда для любых полиномов Р,(Э : Кп —> С таких, что с^Р < в, degQ < в, кх{Р) < с, (<5) < у/сп и /гг(<3) = 0, выполняется:

i е-ёгав+р(вно(е)с[у = (1 + ¿(г> а) р) д)) ехл(р+а2/2) i и„{гп') К"

|5(г,А,Р,<3)| < Сп~1/2+5ее,

где

ип(р) = {№,■■■ ,вп)Т е К" : ||0||оо < Р}

и константа С > 0 зависит только от а, Ъ, с, г, в, е.

При выполненных предположениях Теоремы 1 показывается, в частности, что значение ха(Р + Ф2/2) ограничено по модулю некоторой константой, зависящей только от о, Ь, с, г, я, е.

Третья глава посвящена исследованию свойств классов графов со спектральными ограничениями. Большинство результатов непосредственно следуют из известных в литературе свойств используемых спектральных параметров. Тем не менее некоторые из полученных в этой главе результатов, см., например, Предложения 5, 8, 10, являются новыми.

В §3.1 работы рассматривается класс графов, обладающих сильными перемешивающими свойствами. Различные эквивалентные определения этого класса приводятся в п. 3.1.1.

Для неориентированого простого графа С с множеством вершин УС = {У\,У2, ■ ■ ■ ,г>„} и множеством ребер ЕС определяется п х п матрица Ь следующим образом:

Ь

к

-1, {ь^ук}еЕС, <1^, 3 = к,

О, в остальных случаях,

где п = |У<3| и ^ обозначает степень г^ (Е УС. Матрица Ь = Ь(С) называется матрицей Лапласа графа (3. Собственные значения

А1 < Л2 < ... < А„

матрицы Ь являются неотрицательными вещественными числами, причем кратность нулевого собственного значения совпадает с количеством компонент связности, в частности, А1 = 0. Число Л2 = Л2(С) называется алгебраической связностью графа С.

Граф б называется 7-перемешивающим, если

алгебраическая связность Л2 (С) > 7|УС|.

Этот класс графов называется в диссертации классом графов с сильными перемешивающими свойствами.

В п. 3.1.1 рассматриваются также другие классические параметры графов, которые отражают свойства перемешиваемости: константа Нигера (изопериметрическое число), спектральный зазор между 1 и вторым по величине собственным значением матрицы вероятностей перехода случайного блуждания на графе. В п. 3.1.2 показано, что эти параметры позволяют эквивалентным образом определить класс графов, обладающих сильными перемешивающими свойствами. П. 3.1.3 посвящен обсуждению различных примеров и контрпримеров.

В п. 3.1.4 исследуются структурные свойства 7-перемешивающих графов. Рассматриваются Б — Т пути в графе б, то есть пути, один конец которых принадлежит 5", другой — Т, где 5' и Т являются подмножествами множества вершин УС. Доказывается следующий результат:

Предложение 5. Пусть С — простой 7-перемешивающий граф с п вершинами для некоторого 7 > 0. Подмножества вершин Б, Т С Уб таковы, что 5 П Т = 0. Тогда существуют /хпшш {|5|, |Г|} попарно не пересекающихся по ребрам Б — Т путей длины не превосходящей Н, причем константы ц,Н > 0 зависят только от 7.

В п. 3.1.5 исследуются свойства матриц Лапласа 7-перемешиваю-щих графов. В частности, обсуждается сведение к матрицам, удовлетворяющим условиям (6).

В §3.2 работы рассматривается класс существенно недвудольных графов. Различные эквивалентные определения этого класса приводятся в п. 3.2.1.

Для неориентированого простого графа С с множеством вершин VС? = {у1,У2, ■ ■ ■, уп} и множеством ребер ЕС определяется п х п матрица <2 следующим образом:

где п = \УС\ и сЦ обозначает степень Vj € УС. Матрица <3 = (¿{С) называется беззнаковой матрицей Лапласа или (^-матрицей графа С. Собственные значения

матрицы С} являются неотрицательными вещественными числами, причем кратность нулевого собственного значения равна числу двудольных компонент связности графа, в частности, = 0 тогда и только тогда, когда какая-то из компонент связности является двудольным

1, {уЛ,ук}€ЕС, 2 = к,

0, в остальных случаях,

91 > 42 > ■ ■ ■ > Чп

графов. Число дп = д(С?) называется алгебраической недвудольностью (англ. ЫрагШепевз) графа С?.

Граф С? называется 7-недвудольным, если

алгебраическая недвудольность д(С) > 7|УС?|.

Этот класс графов называется в диссертации классом существенно недвудольных графов.

В п. 3.2.1 рассматриваются также другие параметры графов: спектральный зазор между — 1 и наименьшим собственным значением матрицы вероятностей перехода случайного блуждания на графе, аналог константы Чигера. Показано, что эти параметры позволяют эквивалентным образом определить класс существенно недвудольных графов. П. 3.2.2 посвящен обсуждению различных примеров и контрпримеров.

В п. 3.2.3 исследуются структурные свойства 7-недвудольных графов. Рассматриваются ¿'-пути нечетной длины в графе С?, то есть пути, оба конца которых принадлежит 5, где Б С УС?. Доказывается следующий результат:

Предложение 8. Пусть С? — простой 7-недвудольный граф с п вершинами для некоторого 7 > 0. Тогда для любого 0 ф Б С УС? существует не менее /т|5| попарно не имеющих общих ребер Б-путей нечетной длины, не превосходящей Н, причем константы ц, Н > 0 зависят только от 7.

В п. 3.2-4 исследуются свойства матриц Лапласа 7-недвудольных графов. В частности, обсуждается сведение к матрицам, удовлетворяющим условиям (6).

В §3.3 рассматривается модель Эрдеша-Реньи случайного графа. В этой модели каждое возможное ребро графа присутствует в графе независимо с некоторой фиксированной вероятностью 0 < р < 1. Доказывается следующий результат:

Предложение 10. Вероятность того, что случайный граф с п вершинами в модели Эрдеша-Реньи является одновременно и 7-перемеши-

вающим, и 7-недвудольным, не менее 1 — /3 71, причем константы 7 > 0, (3 > 1 зависят только от р.

В §3.4 работы обсуждается комбинаторный смысл миноров матрицы Лапласа и определителя (^-матрицы. В частности,

¿еЬЬ^ = t(G), (7)

где ¿((У) — число остовных деревьев графа (7, а матрица 1ДГ) получается удалением г-го столбца и г-й строки из матрица Лапласа Ь графа С. Формула (7), известная также как матричная теорема о деревьях, была впервые получена неявным образом Кирхгофом Г. в 1847 г.

В четвертой главе доказываются основные результаты диссертационной работы.

§4.1 работы посвящен перечислению эйлеровых ориентации простого неориентированного графа.

В п. 4-1-1 формулируется следующая теорема:

Теорема 3. Пусть С — неориентированный простой граф с п вершинами Ух, «2,..., ип, имеющими четную степень. Пусть для некоторого фиксированного 7 > 0 граф С является 7-перемешивающим. Тогда:

ЕО{в) = (1 + 5ео(в)) ^»г^+^тг-^ 1 / 1

Кео~ 4 ^ {dj + l^dk + l

{vjtvk}eEG х 1 к

где dj — степень вершины. Vj, t(G) — число остовных деревьев G (эффективно вычисляется с помощью (7)), и для любого е > О

\5eo(G)[<Ceon-^2+e,

где константа Сео > 0 зависит только от 7 и е.

Доказательство Теоремы 3 приводится в п. 4-1-2 и п. 4-1-3-

§4.2 работы посвящен перечислению эйлеровых циклов в простом неориентированном связном графе.

В п. 4-2.1 формулируется следующая теорема:

Теорема 4. Пусть все предположения Теоремы 3 выполнены, тогда:

EC(G) = (1 + Sec(G))

Кес 4 Е Ы + 1 дк + 1) '

где ¿2 — степень вершины V], — число остовных деревьев С (эффективно вычисляется с помощью (7)), и для любого е > О

где константа Сес > 0 зависит только от 7 и е.

Доказательство Теоремы 3 приводится в п. 4-2.2, п. 4-2.3 и п. 4-2-4-Для случая полного графа (7 = Кп выполняется:

Л 2(1<п) = п, \ЕКп\ = п[п~1\ 1{Кп)=пп-\

1^/1 1\2 п- 1

4 , , \п п) 2п

{v¡,vk}eEKn

х~-\ Е fi-iV^

4 ' V ti п

{Vj,vk}eEKn х

Результаты Теорем 3 и 4 для случая полного графа сводятся к формулам (1) и (2), соответственно.

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

Пусть вектор d = (di,d,2, - - - ,dn)T соответствует степеням вершин графа Gen вершинами, а вектор s = (si, S2, • • •, sn)T — заданной по-

следовательности степеней вершин подграфа. Число различных помеченных остовных подграфов графа С с заданными степенями вершин в2,..., в„ обозначается

В п. 4-3.1 формулируется следующая теорема:

Теорема 5. Пусть константы, а,/3,7 > 0 иО < с < 1/2 зафиксированы. Пусть б — неориентированный простой 7-недвудольный граф с п вершинами У\, г>2, • • •, ип, причем константа Чигера (изоперимет-рическое число) г(С?) > па. Тогда для любых в = (вь..., вга)т е К™ и А 6 [б, 1 — е] таких, что 81 + ... + =0 (то(1 2) и тах — Аа!,-1 < (3,

l<j<n

выполняется:

5С(а) = (1 + 5вя(я,С))

2е »» (27г)"

' " V (1 - А)\ео\-Е+$

_ юГд,Т, (1 - 2А)2й?Т1 а7^-1^ (1 - 2Х)атги 89 ~ 4 + 12А(1 — А) + 2А(1-А) + 2А(1 - А) '

где Е = (вх + ... + вп)/2, |.ЕС| - число ребер графа (3, а = — ..., вп — \<1п)т, ги = 1 = (1,..., 1)т,

причем для любого е > 0

< Сздтг"1/2^,

где константа Сзд > 0 зависит только от а, /3,7, е,£.

Доказательство Теоремы 5 приводится в п. 4-3.2 и п. 4-3.3. В п. 4-3-4 обсуждается «наивная» оценка (5). Доказывается следующий результат:

Предложение 11. При выполненных предположениях Теоремы 5:

Л пг -1/2+еЛ 2еКд \Aiet В

56(5, А)

шт0й; ат(£>"1 - <2-1)а

=--Г~ + ~ + 2А(1 — А) •

Для случая полного графа G = Кп выполняется: алгебраическая недвудольность q(Kn) = п—2, число ребер \ЕКп\ = и при п —> оо

detQ = (2гг — 2)(n - 2)"_1 = (l + C^n"1)) 2е"2пп, det D = (п — 1)" = (1 + 0(п-1))е"1пп,

{vj,vk}eVG 4 7

—* 71

гмт1 = -- = 1 + 0(n-1), aTw = 71,

n — 1

aTQ~1a = n72 - 7j/2 + C^n"1), aTD~1a = П72 4- 0(n-1),

1 (1 - 2Л)2 72 - 7?/2 (1 - 2A)71 , =

59 2 12Л(1 — А) 2A(1 — A) 2Л(1 — A) j

= I + lR ~ nRl2 " + Д(1 " 2Л)71 +

KA = -\ + l-R1l + 0{n~l),

где

1 n / a 4 ^

Д= 2A(1-A)'

Если выбрать A = то ai + a-2 + ... + an = 0 и поэтому:

SKn(s) ~ л/2 (2тгпА^+1(1 - exp ^ - - nR72j ,

SKn(s) ~ -v/2e1/,4S^(s, A).

Результаты Теоремы 4 и Предложения 11 для случая полного графа сводятся к формулам (3) и (4) при условии max \sj — А(п — 1)| = 0(1).

1 <j<n

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Аналитический подход, использованный McKay B.D, Robinson R.W., Wormald N.C. для случая полного графа, адаптирован для существенно более широких классов графов со спектральными ограничениями. Получены новые явные асимптотические формулы для эйлеровых ориентаций, эйлеровых циклов и помеченных подграфов с заданной последовательностью степеней вершин.

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

3. При условии асимптотического диагонального доминирования соответствующей матрицы квадратичной формы получена асимптотика интеграла гауссовского типа с полиномиальным возмущением в показателе экспоненты.

Автор выражает благодарность научному руководителю к.ф.-м.н. Тарасову С.П. за постановки задач и постоянное внимание к работе, а также профессору McKay B.D. за обсуждение работы и ряд ценных замечаний.

Работа поддержана грантом РФФИ №11-01-00398а.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Исаев М.И. Асимптотика числа эйлеровых циклов в плотных графах// Труды 53-й научной конференции МФТИ «Современные проблемы фундаментальной и прикладной математики», Управление и прикл. математика, М.:МФТИ, 2010, Т. 1, С. 72-73.

2. ИСАЕВ М.И. Свойства графов с большой алгебраической связностью// Труды 54-й научной конференции МФТИ «Проблемы

фундаментальных и прикладных естественных и технических наук в современном информационном обществе», Управление и прикладная математика, М.: МФТИ, 2011, Т. 1, С. 53-54.

3. Исаев М.И. Асимптотическая формула для числа эйлеровых ориентаций в графах с большой алгебраической связностью// Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова, М.: МГУ, 2012, С. 288.

4. Исаев М.И. Задача перечисления эйлеровых циклов в графах// Труды 55-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе», Управление и прикладная математика, М.: МФТИ, 2012, Т. 1, С. 155-156.

5. Исаев М.И. Асимптотика числа подграфов с заданными степенями вершин в недвудольных графах// Тезисы международной конференции «Алгебра и комбинаторика», посвященной 60-летию A.A. Махнева, Екатеринбург: изд. «УМЦ- УПИ», 2013, С. 58-60.

6. Исаев М.И. Оценка числа подграфов с заданными степенями вершин// Тезисы международной конференции «Дискретная оптимизация и исследование операций», Новосибирск: изд. Ин-та математики, 2013, С. 106.

7. Исаев М.И. Асимптотическое поведение числа эйлеровых ориентаций в графах// Математические заметки, 2013, Т. 93, В. 6, С. 828-843.

8. Исаев М.И., Исаева К.В. О классе графов, обладающих сильными перемешивающими свойствами// Труды МФТИ, 2013, Т, 5, № 3, С. 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 х 841/16. Усл. печ. л. 1,0. Тираж 130 экз. Заказ № 260. Федеральное государственное бюджетное образовательное высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9.

Московский физико-технический институт

(государственный университет) Кафедра математических основ управления

На правах рукописи УДК 519.1

04201361485

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

АНАЛИТИЧЕСКИЙ ПОДХОД К ЗАДАЧАМ ПЕРЕЧИСЛЕНИЯ ГРАФОВ СО СПЕКТРАЛЬНЫМИ ОГРАНИЧЕНИЯМИ

Специальность 01.01.09 «Дискретная математика и математическая кибернетика»

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель кандидат физико-математических наук,

С.П. Тарасов

Москва 2013

ОГЛАВЛЕНИЕ

Введение 5

Глава 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. Комбинаторный смысл миноров матрицы Лапласа и определителя (^-матрицы...........................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

Приложение А. Доказательство Леммы 4 136

ВВЕДЕНИЕ

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

Впервые понятие «граф» ввел в 1936 году венгерский математик Кениг Д. Однако первая работа [39] по теории графов была написана еще в 1736 году Эйлером Л., в которой он не только решил популярную в то время «задачу о Кенигсбергских мостах», но и получил критерий существования в графе специального маршрута (эйлерова цикла, как теперь его называют).

Хотя Эйлер Л. и рассматривал задачи подсчета некоторых типов триангулированных многоугольников на плоскости, все же существенные шаги в теории перечисления графов были сделаны лишь в девятнадцатом столетии. В своих работах, опубликованных в 1857-1889 гг., Кэли А. получил формулы для количества деревьев трех типов: помеченных, корневых и обычных, а также связанных с ними химических структур. Ещё ранее Кирхгоф Г. в [61] нашел в неявной форме число остовных деревьев заданного графа, а значит, в частности, число помеченных деревьев.

В настоящее время перечисление графов представляет собой развитую теорию, занимающую существенное место в области комбинаторного анализа. В книге [76] собраны известные результаты о подсчете помеченных деревьев и свойствах случайных деревьев. В монографии [52] приведено большое количество разнообразных задач перечисления непомеченных графов с определенными свойствами. Для задач такого типа используется алгебраический подход, основанный на теории перечисления Пойа (см., например, [78]). Принцип включения и исключения, обращение Мёбиуса, а также многие другие известные методы, используемые в перечислительной комбинаторике, подробно изложены в [84].

Во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики, и, в частности, интерес к алгоритмическим аспектам перечисления графов (см. [24], [58], [89]). После 1970-х много внимания уделялось асимптотическим оценкам и взаимосвязи между задачами перечисления и теорией случайных графов. Для более подробной информации о применении этого вероятностного подхода см., например, [22], [71].

Аналитические методы, безусловно, относятся к числу наиболее мощных методов комбинаторного анализа. Они основываются на точном описании перечисляемых комбинаторных объектов с помощью производящих функций. Эти функции интерпретируются как аналитические объекты, то есть как отображения комплексной плоскости в себя. Их особенности определяют (асимптотически) коэффициенты производящих функций и позволяют получить оценки членов исходных последовательностей. В книге [44] тщательно изложены основные известные на настоящее время аналитические методы, а также рассмотрены как классические, так и современные приложения этого подхода.

Хотя теория перечисления графов интенсивно развивается уже более 50 лет, интерес к этой области перечислительной комбинаторики не пропал, о

чем говорят многочисленные работы последних лет: [18], [20], [21], [23], [25], [34], [45], [50], [68].

В данной работе результаты из [67], [69], [70] об асимптотике числа эйлеровых ориентации, эйлеровых циклов и помеченных подграфов с заданной последовательностью степеней вершин в полных графах обобщаются для существенно более широких классов графов со спектральными ограничениями. На примере этих классических задач продемонстрирована универсальность аналитического подхода для решения проблем перечисления графов.

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения.

В первой главе обсуждаются проблемы и методы решения рассматриваемых задач. В §1.1 формулируются основные понятия и результаты теории вычислительной сложности проблем перечисления. В §1.2 - §1.4 приводятся постановки задач о подсчете эйлеровых ориентации, эйлеровых циклов и помеченных подграфов с заданной последовательностью степеней вершин. В этих параграфах подробно обсуждаются известные результаты, приложения и подходы для каждой из рассматриваемых проблем. В §1.5 излагается общая схема рассуждения: используя производящие функции, задачи сводятся к оценке многомерных интегралов гауссовского типа.

Вторая глава посвящена асимптотическому анализу интегралов гауссовского типа. В §2.1 приводятся необходимые понятия и предположения. Одним из предположений является асимптотическое диагональное доминирование соответствующей матрицы квадратичной формы. Свойства таких матриц обсуждаются в §2.2. Основной результат о асимптотике интегралов гауссовского типа доказывается в §2.4. Для формулировки этого результата используются несколько специальных функций над полиномами, которые вводятся в §2.3.

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

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

Четвертая глава посвящена основным результатам данной работы. В каждом из §4.1-4.3 сначала формулируется асимптотическая формула для соответствующей задачи, затем приводится доказательство, основанное на результатах из Главы 2 и Главы 3.

В Приложении данной работы приведены доказательства некоторых вспомогательных лемм.

В диссертации получены следующие результаты, характеризущиеся научной новизной:

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

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

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

4. Определена асимптотика интеграла гауссовского типа, при условии асимптотического диагонального доминирования соответствующей матрицы квадратичной формы.

Основные результаты работы докладывались на научных семинарах в следующих организациях:

-9- Вычислительный центр им. А.А. Дородницына РАН (Москва, 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 (а именно: [8], [9], [56]) — в изданих из списка, рекомендованного ВАК РФ.

Глава 1.

НЕКОТОРЫЕ ЗАДАЧИ ПЕРЕЧИСЛЕНИЯ ГРАФОВ: ПРОБЛЕМЫ И МЕТОДЫ ИХ РЕШЕНИЯ

1.1. Проблемы алгоритмического решения задач перечисления

Наиболее изученными объектами теории сложности вычислений являются задачи распознавания. Такие задачи можно охарактеризовать вопросом «принадлежит ли указанное слово языку?» и множеством ответов {«да», «нет»}. Как правило, каждой задаче распознавания естественным образом соответствует задача перечисления, в постановке которой фигурирует вопрос «сколько?». Например:

• Гамилътонов цикл. Сколько существует в заданном графе различных простых циклов, содержащих все вершины?

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

• Клика. Сколько существует в заданном графе различных полных (т.е. любые две вершины соединены ребром) подграфов из к вершин?

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

ны Тьюринга, работающей за полиномиальное время. Класс (JР может быть также определен как класс задач перечисления, соответствующих задачам распознавания из NP. Задачи перечисления, соответствующие ./VP-полным задачам (например, существование гамильтонова цикла, вершинного покрытия или клики заданной мощности), обычно являются $Р-полными (см. работу [27]) и ввиду результатов Toda S. (см. Теорему 4.7 из [86]) считаются чрезвычайно трудными с точки зрения вычислительной сложности.

Одним из активно развивающихся подходов для практического решения вычислительно трудных задач является построение параметризированных алгоритмов. Роль параметра в таких алгоритмах — учесть информацию о структуре входных данных алгоритма и выделить основной источник неполиномиальной сложности. Формальное определение следующее: параметризирован-ная задача с длиной входа п считается полиномиально разрешимой с фиксированным параметром, или FPT-разрешимой (Fixed-Parameter Tractable), если она может быть решена некоторым параметризированным алгоритмом за время

к) = О (п0(1) • /(/с))

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

Например, для задачи о вершинном покрытии в качестве параметра можно взять мощность искомого набора вершин. Используя факт, что для любой вершины либо она входит в набор, либо все смежные с ней вершины, любое покрытие мощности, не превосходящей /с, находится за время 0(п 2к). В качестве примера преблемьт, которая не является FPT-разрешимой, обычно рассматривается задача о клике. Для более подробной информации о теории параметризированной сложности см., например, [41], [45] и ссылки, приведенные там.

Другим важным подходом для решения вычислительно трудных задач на практике является разработка приближенных и вероятностных алгоритмов, для которых:

1 - £ < Fout/Fexact < 1 + £ (1.1)

или

Pr(l - г < Fout/Fexact < 1 + е) > 1 - (1.2)

где Fexact обозначает искомое значение, Fout — результат работы алгоритма и константы ô из интервала (0,1).

• FPTAS. Полностью полиномиальной аппроксимационной схемой называется приближенный алгоритм, в котором уровень точности е выступает в качестве параметра, причем алгоритм удовлетворяет (1.1) и время работы ограничено полиномом от длины входы и величины е~1.

Любая задача, для которой существует полностью полиномиальная аппрок-симационная схема, является FPT-разрешимой (см. Секцию 3 в [41]).

• FPRAS. Полностью полиномиальной рандомизированной аппроксимационной схемой называется приближенный алгоритм, в котором уровень точности е и константа <5 выступают в качестве параметров, причем алгоритм удовлетворяет (1.2) и время работы ограничено полиномом от длины входы и величин б"1, log<5-1.

Построение приближенных и вероятностных полиномиальных алгоритмов для задач перечисления, соответствующим NP-полным задачам, сопряжено с рядом трудностей (см. [36], [59]). Действительно, подобные алгоритмы позволяют сравнить искомое значение с 0 и тем самым решить соответствующую задачу распознавания.

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

Например, в [18] доказано существование полностью полиномиальной рандомизированной аппроксимационной схемы для числа гамильтоновых циклов в плотных графах (плотность графа может быть рассмотрена в качестве параметра). Отметим также результаты из [17] о возможности построения в случае большой плотности приближенных алгоритмов для различных трудных задач оптимизации.

Удивительно, что некоторые JjP-полные проблемы соответствуют легким задачам распознавания из класса Р. В [89] показано, что задача перечисления совершенных паросочетаний в двудольном графе является {|Р-полной. Эта задача эквивалентна подсчету перманента п х п матрицы А, все элементы которой равны 0 или 1,

per А =

О" j

где сумма по всем п! перестановкам а множества {1,2,... ,п} (аналогично детерминанту матрицы, только все слагаемые положительного знака).

Следующ�