Содержание к диссертации
Введение
1. Наследственные классы 9
1.1. Терминология 9
1.2. Определение и примеры наследственных классов 12
1.3. Энтропия 17
2. Критические классы 24
2.1. А дольные графы и ранг 24
2.2. Лемма о матрицах 28
2.3. Энтропия и ранг 31
2.4. Критические классы 35
2.5. Примеры и следствия 38
3. Классы ранга 1 43
3.1. Слои и ярусы 43
3.2. Константный ярус 44
3.3. Полиномиальный ярус 45
3.4. Экспоненциальный ярус 49
3.5 Факториальный ярус 52
4. Независимые множества 55
4.1. Простые и сложные классы 55
4.2. Операции над классами графов 61
4.3. Сильно наследственные а-простые классы 65
4.4. Граничные классы 67
5. Некоторые а-простые классы 72
5.1. Область эффективности переборной стратегии 72
5.2. Класс Free(F,P8) 78
5.3. Класс Free(F) 87
5.4. Классы Free(P5) и Ргее{Р2+Ръ)
6. Кодирование графов 103
6.1. Универсальное кодирование 104
6.2. Оценки трудоемкости 108
Литература
- Определение и примеры наследственных классов
- Энтропия и ранг
- Полиномиальный ярус
- Сильно наследственные а-простые классы
Определение и примеры наследственных классов
Пусть теперь щ 0 и Sj 0 для некоторого і. Не теряя общности, можно считать, что і - к. Положим п = 0(mi,si,...,m/(,sj -) и рассмотрим (т ,..., )-матрицу А с п различными столбцами, не содержащую полной (si,..., )-подматрицы. Выберем в ней какую-либо строчку из к-й полосы. Если удалить эту строчку, то в полученной матрице А могут появиться одинаковые столбцы. Разобьем А на две подматрицы: X - она состоит из столбцов, имеющих дубликаты, Y - из уникальных столбцов. В матрице X каждый столбец встречается дважды. Разобьем ее на две подматрицы, классифицируя столбцы по элементам удаленной строки: в подматрицу Ха включим те столбцы у которых в удаленной стоке был элемент а, а є {0,1}. Если в каждой из матриц Ха по щ столбцов, a Y состоит из п2 столбцов, то 2щ + п - п . Допустим, что в XQ имеется полная (5,i,..., _i, - 1) подматрица. Такая же подматрица и с тем же множеством строк есть в Х\. Взяв эти две подматрицы и добавив элементы зо удаленной ранее строки, получили бы полную (si,...,sk)-подматрицу в матрице А. Следовательно, в XQ не может быть полных (s\,..., sk_\, sk - 1) -подматриц, поэтому щ &{mbsh...,mk_bsk_bmk - \,sk - 1). (2.1) Рассмотрим теперь подматрицу, получаемую объединением столбцов матриц XQ И Г. В ней нет полных (s\,...,sk)-подматриц, следовательно, щ+п2 &(mhsh...,mk_hsk_hmk -\,sk). (2.2) Складывая (2.1) и (2.2), получаем 0(musi,...,mk,sk) 0(mi,si,...,mk -l,sk -l) + 3 (mbsi,...,mk -l,sk) (2.3) Завершить доказательство можно индукцией по величине к Р - _imisi Случай р = О рассмотрен выше, а в неравенстве i=l (2.3) оба слагаемых в правой части имеют меньшее значение р, чем левая часть. Поэтому можно применить предположение индукции: b(mhsh...tmk,sk) 2т\+---+тк _ nij \ і J ґк-\ mj Гт.\Лґ П І 0=1 i=Sj ( mk\+ m mk - i\ і J і J l=sk W Эта лемма будет ниже применяться при гщ =...= тк = т, s\ =...= sk = s. Обозначим для этого случая b(m,s,...,m,s) = (f k(m,s). Применяя неравенство Бернулли и границу Чернова для суммы биномиальных коэффициентов ([35], простое доказательство можно найти в [19], стр.303), получаем при s т/2 оценку S k{mis) = 2mk кІ -ЩЛ k2m(k-l+H(H) t (2.4) і=0 где Н(х) = -х log х-(1-х) log(l - x)
Замечание. Формулировка теоремы охватывает и «сингулярные» крайние случаи: конечные классы, для которых rg = 0, h- -сю, и класс всех графов, для которого rg - со, h - 1. В приводимом ниже доказательстве рассматриваются все остальные случаи, т.е. когда X - бесконечный наследственный класс, отличный от G. Доказательство. Пусть rg(X) = к. Тогда х[к] = ф] кЛп2 и, учитывая, что Хи хЩ, имеем \Xn\ G[ = 2V2 , следовательно, h(X) 1 - . rg(X)
Доказательство обратного неравенства проводим индукцией по к. По понятной причине нельзя взять в качестве базы индукции случай к - 0. Поэтому мы начинаем с к = 1, но так как доказательства для базы и шага индукции оказываются очень сходными, проводим их одновременно, следя за тем, чтобы индуктивное предположение применялось только при к 1. Итак, пусть rg(X) = k 0. Это означает, что существует (к +1) -дольный граф Я, никакое пополнение которого не принадлежит X. Любой {к +1) -дольный граф, порожденным подграфом которого является Н, тоже будет обладать этим свойством, поэтому можно считать, что в Н все доли имеют одинаковую мощность d Пусть Н - к -дольный граф, полученный из Н удалением одной доли. Возьмем такие т и t d + f\ogd \, чтобы для графа Н выполнялись условия леммы 2.1. Пусть F - граф, существование которого утверждается в этой лемме, т.е. {к,т) -граф, в котором каждый порожденный (к,t) -подграф содержит порожденный подграф, изоморфный Н . Обозначим через Y множество всех графов из X, у которых нет порожденных подграфов, изоморфных пополнениям графа F, Z = X-Y. При к = 1 Н - пустой граф и в качестве F тоже можно взять пустой граф. Так как любой граф является пополнением пустого графа с тем же числом вершин, то в этом случае \Yn\- 0 при п т. При к 1 имеем rg(Y) к, следовательно, по предположению индукции, А(У) 1 !— и к-\ + є(п) п2 (к-2 2 \к-\ \Yn\ 2 K , (2.5) где є{п) - 0 при п — СО . Оценим мощность множества Zn. Пусть G aZn. Граф G содержит порожденный подграф, изоморфный пополнению графа F. Пусть A\,...,Ai - множества вершин графа G, соответствующие долям графа F при таком изоморфизме, к А = (JАг В -VG- А. Граф G однозначно определяется i=l следующей совокупностью объектов: 1) пополнение графа F; 2) инъекция множества вершин графа F в множество 3) граф G(B); 4) граф G(A,B). му Существует ровно 2 различных пополнений графа F. Число отображений из п. 2) не превосходит п . Граф G(B можно выбрать не более чем 1 ,-/ 1 способами. Рассмотрим граф G(A,B). Образуем его «двудольную» матрицу смежности, в которой строки соответствуют вершинам из множества А, столбцы - вершинам из В. Ее можно рассматривать как состоящую из к полос, соответствующих множествам А,. Допустим, в ней есть полная (t,...,t) подматрица. Пусть А - множество вершин, соответствующих строкам, В - столбцам этой подматрицы. По лемме 2.1 в А найдется подмножество А" мощности Ы такое, что подграф G(A") является пополнением графа Н . Для каждого подмножества М cz А" в В имеется ровно 2 вершин, окрестность которых в А совпадает с М. Так как t d+ \\о%сГ\, то при любом к, но тогда оказывается, что в В можно выбрать d вершин, которые вместе с А" порождают в графе G подграф, являющийся пополнением графа К Следовательно, в матрице смежности графа G(A,B) нет полных (/,...,/)-подматриц. По лемме 2.2 число различных столбцов в этой матрице не превосходит 0 (w,f). Такую матрицу, а, следовательно, и граф G(A,B можно выбрать не более чем
Энтропия и ранг
Для каждого класса, фигурирующего в (Э.З), функция logXJ имеет порядок «logп, т.е. по порядку совпадает с log(«!). Это дает основание назвать следующий ярус факториальным. Из теоремы 3.3 следует, что в факториальном ярусе имеется ровно девять минимальных элементов. Эта информация, однако, полезна более для характеристики нижележащих ярусов, чем самого факториального. В настоящее время не известно аналогичного описания факториального яруса через «запрещенные» классы, т.е. минимальные классы вышележащего яруса, как не известно, каков этот ярус и даже существует ли вообще ярус, непосредственно следующий за факториальным. Вместе с тем факториальный ярус значительно интереснее предыдущих хотя бы тем, что содержит многие известные классы: леса, планарные графы, реберные графы и т.д. К тому же этот ярус и в чисто количественном отношении богаче предыдущих. С помощью теоремы 3.3 нетрудно показать, что каждый экспоненциальный (а тем более полиномиальный или константный) класс является конечно определенным. Поэтому множество всех таких классов счетно. С другой стороны, уже в классе всех лесов For содержится континуальное семейство факториальных подклассов. Действительно, определим мост как дерево, в котором степени вершин не превосходят 3, причем имеется точно две вершины степени 3 и каждая из них смежна с двумя вершинами степени 1. Если X - произвольное множество мостов, то класс For/X включает множество Deg(l) и, следовательно, является факториальным. Эти классы, соответствующие разным множествам X, различны, так как ни один мост не является подграфом другого моста. В оставшейся части этого раздела будут охарактеризованы конечно определенные сильно наследственные факториальные классы. Лемма 3.2. Если в графе G степень каждой вершины не меныие чем к, то любое дерево с к + \ вершиной является подграфом графа G. Доказательство. Пусть Т - дерево с вершинами VQ , v\,... V, причем вершины занумерованы таким образом, что подграф Ті - T(VQ,V\,...,VI) при любом і является деревом. Тогда вершина Vj в этом подграфе имеет степень 1. Покажем, что если в графе G, у которого степень каждой вершины не меньше к, есть подграф, изоморфный дереву 7j_i, то в нем есть и подграф, изоморфный дереву 7}. Действительно, пусть Vj - вершина, смежная с V/ в дереве 7}, а - образ вершины Vj при изоморфном отображении дерева Tj_\ в подграф графа G. Так как степень вершины а не меньше к и / к, то в G имеется вершина Ь, смежная с а и отличная от образов всех остальных вершин дерева 7 _j. Но тогда мы можем продолжить это отображение до изоморфизма дерева 7] в подграф графа G, поставив в соответствие вершине уг вершину Ь, а ребру (v/,v,) ребро (Ь,а).
Доказательство. Так как любой лес является подграфом дерева, то достаточно рассмотреть случай, когда классу X не принадлежит некоторое дерево Т. Если t - число вершин в Т, то по лемме 3.2 в любом графе G еХ имеется вершина степени не более t - 2. Если такую вершину удалить из G, то в оставшемся графе также будет вершина степени не более t - 2, и т.д. Отсюда следует, что в каждом графе из Хп число ребер не превосходит n(t - 2). Поэтому f (ri) \ Доказательство. Пусть k - длина наибольшего цикла, встречающегося в запрещенных подграфах для класса X. Тогда X содержит все графы, обхват которых (длина наименьшего цикла) не меньше к + \. Известно (см., например, [50]), что среди таких графов имеется граф, в котором число ребер по порядку не меньше п + . Каждый остовный подграф этого графа либо не содержит циклов, либо имеет обхват не меньше чем к + l. Следовательно, все эти 1+1/ подграфы принадлежат классу X. Поэтому \Хп\ 2 при некотором к 0. Из лемм 3.3 и 3.4 следует
Напомним, что подмножество множества вершин графа называется независимым множеством, если эти вершины попарно несмежны. Независимое множество наибольшей мощности в графе G называется наибольшим независимым множеством графа (далее - ННМ), а его мощность - числом независимости графа и обозначается через a{G). Задача о независимом множестве (далее - ЗНМ) состоит в нахождении в данном графе наибольшего независимого множества. Эта задача NP-трудна и остается такой для некоторых классов графов, отличных от G [16]. С другой стороны, известен ряд классов, для которых ЗНМ может быть решена за полиномиальное время. Настоящая глава содержит результаты о сложности этой задачи для наследственных классов графов.
Известно [15], что задача об отыскании ННМ по сложности полиномиально эквивалентна задаче определения числа независимости. Чаще всего мы будем иметь дело именно с этой последней и под ЗНМ будем понимать именно ее.
Полиномиальный ярус
Приведенные выше результаты дают полную классификацию конечно определенных сильно наследственных классов по сложности решения ЗНМ: если Т с X, то класс X является а-сложным, в противном случае - а-простым. Для конечно определенных классов, не являющихся сильно наследственными, картина еще очень далека от подобной завершенности. В то же время имеются положительные результаты, относящиеся к направлению поиска, подсказываемому теоремой 4.1, т.е. доказательства а -простоты некоторых классов, определяемых одним запрещенным подграфом из Т. Их изложению посвящена оставшаяся часть этой главы. В этом разделе доказывается а -простота каждого класса X, у которого Forb(X) состоит из единственного графа, принадлежащего множеству Deg(l). Как побочное следствие полученных оценок доказывается также справедливость (в слегка ослабленной форме) гипотезы, высказанной Балашем и Ю [29].
Очевидный план решения ЗНМ состоит в переборе всех максимальных независимых множеств (далее применяем сокращение МНМ). Число МНМ в графе G будем обозначать через t(G). В [62] предложен алгоритм, позволяющий найти все МНМ графа за время t{G)0{m + п). Наибольшее значение величины t(G) для графов с п вершинами равно З п [55], но для некоторых графов она может быть значительно меньше и в таких случаях перебор МНМ оказывается эффективным. В этом разделе доказывается, что для графов из наследственного класса величина t{G) растет с полиномиальной скоростью тогда и только тогда, когда среди запрещенных подграфов для этого класса имеется граф вида рК2 - Доказательство основано на полиномиальной оценке числа t(G) для графов из класса Free{pK2).
Вершину графа будем называть доминирующей, если она смежна со всеми остальными вершинами. Для вершин а и Ъ графа G обозначим через Ga подграф, получаемый удалением этих вершин и всех, смежных хотя бы с одной из них. Лемма 5.1. Если а - не доминирующая вершина графа G, то t(G) t(G - а) + (Ga ft). beN(a) Доказательство. Разобьем все МНМ графа G на две категории - к первой отнесем те, в которых содержатся МНМ графа G-а, ко второй - все остальные. Множество всех МНМ первой категории обозначим через Щ, второй - через #2. Каждое X є Н\ либо не содержит вершину а и является, следовательно, МНМ в графе G - а, либо содержит а, и тогда X - {а} есть МНМ в G - а . Обратно, любому МНМ Y графа G - а можно поставить в соответствие множество X є Ні: если в Y есть вершины, смежные с а, то полагаем X - Y, если же таких нет, то X = Yu {а}. Таким образом, имеется взаимно однозначное соответствие между Н\ и множеством всех МНМ графа G-a, поэтому t{G) = t{G-a) + \H2\.
Рассмотрим семейство Н - Каждое множество из Н2 содержит вершину а. Пусть X и {а} є Н2. Так как а не доминирующая, то X Ф 0. Множество X не является МНМ графа G-a, поэтому существует вершина Ъ, смежная с а и несмежная со всеми вершинами из X. Значит, X целиком содержится в графе Ga . Так как X является МНМ в графе G-N[a], то оно будет МНМ и в его порожденном подграфе Ga,b- Поэтому #2 Y. Ga,b)- П beN(a) Порожденный подграф, у которого каждая компонента связности состоит из двух вершин, будем называть М -подграфом. Число всех М -подграфов графа G обозначим через M(G). Если а произвольная вершина графа G, то любой М-подграф либо содержится в G-а, либо содержит ребро, инцидентное вершине а. Отсюда следует равенство M(G) = M(G-a)+ Z(M(Ga)Z,) + l). (5.1) beN(a) Теорема 5.1. Для любого графа G справедливо неравенство t(G) M(G) + 1. Доказательство. Для полного графа с п вершинами /г л »г/г ч п(п-Х) имеем t(Kn) = n, М(Кп) = -± и неравенство выполняется при любом п. Если граф не является полным, то в нем есть не доминирующая вершина а. Утверждение теоремы доказывается индукцией по числу вершин с применением леммы 5.1 и соотношения (5.1): t{G) t(G-a)+ %«Саі,) beN(a) M(G-a) + l+ (M(Ga6) + l) =M(G) + h b =N(a)
Отметим, что равенство в утверждении теоремы 5.1 достигается на графах из класса Deg(l). В графе, принадлежащем классу FreeipKj), всякий М -подграф содержит не больше чем р -1 ребро. Поэтому получаем Следствие. Если G - граф с т ребрами из класса Free(pK2), то р \пг\ t(G) Y\\. (5.2) Эта оценка позволяет полностью охарактеризовать наследственные классы, для которых перебор максимальных независимых множеств может быть выполнен за полиномиальное время. Для множества графов X обозначим tx(n) = max t(G). GeX„ i» Теорема 5.2. Для наследственного класса X функция tx(n) ограничена сверху полиномом тогда и только тогда, когда Deg(l) 2 X. Доказательство. В графе рК eDeg(l) число МНМ равно 2Р и отсюда следует, что tx(n) растет с экспоненциальной скоростью для любого класса, включающего Deg(l). Если же Deg(l) xX, то существует такое р, что рК2 X и , следовательно, X с Free{pK2). Из (5.2) следует полиномиальная оценка сверху для tx(n) Следствие. Класс Free{pK.2) при любом р является а -простым.
В заключение этого раздела приведем еще одно следствие из теоремы 5.1, касающееся гипотезы, высказанной в работе [29]. Ребро графа назовем доминирующим, если любая вершина графа смежна хотя бы с одним из концов этого ребра. Обозначим через m\{G) количество доминирующих ребер в графе G, TWQ(G) =\EG\-m\{G). В [29] доказано, что для любого графа из Free((p + 1) ), у которого дополнительный граф связен, справедливо неравенство t(G) mfi + \, и высказано предположение, что ( Лр t(G) - + 1 . (5.3) V р ) В [40] получена оценка, из которой следует, что (5.3) справедливо асимптотически, если mo = Q(n ). Ниже это предположение будет доказано в следующей слегка ослабленной форме. Теорема 5.3. Для любого графа G є Free((p + l)Kj) справедливо неравенство t(G) щ + 1 V р ) + Ш\. Предварительно получим еще одну оценку для числа всех (не только максимальных) независимых множеств графа. Это число будем обозначать через s(G), при этом для удобства полагаем, что пустое множество является независимым множеством любого графа.
Сильно наследственные а-простые классы
Всякий граф может быть задан матрицей смежности, причем для обыкновенного графа достаточно указать только элементы матрицы, расположенные выше главной диагонали. Выписывая эти элементы в одну строчку (сначала элементы первой строки, затем второй и т.д.), получим двоичное слово длины уіп(п-ї), которое будем называть каноническим кодом графа. Канонический код графа G будем обозначать через c(G). При отсутствии априорной информации о графе канонический код является неизбыточным, если же мы имеем дело с графами из некоторого класса X, то, вообще говоря, они могут быть закодированы словами меньшей длины. Из результатов главы 1 следует, что в том случае, когда X -наследственный класс с ненулевой энтропией, самый экономный равномерный двоичный код для графов из X имеет длину слова, асимптотически равную п h{X) 12. Таким образом, h{X) - предельное значение «коэффициента сжатия», т.е. отношения длины кода, построенного с учетом принадлежности графа к классу X, к длине канонического кода. При этом, так как h(X) 1 для любого наследственного класса, отличного от класса всех графов, то любой такой класс допускает кодирование, более экономное, чем каноническое. Возникает вопрос о том, какой ценой может быть достигнуто такое сжатие информации, какова может быть трудоемкость кодирования и декодирования. В этой главе рассматривается метод кодирования графов, который дает асимптотически оптимальные коды для любого наследственного класса с ненулевой энтропией и допускает эффективную реализацию. В частности, декодирование, т.е. вычисление одного элемента матрицы смежности по коду графа требует выполнения лишь постоянного, не зависящего от числа вершин п количества арифметических операций над числами, не превышающими
Описываемое ниже кодирование является отображением множества всех обыкновенных графов в множество слов в алфавите {0,1}. Исходными данными для построения кода графа служат число его вершин и матрица смежности. Никакая другая информация, в том числе о принадлежности графа тому или иному специальному классу, не используется, в то же время это кодирование оказывается асимптотически оптимальным для любого наследственного класса с ненулевой энтропией. В этом состоит универсальность кодирования - эффект, хорошо известный для вероятностных моделей классической теории кодирования. Пусть л 16, GEGH, М-\\ЩА\ - матрица смежности графа G. Пусть р - наибольшее простое число, заключенное в интервале n/sjlogn +1, 2 n/ logn (такое всегда существует по теореме Чебышева - см., например, [23]), к - \_n/pj . Разобьем множество [1,пу- на две части: первая из них, обозначаемая Щ, состоит из всех таких пар {a,b), что a кр, Ъ кр, _(а - l)/pj \_(Ь - 1)/р], все остальные пары составляют вторую часть, 7?2- Рассмотрим подграфы Ff = G([pi +1, p(i + 1)]), 0 і к -1, и образуем слова a = c(F0)c(Fl)...c(Fk_l), P{J) = mj,kp+\mj,kp+2---mj,n, 0 j kp, y = c(G([kp + l,n])) Слово /г полностью определяет (при известном п) отношение смежности для всех пар вершин, входящих в /?2 С частью R\ поступим следующим образом. Для любой пары 2 (х,у) е[0,р- 1] определим множество Qx,y = {a - а є[1,кр], x\{a-\)lp\ + y = a-\ (mod p)). 105 Каждая пара из R\ встречается точно в одном из множеств Qx,y В самом деле, если (a,b)eRi и і \_(а-\)/р\, І = [_( - \)Ір\, то ІФ j (по определению R\), поэтому система xi + у = а -1 (mod р), xj + у = Ь -1 (mod р) имеет единственное решение, определяемое сравнениями \x(i-j) = a-b (mod/?), Хг-У") = ( -! "-(«-1)7 (mod/?). Таким образом, для полного описания графа G достаточно, кроме /г , задать все подграфы вида Gx v = Сдбл Перенумеровав в каждом из них вершины в соответствии с отображением z - \_(z- \)/р] + \, получим р графов Gx„, принадлежащих множеству G . Среди этих графов могут быть одинаковые. Допустим, что множество \G Xу: (х,у) е[0,р-1] состоит из т элементов, занумеруем его элементы некоторым (произвольным) образом числами от 0 до т-\. Пусть Щ обозначает граф, получивший при этом номер /. Обозначим через со(х,у) двоичную запись длины / = ["logт\ такого числа г, что G Xy, = Щ и образуем слова
Похожие диссертации на Исследование количественных и сложностных характеристик наследственных классов графов
