Содержание
1. Предварительные сведения 12
1.1. Некоторые сведения о порождающих множествах в группах подстановок 12
1.2. Некоторые свойства графов, степени вершин которых ограничены .... 14
1.3. Некоторые свойства цветных графов с ограниченной кратностью цветов 16
1.4. Некоторые свойства древесных разложений но расстоянию.............. 19
2. Изоморфизмы графов и двухсвязные компоненты графов 22
2.1. Изоморфизмы деревьев Хусими........................................ 23
2.1.1. Вспомогательные алгоритмы................................... 23
2.1.2. Алгоритм распознавания изоморфизма деревьев Хусими .... 25
2.2. Изоморфизмы почти деревьев......................................... 29
2.2.1. Изоморфизмы цветных графов с ограниченными степенями вершин 29
2.2.2. Изоморфизмы графов, блоки которых являются графами с ограниченными степенями вершин 32
.2.2.3. Изоморфизмы почти деревьев с параметром к.................. 35
2.3. Изоморфизмы графов, блоки которых
являются графами из класса ВС к.................................... 36
3. £>г$£-разложения и изоморфизмы графов 41
3.1. Алгоритм распознавания изоморфизма для класса графов ТО .......... 42
3.2. Алгоритм распознавания изоморфизма для класса графов Т>0л......... 49
4. Изоморфизмы цветных графов 63
4.1. Цветные двухкомпонентные графы..................................... 63
4.2. Алгоритм распознавания изоморфизма для класса цветных графов ТВСк 67
4.3. Алгоритм распознавания изоморфизма для класса цветных графов ТВС1к 71
5. Изоморфизмы графов с простым спектром и цепные разложения по расстоянию 79
5.1. Некоторые факты и обозначения ..................................... 79
5.2. Изоморфизмы графов из класса 5рсс 1................................ 80
5.3. Изоморфизмы графов в классе РаИгвре^............................... 88
Введение
Данная диссертация посвящена изучению проблемы изоморфизма графов. Здесь и далее под графами мы понимаем конечные неориентированные графы без петель и кратных ребер. Для графов мы будем пользоваться системой обозначений из книги |1]. Множество вершин графа С будем обозначать через УС или И(С?), а множество ребер - через ЕС или £■((?). Обычно через п будем обозначать количество вершин (или порядок) графа, если не оговорено противное, а через тп - число его ребер. Проблема изоморфизма графов состоит в следующем: существует ли полиномиальный алгоритм, который для каждой пары графов распознает изоморфны они или нет.
На данный момент неизвестно никакого полиномиального алгоритма распознавания изоморфизма произвольных графов. Бач ее того, неизвестно - существует ли такой алгоритм вообще. В диссертации рассматривается проблематика, связанная с построением полиномиальных алгоритмов распознавания изоморфизма для некоторых классов графов. Вопросы, имеющие отношение к проблеме существования полиномиального алгоритма распознавания изоморфизма произвольных графов, в диссертации не рассматриваются. Однако, хотелось бы коротко рассказать, какое место занимает задача распознавания изоморфизма графов в иерархии теории сложности.
Доказано, что задача распознавания изоморфизма графов лежит в классе NP, но неизвестно является ли она МР-полной. Установлено, что задача распознавания изоморфизма двух графов полиномиально эквивалентна задаче поиска числа изоморфизмов между двумя графами [18]. Так как задачи распознавания и перечисления для всех известных Л^Р-полных задач не являются полиномиально эквивалентными, существует гипотеза, что задача распознавания изоморфизма графов не является ЛгР-полной (5|, 117].
В силу этого возможно, что при Р ф NP, задача распознавания изоморфизма графов и все задачи, полиномиально эквивалентные ей, образуют отдельный класс гак называемых изоморфно полных задач. Примеры таких задач можно найти, в частности, в (18] и |19|.
Вернемся к обсуждению алгоритмических аспектов задачи распознавания изоморфизма графов.
Из известных алгоритмов распознавания изоморфизма для класса всех графов наименьшую временную сложность имеет алгоритм Земляченко [5]. Бабаи и Лаксом было
показано, что временная сложность этого алгоритма 0(еп*+0(1)) [19], где п - количество вершин графов.
Поскольку, как уже говорилось выше, построить полиномиальный алгоритм распознавания изоморфизма дчя класса всех графов не удается, исследования в этой области разделяются на два направления:
1) построение так называемых эористгпеских алгоритмов распознавания изомор-физма графов;
2) построение полиномиальных алгоритмов распознавания изоморфизма для отдельных классов графов.
Результаты, представленные в диссертации имеют отношение ко второму направлению, по хотелось бы коротко рассказать об основных фактах, касающихся эвристических алгоритмов распознавания изоморфизма графов. Эти алгоритмы основаны на довольно естественной идее расклассифицировать вершины графов таким образом, чтобы избежать полного перебора. Иными словами, если С?1 и С2 - графы, между которыми проверяется наличие изоморфизма, то мы разбиваем мно>ж*ства вершин графов С\ и
<72 на классы, приписывая вершинам метки или, иными словами, цвета так, что изоморфизм может отображать вершину и графа С1 в вершину V графа (72 только если и и V имеют одинаковый цвет. Для этого используются некоторые свойства вершин графов, инвариантные относительно изоморфизма. В качестве простейшего примера можно привести классификацию вершин по их степеням. Алгоритмы, основанные на идее разбиения множества вершин на классы, можно найти, например, в (15), (16|, (20), [21). Необходимо отметить, что хотя в большинстве случаев они и многие подобные им алгоритмы, как правило, достаточно эффективны, время работы в худшем случае у них экспоненциально. Попутно заметим, что алгоритм в статье [20] являлся базовым при написании ее автором программы Ь'аиЬу, которая для пары произвольных графов проверяет являются ли они изоморфными. Многие исследователи (см., в частности, [17]) полагают, что №ау1у является на данное время наиболее эффективным по быстродействию программным средством распознавания изоморфизма произвольных графов.
В связи с этим представляет интерес задача распознавания изоморфизма цветных графов. Следующее понятие понадобится нам в дальнейшем при изложении результатов диссертации.
Определение. Цветным графом называется пара (О,/), где С - обыкновенный граф, а / - функция из множества вершин графа <7 в некоторый начальный отрезок натурального ряда {1 . Для вершины у графа (7 число /(у) называется цветом
вершины у. Число вершин цвета I называется кратностью цвета г.
Цветной граф ((?,/) будем обозначать также через (7/. Множество вершин цвета г в цветном графе <7/ будем обозначать через С, и называть его г-м цветным классом, а множество всех цветных классов <7ь...,С* обозначим через С и будем называть его разбиение.«* на цветные классы множества вершин цветного графа <7/.
Понятно, что цвета в цветном графе (С,/) можно задавать не только с помощью цветной функции /. Очень часто мы будем брать граф <7, а потом указывать разбиение С = {Сь..., <7(} множества его вершин на цветные классы.
Два цветных графа изоморфны, если для них имеется изоморфизм, сохраняющий цвета вершин. Такой изоморфизм мы будем называть цветным изоморфизмом. В дальнейшем под изоморфизмами цветных графов мы всегда будем понимать их цветные изоморфизмы.
Известно, что задача распознавания изоморфизма в классе всех цветных графов полиномиально эквивалентна задаче распознавания изоморфизма графов [18], иными словами она изоморфно полна.
Прежде чем перейти к изложениию результатов диссертации, укажем основные классы графов, для которых различными авторами построены полиномиальные алгоритмы распознавания изоморфизма, и введем обозначения для некоторых из них.
К таким классам графов относятся корневые деревья [2], деревья [3], связные графы, степени вершин которых ограничены натуральной константой [18), графы интервалов [14), графы ограниченной древесной ширины [13), планарные графы [7), графы, род которых ограничен натуральной констаной [18), графы с ограниченной древесной шириной по расстоянию [12), цветные графы, кратность каждого цвета в которых ограничена некоторой константой [18|, и графы, у которых кратности собственных чисел ограничены некоторой константой [10].
Хотя алгоритмы в приведенном списке решают частные случаи одной и той же задачи, приемы, которые в них используются, очень сильно различаются. Часть из них использует не только комбинаторные методы, такие как поиск в графе, различные
сортировки ит. п., но также методы теории групп подстановок и некоторые матричные алгоритмы.
Пусть d - некоторая натуральная константа. Обозначим через Qd класс связных графов, степени вершин которых не превосходят d. Алгоритм распознавания изоморфизма графов в классе Qd} доказательство корректности его работы, оценку его временной сложности и доказательство того, что она (оценка) справедлива, можно, как уже указывалось выше, найти в монографии [18). Эту оценку сложности алгоритма распознавания изоморфизма для класса графов Qd мы приводить не будем, поскольку она является довольно сложной функцией. Заметим только, что она примерно составляет 0(nd')(19). В работах |17) и (18) говорится, что Лаке утверждает о возможности существенного уменьшения этой оценки. Необходимо отметить, что для класса графов был построен полиномиальный алгоритм распознавания изоморфизма сложности 0(п4) (18). Этот алгоритм использует по сути дела такие же методы, как и более общий алгоритм. Подробнее об алгоритме Бабаи-Лакса распознавания изоморфизма для класса графов Qd мы расскажем в параграфе 1.2.
Введем обозначение ВСк для класса всех цветных графов, цветная кратность которых не превосходит натурального числа к, т. е. для каждого цветного класса Сі графа G Є ВСк имеем |Cj| < к. Бабаи разработал полиномиальный алгоритм распознавания изоморфизма для класса цветных графов ВСк [18). Временная сложность алгоритма Бабаи 0(п6 • (2/с)!6 • (n-f (2к)2)). Схема работы этого алгоритма приведена в параграфе
1.3.
Введем обозначение еще для одного класса графов, для которого построен полиномиальный алгоритм распознавания изоморфизма. Пусть дан обыкновенный п-вершинный граф G, и пусть A(G) - матрица смежности графа G. Спектром графа G называют набор собственных значений Аі, Аг,..., А* его матрицы смежности A(G). Вообще говоря, числа А,, где і = 1,..., п, не обязательно попарно различны. Заметим, что числа А*, где і = 1,...,п, называют собствеютми значениями графа G. Кратностью собственного значения А*, где г = 1,..., л, называется число его вхождений в набор Аь \2,..., А„ или, что то же самое, кратность корня А і в характеристическом многочлене матрицы A(G).
Далее для каждого к 6 N через Speck будем обозначать класс графов, в которых кратность каждого собственного значения не превосходит к. Для любого натурального числа к существует полиномиальный алгоритм распознавания изоморфизма для класса графов Speck |10). Заметим, что сложность этого алгоритма 0(плк+с), где с-некоторая положительная константа.
Необходимо отметить, что для класса графов Spec і существует алгоритм распознавания изоморфизма с временной сложностью 0(п3). Этот алгоритм в отличие от алгоритма распознавания изоморфизма для класса Speck, где к > I, не использует теоретико-групповой подход. Схема работы алгоритма распознавания изоморфизма графов для класса Specx приводится в параграфе 5.2.
Перейдем теперь к обсуждению задач, рассматриваемых в диссертации.
В частности, в диссертации рассматриваются разложения графов на двухсвязные компоненты (блоки). Формализацией такого разложения является граф блоков и точек сочленения.
Определение. Пусть G - связный граф с множеством блоков {Вь..., В,} и множеством точек сочленения {сі,...,сі}. Граф bc(G)} вершинами которого являются элементы из {2?ь ..., В3, Сі..., Сі} и две вершины котрого смежны, если одна соответствует блоку Ві, а другая точке сочленения с,, причем Cj Є В», называется графом блоков и
точек сочленения графа G .
Негрудно показать, что граф блоков и точек сочленения любого графа G является деревом и что вершинами степени 1 могут быть только вершины, которые соответствуют блокам графа G. Граф блоков и точек сочленения будем в дальнейшем называть деревом блоков и точек сочленения.
Пусть К. - произвольный класс графов, для которою известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, a S - некоторый тин "древовидных" разложений графов на компоненты. В данной работе мы будем рассматривать следующие типы "древовидных" разложений графа: представление графа в виде дерева блоков и точек сочленения (см. выше); древесные разложения графов по расстоянию (12); минимальные древесные разложения графов по расстоянию (12); цепные разложения графов по расстоянию (12) и т. п.
Будем говорить, что граф G принадлежит классу TSfC, если он обладает разложением типа S на компоненты, принадлежащие классу К,, а соответствующее дерево компонент принадлежит классу Т. Если класс Т совпадает с классом всех деревьев, то в этом случае класс графов TSfC будем обозначать просто через SfC.
Диссертация посвящена рассмотрению следующих двух проблем.
Проблема А. Пусть К. - произвольный класс графов, для которого известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, a S - некоторый тип "древовидных"разложений графов на компоненты. Существует ли полиномиальный алгоритм распознавания изоморфизма для класса графов TSfC?
Проблема В. Пусть К. - произвольный класс цветных графов, для которого известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, a S - некоторый тип "древовидных"разложений гімфов на компоненты. Существует ли полиномиальный алгоритм распознавания изоморфизма для класса цветных графов ТSfC ?
Отметим, что проблема А фактически уже рассматривалась в работе Бодлсндера (13) для случая, когда в качестве Т фигурирует класс всех деревьев, в качестве S -древесные разложения графов, а в качестве К. - класс всех графов, число вершин в которых ограничено некоторой натуральной константой.
Пусть G - некоторый граф, а и и v - его вершины. Длина кратчайшего маршрута из вершины и в вершину v обозначается через dc{u,v) и называется расстоянием между вершинами и и и.
Определение. Пусть G = (V, Е) - связный граф. Древесным разложением графа G по расстоянию называется тройка ({X, : і € /}, Т = (/, F), г) такая, что
!) U Xi = V иХіП Xj = 0 для любых г ф j, где i,j Є /;
•є/
2) Т является корневым деревом с корнем в вершине г Є /;
3) для каждого v Є V если v Є Хі, то dG{Xr, и) = dr(r,i),
4) для каждого ребра {и,го} Є Е существуют такие i,j € I, что v є Xit w Є Xj и либо і =i j, либо {i,j} € F.
Если дерево Т = (I, F) является простой цепью, то такое древесное разложение связного графа по расстоянию будем называть цепным разложением графа по расстоянию.
Если множество Хг является одноэлементным, т. е. Хг = {н}, где и - некоторая вершина графа, то такое древесное разложение по расстоянию будем называть древесным разложением по расстоянию с выделенным корнем.
Поскольку древесное разложение по расстоянию определяется только для связных
6
графов, говоря, что граф (7 обладает древесным разложением по расстоянию, мы подразумеваем, что Б - связный граф.
Множества где г £ I, называются компонентами древесного разложения по расстоянию. Множество ХТ мы будем называть корневым множеством или корнем древесного разложения по расстоянию.
Будем говорить, что компонента Ху является сыном компоненты Ху, если в корневом дереве Т вершина I является сыном вершины
Определение. Пусть Б = ({Л* : г £ /},Т = - древесное разложение
графа б? по расстоянию. Для каждой компоненты древесного разложения Ху определим множество У(Б, Х{) = и Ху, где Тг - максимальное корневое поддерево дерева Т с
>€У(7-)
корнем в вершине г.
Определен ие. Пусть Б — ({Я* : г 6 /},Т = (/, Б), г) - древесное разложение графа С по расстоянию. Б называется минимальным, если для каждого I £ I порожденный подграф С(К(Д Я*)) графа Б является связным.
Шириной древесного разложения по расстоянию называется количество вершин в максимальной по мощности компоненте. Древесной шириной графа по расстоянию называется наименьшая ширина древесных разложений по расстоянию.
Введем следующие обозначения для типов "древовидных" разложений, которые мы будем рассматривать в диссертации:
1) «51 - разложение графов на блоки и точки сочленения;
2) &2 ~ цепные разложения графов по расстоянию, корневые множества которых одноэлементны (заметим, что в этом случае естественно считать, что соответствующий класс Т совпадает с классом цепей);
3) 53 - минимальные древесные разложения графов по расстоянию, корневые множества которых одноэлементны.
В диссертации изучаются случаи, когда на компоненты "древовидных" разложений накладываются условия вида:
1) каждая компонента порождает подграф, который принадлежит классу графов Ол, где с1 - некоторая натуральная константа (глава 3);
2) каждая компонента порождает подграф, который принадлежит классу графов ВСк, где к - некоторая натуральная константа (глава 4);
3) каждая компонента порождает подграф, который принадлежит классу графов 5рес1 (глава 5).
То, что нами рассматриваются только классы графов, алгоритмы распознавания изоморфизма которых были получены теоретико-групповыми методами, не случайно. В частности, это обосновывается следующим. Пусть К, - класс графов, в котором задача распознавания изоморфизма решается за полиномиальное время чисто комбинаторными методами. С помощью небольшой модернизации соответствующего алгоритма обычно удается решить за полиномиальное время и задачу распознавания изоморфизма в классе Т«5г£ даже в случае, когда класс Т совпадает с классом всех деревьев. Кроме того, отметим, что для некоторых классов К. имеет место равенство К = 8ХК (например, если К - класс планарных графов).
Для разложений типов «5г и «53 в случае, если К, - класс графов, в котором задача распознавания изоморфизма решается за полиномиальное время чисто комбинаторными методами, ситуация не столь проста и скорее всего тоже требует применения теоретико-групповых методов.
7
- Київ+380960830922