Содержание к диссертации
Введение
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. Алгоритм распознавания изоморфизма для класса графов VQd 42
3.2. Алгоритм распознавания изоморфизма для класса графов T>Qkd 49
4. Изоморфизмы цветных графов 63
4.1. Цветные двухкомпонентные графы 63
4.2. Алгоритм распознавания изоморфизма для класса цветных графов VBCk 67
4.3. Алгоритм распознавания изоморфизма для класса цветных графов ТВС{ 71
5. Изоморфизмы графов с простым спектром и цепные разложения по расстоянию 79
5.1. Некоторые факты и обозначения 79
5.2. Изоморфизмы графов из класса Speci 80
5.3. Изоморфизмы графов в классе PathSpeci 88
- Некоторые свойства графов, степени вершин которых ограничены
- Некоторые свойства древесных разложений по расстоянию
- Алгоритм распознавания изоморфизма деревьев Хусими
- Изоморфизмы графов, блоки которых являются графами с ограниченными степенями вершин
Введение к работе
Данная диссертация посвящена изучению проблемы изоморфизма графов. Здесь и далее под графами мы понимаем конечные неориентированные графы без петель и кратных ребер. Для графов мы будем пользоваться системой обозначений из книги [1]. Множество вершин графа G будем обозначать через VG или V(G), а множество ребер - через EG или E(G). Обычно через п будем обозначать количество вершин (или порядок) графа, если не оговорено противное, а через т - число его ребер. Проблема изоморфизма графов состоит в следующем: существует ли полиномиальный алгоритм, который для каждой пары графов распознает изоморфны они или нет.
На данный момент неизвестно никакого полиномиального алгоритма распознавания изоморфизма произвольных графов. Более того, неизвестно - существует ли такой алгоритм вообще. В диссертации рассматривается проблематика, связанная с построением полиномиальных алгоритмов распознавания изоморфизма для некоторых классов графов. Вопросы, имеющие отношение к проблеме существования полиномиального алгоритма распознавания изоморфизма произвольных графов, в диссертации не рассматриваются. Однако, хотелось бы коротко рассказать, какое место занимает задача распознавания изоморфизма графов в иерархии теории сложности.
Доказано, что задача распознавания изоморфизма графов лежит в классе NP, но неизвестно является ли она iVP-полной. Установлено, что задача распознавания изоморфизма двух графов полиномиально эквивалентна задаче поиска числа изоморфизмов между двумя графами [18]. Так как задачи распознавания и перечисления для всех известных ІУР-полньїх задач не являются полиномиально эквивалентными, существует гипотеза, что задача распознавания изоморфизма графов не является iVP-полной [5], [17].
В силу этого возможно, что при Р ф NP, задача распознавания изоморфизма графов и все задачи, полиномиально эквивалентные ей, образуют отдельный класс так называемых изоморфно полных задач. Примеры таких задач можно найти, в частности, в [18] и [19].
Вернемся к обсуждению алгоритмических аспектов задачи распознавания изоморфизма графов.
Из известных алгоритмов распознавания изоморфизма для класса всех графов наименьшую временную сложность имеет алгоритм Земляченко [5]. Бабаи и Лаксом было
показано, что временная сложность этого алгоритма 0(еп +^) [19], где п - количество вершин графов.
Поскольку, как уже говорилось выше, построить полиномиальный алгоритм распознавания изоморфизма для класса всех графов не удается, исследования в этой области разделяются на два направления:
построение так называемых эвристических алгоритмов распознавания изоморфизма графов;
построение полиномиальных алгоритмов распознавания изоморфизма для отдельных классов графов.
Результаты, представленные в диссертации имеют отношение ко второму направлению, но хотелось бы коротко рассказать об основных фактах, касающихся эвристических алгоритмов распознавания изоморфизма графов. Эти алгоритмы основаны на довольно естественной идее расклассифицировать вершины графов таким образом, чтобы избежать полного перебора. Иными словами, если Gi и Gi - графы, между которыми проверяется наличие изоморфизма, то мы разбиваем множества вершин графов G\ и
G2 на классы, приписывая вершинам метки или, иными словами, цвета так, что изоморфизм может отображать вершину и графа Gx в вершину v графа (?2 только если и и v имеют одинаковый цвет. Для этого используются некоторые свойства вершин графов, инвариантные относительно изоморфизма. В качестве простейшего примера можно привести классификацию вершин по их степеням. Алгоритмы, основанные на идее разбиения множества вершин на классы, можно найти, например, в [15], [16], [20], [21]. Необходимо отметить, что хотя в большинстве случаев они и многие подобные им алгоритмы, как правило, достаточно эффективны, время работы в худшем случае у них экспоненциально. Попутно заметим, что алгоритм в статье [20] являлся базовым при написании ее автором программы Nauty, которая для пары произвольных графов проверяет являются ли они изоморфными. Многие исследователи (см., в частности, [17]) полагают, что Nauty является на данное время наиболее эффективным по быстродействию программным средством распознавания изоморфизма произвольных графов.
В связи с этим представляет интерес задача распознавания изоморфизма цветных графов. Следующее понятие понадобится нам в дальнейшем при изложении результатов диссертации.
Определение. Цветным графом называется пара (G,/), где G - обыкновенный граф, а / - функция из множества вершин графа G в некоторый начальный отрезок натурального ряда {1,..., t}. Для вершины v графа G число f(v) называется цветом вершины v. Число вершин цвета г называется кратностью цвета г.
Цветной граф (G, /) будем обозначать также через G/. Множество вершин цвета г в цветном графе (7/ будем обозначать через Q и называть его г-м цветным классом, а множество всех цветных классов Сх,..., Ск обозначим через С и будем называть его разбиением на цветные классы множества вершин цветного графа Gf.
Понятно, что цвета в цветном графе (G, /) можно задавать не только с помощью цветной функции /. Очень часто мы будем брать граф G, а потом указывать разбиение С = {Ci,..., Ct} множества его вершин на цветные классы.
Два цветных графа изоморфны, если для них имеется изоморфизм, сохраняющий цвета вершин. Такой изоморфизм мы будем называть цветным изоморфизмом. В дальнейшем под изоморфизмами цветных графов мы всегда будем понимать их цветные изоморфизмы.
Известно, что задача распознавания изоморфизма в классе всех цветных графов полиномиально эквивалентна задаче распознавания изоморфизма графов [18], иными словами она изоморфно полна.
Прежде чем перейти к изложениию результатов диссертации, укажем основные классы графов, для которых различными авторами построены полиномиальные алгоритмы распознавания изоморфизма, и введем обозначения для некоторых из них.
К таким классам графов относятся корневые деревья [2], деревья [3], связные графы, степени вершин которых ограничены натуральной константой [18], графы интервалов [14], графы ограниченной древесной ширины [13], планарные графы [7], графы, род которых ограничен натуральной констаной [18], графы с ограниченной древесной шириной по расстоянию [12], цветные графы, кратность каждого цвета в которых ограничена некоторой константой [18], и графы, у которых кратности собственных чисел ограничены некоторой константой [10].
Хотя алгоритмы в приведенном списке решают частные случаи одной и той же задачи, приемы, которые в них используются, очень сильно различаются. Часть из них использует не только комбинаторные методы, такие как поиск в графе, различные
сортировки и т. п., но также методы теории групп подстановок и некоторые матричные алгоритмы.
Пусть d - некоторая натуральная константа. Обозначим через Qa класс связных графов, степени вершин которых не превосходят d. Алгоритм распознавания изоморфизма графов в классе Q&, доказательство корректности его работы, оценку его временной сложности и доказательство того, что она (оценка) справедлива, можно, как уже указывалось выше, найти в монографии [18]. Эту оценку сложности алгоритма распознавания изоморфизма для класса графов Qa мы приводить не будем, поскольку она является довольно сложной функцией. Заметим только, что она примерно составляет 0(nd!)[19]. В работах [17] и [18] говорится, что Лаке утверждает о возможности существенного уменьшения этой оценки. Необходимо отметить, что для класса графов С?3 был построен полиномиальный алгоритм распознавания изоморфизма сложности 0(пА) [18]. Этот алгоритм использует по сути дела такие же методы, как и более общий алгоритм. Подробнее об алгоритме Бабаи-Лакса распознавания изоморфизма для класса графов Q& мы расскажем в параграфе 1.2.
Введем обозначение ВС^ для класса всех цветных графов, цветная кратность которых не превосходит натурального числа к, т. е. для каждого цветного класса Сі графа G Є ВСк имеем |Cj| < к. Бабаи разработал полиномиальный алгоритм распознавания изоморфизма для класса цветных графов ВСь [18]. Временная сложность алгоритма Бабаи 0(п6 (2к)\6 (п + (2А;)2)). Схема работы этого алгоритма приведена в параграфе 1.3.
Введем обозначение еще для одного класса графов, для которого построен полиномиальный алгоритм распознавания изоморфизма. Пусть дан обыкновенный п-вершинный граф G, и пусть A(G) - матрица смежности графа G. Спектром графа G называют набор собственных значений Ль А2,..., Хп его матрицы смежности A(G). Вообще говоря, числа Aj, где г = 1,..., п, не обязательно попарно различны. Заметим, что числа Aj, где г — 1,...,п, называют собственными значениями графа G. Кратностью собственного значения Aj, где г = 1,..., п, называется число его вхождений в набор Ai, А2,..., Ап или, что то же самое, кратность корня Aj в характеристическом многочлене матрицы A{G).
Далее для каждого к Є N через Specf. будем обозначать класс графов, в которых кратность каждого собственного значения не превосходит к. Для любого натурального числа к существует полиномиальный алгоритм распознавания изоморфизма для класса графов Speck [10]. Заметим, что сложность этого алгоритма 0(п4к+с), где с-некоторая положительная константа.
Необходимо отметить, что для класса графов Spec\ существует алгоритм распознавания изоморфизма с временной сложностью 0(п3). Этот алгоритм в отличие от алгоритма распознавания изоморфизма для класса Speck, где к > 1, не использует теоретико-групповой подход. Схема работы алгоритма распознавания изоморфизма графов для класса Specx приводится в параграфе 5.2.
Перейдем теперь к обсуждению задач, рассматриваемых в диссертации.
В частности, в диссертации рассматриваются разложения графов на двухсвязные компоненты (блоки). Формализацией такого разложения является граф блоков и точек сочленения.
Определение. Пусть G - связный граф с множеством блоков {В\,..., Bs} и множеством точек сочленения {с\,..., сі}. Граф bc(G), вершинами которого являются элементы из {Bi,..., Bs, сі..., q} и две вершины которого смежны, если одна соответствует блоку Bi, а другая точке сочленения с,, причем Cj Є Bi, называется графом блоков и
точек сочленения графа G .
Нетрудно показать, что граф блоков и точек сочленения любого графа G является деревом и что вершинами степени 1 могут быть только вершины, которые соответствуют блокам графа G. Граф блоков и точек сочленения будем в дальнейшем называть деревом блоков и точек сочленения.
Пусть К - произвольный класс графов, для которого известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, a S - некоторый тип "древовидных" разложений графов на компоненты. В данной работе мы будем рассматривать следующие типы "древовидных" разложений графа: представление графа в виде дерева блоков и точек сочленения (см. выше); древесные разложения графов по расстоянию [12]; минимальные древесные разложения графов по расстоянию [12]; цепные разложения графов по расстоянию [12] и т. п.
Будем говорить, что граф G принадлежит классу TSK, если он обладает разложением типа S на компоненты, принадлежащие классу /С, а соответствующее дерево компонент принадлежит классу Т. Если класс Т совпадает с классом всех деревьев, то в этом случае класс графов TSK будем обозначать просто через SK.
Диссертация посвящена рассмотрению следующих двух проблем.
Проблема А. Пусть К - произвольный класс графов, для которого известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, a S - некоторый тип "древовидных" разложений графов на компоненты. Существует ли полиномиальный алгоритм распознавания изоморфизма для класса графов TSK ?
Проблема В. Пусть К - произвольный класс цветных графов, для которого известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, a S - некоторый тип "древовидных"разложений графов на компоненты. Существует ли полиномиальный алгоритм распознавания изоморфизма для класса цветных графов TSK ?
Отметим, что проблема А фактически уже рассматривалась в работе Бодлендера [13] для случая, когда в качестве Т фигурирует класс всех деревьев, в качестве S -древесные разложения графов, а в качестве К - класс всех графов, число вершин в которых ограничено некоторой натуральной константой.
Пусть G - некоторый граф, а и и v - его вершины. Длина кратчайшего маршрута из вершины и в вершину v обозначается через da{u,v) и называется расстоянием между вершинами и и v.
Определение. Пусть G = (V, Е) - связный граф. Древесным разложением графа G по расстоянию называется тройка ({Xt : і Є 1},Т = (I,F), г) такая, что
1) (J Хі — V и Х{ Г) Xj — 0 для любых г ф j, где г, j Є /;
ге/
Т является корневым деревом с корнем в вершине г Є Г,
для каждого v Є V если v Є Хі, to dc(Xr,v) = сіт(г,і),
для каждого ребра {v,w} Є Е существуют такие i,j Є I, что v Є Хі, w Є Xj и либо і =і j, либо {г, j} Є F.
Если дерево Т = (/, F) является простой цепью, то такое древесное разложение связного графа по расстоянию будем называть цепным разложением графа по расстоянию.
Если множество ХТ является одноэлементным, т. е. Хг = {и}, где и - некоторая вершина графа, то такое древесное разложение по расстоянию будем называть древесным разложением по расстоянию с выделенным корнем.
Поскольку древесное разложение по расстоянию определяется только для связных
графов, говоря, что граф G обладает древесным разложением по расстоянию, мы подразумеваем, что G - связный граф.
Множества Хі, где г I, называются компонентами древесного разложения по расстоянию. Множество ХТ мы будем называть корневым множеством или корнем древесного разложения по расстоянию.
Будем говорить, что компонента Хі является сыном компоненты Xj, если в корневом дереве Т вершина г является сыном вершины j.
Определение. Пусть D = ({Хі : г 6 1},Т = (I,F),r) - древесное разложение графа G по расстоянию. Для каждой компоненты древесного разложения Хі определим
множество V(D, Хі) = [J Xj, где Ті - максимальное корневое поддерево дерева Т с
jev(Ti) корнем в вершине І.
Определение. Пусть D — ({Хі : і Є 1},Т — (I,F),r) - древесное разложение графа G по расстоянию. D называется минимальным, если для каждого і Є I порожденный подграф G(V(D,Xi)) графа G является связным.
Шириной древесного разложения по расстоянию называется количество вершин в максимальной по мощности компоненте. Древесной шириной графа по расстоянию называется наименьшая ширина древесных разложений по расстоянию.
Введем следующие обозначения для типов "древовидных" разложений, которые мы будем рассматривать в диссертации:
с?з - минимальные древесные разложения графов по расстоянию, корневые множества которых одноэлементны.
В диссертации изучаются случаи, когда на компоненты "древовидных" разложений накладываются условия вида:
каждая компонента порождает подграф, который принадлежит классу графов Qd, где d - некоторая натуральная константа (глава 3);
каждая компонента порождает подграф, который принадлежит классу графов ВС к, где к - некоторая натуральная константа (глава 4);
каждая компонента порождает подграф, который принадлежит классу графов Spec\ (глава 5).
То, что нами рассматриваются только классы графов, алгоритмы распознавания изоморфизма которых были получены теоретико-групповыми методами, не случайно. В частности, это обосновывается следующим. Пусть 1С - класс графов, в котором задача распознавания изоморфизма решается за полиномиальное время чисто комбинаторными методами. С помощью небольшой модернизации соответствующего алгоритма обычно удается решить за полиномиальное время и задачу распознавания изоморфизма в классе TSyK, даже в случае, когда класс Т совпадает с классом всех деревьев. Кроме того, отметим, что для некоторых классов /С имеет место равенство /С = S\K (например, если К - класс планарных графов).
Для разложений типов 5г и <% в случае, если /С - класс графов, в котором задача распознавания изоморфизма решается за полиномиальное время чисто комбинаторными методами, ситуация не столь проста и скорее всего тоже требует применения теоретико-групповых методов.
По поводу разложений типов 52 и 5з необходимо заметить следующее. Они и аналогичные им разложения, как уже было отмечено, рассматривались в работе [12]. Там были построены алгоритмы распознавания изоморфизма для класса графов, древесная ширина по расстоянию которых не превосходит некоторой наперед заданной константы к (или в наших обозначениях для класса S^JC, где К совпадает с классом графов, количество вершин в которых не более А;). Заметим, что при этом, вообще говоря, не требовалось, чтобы корневое множество было одноэлементно. Достаточно было, чтобы оно принадлежало этому классу /С.
Более точно, пусть к - некоторое натуральное число. Если графы обладают древесными разложениями по расстоянию, в которых каждая компонента по мощности не превосходит А; (этот класс графов будем обозначать через TVWk), то существует полиномиальный алгоритм распознавания их изоморфизма с временной сложностью 0((A;!)2A;2nfe+2), где п - количество вершин в графах [12]. В случае же если графы обладают цепными разложениями по расстоянию, в которых каждая компонента по мощности не превосходит к (этот класс графов будем обозначать через WW к), то существует полиномиальный алгоритм распознавания их изоморфизма с временной сложностью 0((k\)2k2nk+l) [12]. Если же мы ограничимся разложениями по расстоянию с выделенным корнем, в которых каждая компонента по мощности не превосходит к, то получим алгоритм сложности 0((к\)2к2п3) для древесных разложений и 0((к\)2к2п2) для цепных разложений [12]. Соответствующие классы графов будем обозначать через HTVWk и nVVWk.
Цель наших исследований проблемы А и проблемы В состоит в рассмотрении ситуаций, когда на компоненты накладываются более общие условия вида:
каждая компонента порождает подграф, который принадлежит классу графов Qd, где d - некоторая натуральная константа (глава 3);
каждая компонента порождает подграф, который принадлежит классу графов ВС к, где к - некоторая натуральная константа (глава 4);
каждая компонента порождает подграф, который принадлежит классу графов Speci (глава 5).
Скажем несколько слов о том почему при рассмотрении древесных разложений по расстоянию мы требуем, чтобы корневое множество было одноэлементно. Если убрать это ограничение, то при выборе корневого множества может возникнуть, вообще говоря, слишком большой произвол и множество всех древесных (даже цепных и минимальных) разложений графа по расстоянию при этом может экспоненциально зависеть от количества вершин графа.
Нетрудно увидеть, что древесных разложений графа по расстоянию даже с одноэлементным корневым множеством может быть несколько. Ясно, что всегда существует цепное разложение графа по расстоянию для заданного корня. Если для некоторого корневого множества цепное разложение совпадает с минимальным древесным разложением, то можно показать, что множество древесных разложений по расстоянию для заданного корня состоит только из одного элемента - цепного разложения по расстоянию. Хотя в общем случае при выборе древесного разложения даже при заданном корневом множестве может возникать довольно большой произвол. Поскольку мы применяем древесные разложения графов по расстоянию к задаче распознавания изоморфизма графов, нам важно устранить этот произвол. Можно показать, что для заданного корневого множества однозначно получается только цепное разложение графа по расстоянию и минимальное древесное разложение графа по расстоянию. Поэтому в дальнейшем мы будем рассматривать для заданного корня только случаи цепного
разложения по расстоянию и минимального древесного разложения по расстоянию.
Введем обозначения для некоторых классов графов, которые встречаются в диссертации.
Block(Qd), где d - некоторое натуральное число. Связный граф G принадлежит классу Block(Qd), если любой блок графа G порождает в G подграф из класса Q& (в обозначениях проблемы А: К — Т - класс всех деревьев, a «S = «Si).
Block(BCk), где к - некоторое натуральное число. Связный граф G принадлежит классу Block(BCk), если любой блок графа G порождает в G подграф из класса ВСк (в обозначениях проблемы В: К = ВСк, Т - класс всех деревьев, a «S = Si).
DQld, где d и I - фиксированные натуральные числа. Граф G принадлежит классу DQld, если он обладает минимальным древесным разложением по расстоянию, у которого корневое множество одноэлементно, каждая компонента имеет не более / сыновей и каждая компонента порождает в G подграф из класса Qd.
VBCk, где А; - некоторое натуральное число. Граф G принадлежит классу VBCk, если он обладает цепным разложением по расстоянию, у которого корневое множество одноэлементно и каждая компонента порождает в G подграф из класса ВСк-
ТВС1к, где к и I - фиксированные натуральные числа. Граф G принадлежит классу 7~ВСк, если он обладает минимальным древесным разложением по расстоянию, у которого корневое множество одноэлементно, каждая компонента имеет не более I сыновей и каждая компонента порождает в G подграф из класса ВСк-
PathSpeci- Связный граф G принадлежит классу PathSpeci, если он обладает цепным разложением по расстоянию, у которого корневое множество одноэлементно и каждая компонента порождает в G подграф из класса Speci.
Перейдем к изложению результатов диссертации, но сначала скажем несколько слов о ее структуре. Материал, изложенный в диссертации разделен на 5 глав. Каждая из этих глав разделяется на параграфы. Утверждения (теоремы, леммы, предложения, следствия) нумеруются парами индексов, из которых первый указывает номер главы, а второй - номер утверждения данного типа в главе.
Первая глава диссертации носит вспомогательный характер. В ней вводятся некоторые понятия и приводятся утверждения, на которые опираются доказательства основных результатов диссертации.
Во второй главе мы рассматриваем разложения графов на блоки и точки сочленения.
Эти разложения при ограничениях на блоки, о которых мы говорили выше, могут быть использованы при построении полиномиального алгоритма распознавания изоморфизма в классе почти деревьев с параметром к, где к - некоторая натуральная константа.
Определение. Связный граф G называется почти деревом с параметром к, если он обладает таким остовным деревом Т, что каждый блок графа G содержит не более чем к не принадлежащих дереву Т ребер.
Почти деревья с параметром 1 называют деревьями Хусими. Легко видеть, что каждый блок дерева Хусими является либо ребром, либо циклом.
В разделе 2.1.2 предлагается алгоритм с временной сложностью 0(п2) распознавания изоморфизма для класса деревьев Хусими, т. е. доказывается, что справедлива следующая
Теорема 2.4 Существует алгоритм с временной сложностью 0(п2) распознавания изоморфизма деревьев Хусими.
Основным результатом раздела 2.2.2 является
Теорема 2.8 Для каждого натурального d существует полиномиальный алгоритм распознавания изоморфизма для класса графов Block(Qd)-
Заметим, что при доказательстве теоремы 2.8 использовались результаты Бабаи и Лакса, полученные при построении полиномиального алгоритма распознавания изоморфизма для класса связных графов Qd, т. е. связных графов, степени вершин которых не превосходят d [18].
Основным результатом раздела 2.3.3 является
Теорема 2.10 Для каждого натурального к существует полиномиальный алгоритм распознавания изоморфизма для класса почти деревьев с параметром к.
Следующая теорема является основным результатом параграфа 2.3.
Теорема 2.14 Для каждого натурального к существует алгоритм распознавания изоморфизма для класса графов Block(BCk) с временной сложностью 0(п$ ((2А;)!)6
(п+ №>)).
В последующих главах, как мы уже отмечали, рассматриваются разложения, которые являются частными случаями древесных разложений по расстоянию.
В главе 3 рассматриваются древесные сйзі-разложения. Фактически это минимальные древесные разложения, у которых каждая компонента порождает связный подграф. Заметим, что не все графы обладают разложениями такого рода. В качестве примера можно привести цикл длины 4.
Более точно, древесное разложение графа G по расстоянию ({Хі : і Є 1},Т = (I,F), г) называется древесным б^-разложением графа G, если \ХГ\ — 1 и для каждого і Є І подграфы G(Xi) графа G связные.
Пусть dn I- фиксированные натуральные числа. Будем говорить, что связный граф G является графом из класса DQ\, если он обладает древесным сйві-разложением ({Хі : і Є /}, Т = (І, F), г) таким, что для каждого і Є І подграф G(Xi) принадлежит ^ив дереве Т каждая вершина имеет не более І сыновей. Такие древесные dist-разложения будем называть Q^-древесными dist-разложениями.
В параграфе 3.2 рассматривается класс графов DQld и доказывается следующий результат.
Теорема 3.6 Для любых натуральных чисел d и I существует полиномиальный алгоритм распознавания изоморфизма для класса графов VQld.
В четвертой главе мы будем рассматривать классы цветных графов VBCk и ТВС1к, где к и I - натуральные константы.
Цветной граф G принадлежит классу VBCk, если он связный и для него существует цепное разложение Р =({^ : і Є /}, Т — (I, F), г) по расстоянию с выделенным корнем такое, что для каждого і Є I цветной граф G(Xi) содержится в классе ВСк-
Цветной граф G принадлежит классу ТВС1к, если он связный и для него существует минимальное древесное разложение D —({Хі : і Є 1},Т = (I,F), г) по расстоянию с выделенным корнем такое, что для каждого і Є I цветной граф G(Xi) содержится в классе ВСк и каждая вершина в Т имеет не более / сыновей. В дальнейшем такие древесные разложения по расстоянию с выделенным корнем будем называть TreeColork-разложениями. Заметим, что если цветной граф G Є TBClk, то множество всех его ТгееСо/ог^-разложений не обязательно одноэлементно.
Основной результат параграфа 4.3 - полиномиальный алгоритм распознавания изоморфизма для класса графов VBCk-
Теорема 4.3 Для каждого натурального к существует алгоритм распознавания изоморфизма для класса графов VBCk с временной сложностью 0(1\ ns ((2А;)!)6 (п + (2А02)).
Основной результат параграфа 4.4 - полиномиальный алгоритм распознавания изоморфизма для класса графов ТВС1к. Более точно, справедлива следующая
Теорема 4.7 Для любых натуральных чисел к и I существует алгоритм распознавания изоморфизма для класса графов ТВС\. с временной сложностью О (II пд ((2k)\y.(n + (2k)*)).
Заметим, что для фиксированных чисел к и I класс графов VBCk не обязательно содержится в классе ТВС1к, т.е. два последних результата не зависят один от другого.
В параграфе 5.3 мы рассматриваем класс графов PathSpec\. Будем говорить, что граф G принадлежит классу PathSpeci, если он связный и для него существует цепное разложение Р =({Хі : г Є /}, Т — (I,F), г) по расстоянию с выделенным корнем такое, что для каждого г Є I граф G(Xi) содержится в классе Spec\. В параграфе 5.3. доказывается
Теорема 5.5 Существует полиномиальный алгоритм распознавания изоморфизма для класса графов PathSpeci.
Хотелось бы отметить, что скорее всего для класса графов Spec\ справедливы результаты, аналогичные теоремам 2.14 и 4.7 для класса цветных графов ограниченной цветной кратности (имеется в виду полиномиальность алгоритмов, оценка сложности конечно будет другая). Пока этот вопрос специально автором диссертации не исследовался. Более того, вполне вероятно, что результаты, аналогичные теореме 5.5 и теоремам 2.14 и 4.7 для цветных графов, будут справедливы и для класса графов Speck-
Результаты диссертации докладывались на международном семинаре по теории групп (Екатеринбург, 2001), на международном семинаре "Дискретная математика и ее приложении "(Москва, 2004), на международной конференции "Дискретный анализ и исследование операции" (Новосибирск, 2004). Кроме того, автором было сделан ряд докладов на семинаре Л. Н. Шеврина "Алгебраические системы"в Уральском государственном университете.
Автор выражает глубокую признательность своему научному руководителю профессору В. А. Баранскому за постоянное внимание к работе и ценные замечания, способ-ствовашие ее улучшению.
Некоторые свойства графов, степени вершин которых ограничены
В этом параграфе приводятся некоторые свойства графов, степени вершин которых ограничены, и необходимые для дальнейшего изложения сведения об алгоритме Бабаи-Лакса распознавания изоморфизма в классе графов, степени вершин в которых не превосходят некоторой наперед заданной натуральной константы d. Во введении мы уже упомянули этот результат. Там же мы ввели обозначение Q& для этого класса графов. Как уже указывалось во введении, в процессе работы алгоритма Бабаи-Лакса значительную роль играют результаты из теории групп подстановок. Возможность их применения достигается сведением задачи распознавания изоморфизма связных графов, степень каждой вершины в которых не превосходит натуральной константы d, к задаче поиска группы автоморфизмов, оставляющих на месте некоторое ребро связного графа, степень каждой вершины в котором не превосходит d. Это сведение осуществляется следующим образом. Возьмем пару связных графов G\ и G2, степень каждой вершины в которых меньше или равна d. Зафиксируем в графе G\ ребро е\ = {щ,Уі}, добавим в G\ вершину W\, ребра {щ,и)\} и {w\,V\}, удалим ребро е\. Полученный граф обозначим через G\. Аналогично возьмем в графе G2 ребро е2, добавим в G2 вершину w2, ребра {u2,W2} и {w2,v2}, удалим ребро е2. Полученный граф обозначим через G 2. Затем графы G[ и G 2 объединяются и к объединению JI U G 2 добавляется ребро є = {wi,w2}. Полученный граф обозначим через G. В [18] показано, что за полиномиальное время можно построить порождающее множество полиномиальной мощности К группы автоморфизмов Aute(G) графа G, которая стабилизирует множество {wi,w2} или, что равносильно, фиксирует ребро є графа G. Очевидно, что если в К существует элемент, переставляющий uii и w2, то графы Gi и G2 изоморфны. Таким образом, пройдя в худшем случае по всем ребрам графа G2 мы установим будут ли изоморфны графы G\ и G2. Приведем несколько свойств групп вида Aute(G) которые понадобятся нам для дальнейшего изложения. Если К - некоторое множество подстановок из Sn, то через (К) будем обозначать группу подстановок, порождаемую множеством К. Для каждого натурального числа b определим класс групп Г&, состоящий из конечных групп, имеющих композиционные ряды такие что для каждого г, 1 г г — 1, выполняется [А : A i+1 ] Ь. Очевидно, ть с гь+1. Из утверждений, доказанных в [18], вытекает справедливость следующей леммы. Лемма 1.1. Пусть d - натуральная константа. Если граф G принадлежит классу Qd и е - ребро графа G, то 1) группа автоморфизмов Aute(G) граф/а G, фиксирующая ребро е, лежит в классе Ть, где b = —2 2) существует алгоритм полиномиальной сложности, который строит порожда ющее множество полиномиальной мощности группы Aute(G).
Полиномиальный алгоритм, строящий группу Aute(G) можно найти в монографии [18]. Оценка его времени работы довольно сложная функция, поэтому мы ее не приводим. В наших рассмотрениях нам будет достаточно его полиномиальности. Из последней леммы и возможности сведения задачи распознавания изоморфизма в классе графов Qd к задаче поиска группы автоморфизмов Aute(G) следует глубокий результат Бабаи-Лакса. Лемма 1.2. Пусть d - натуральная константа. Для класса графов Qd существует полиномиальный алгоритм распознавания изоморфизма. В следующей лемме [18] представлены важные свойства групп из класса Гь для каждого натурального 6. Лемма 1.3. (а) Если А Є Г , то любая подгруппа группы А содержится в Ть (b) Если А Є Гь, то любой гомоморфный образ группы А содержится в IV (c) Если N А, причем N Є Гй и A/N Є Г6, то А Є Г6. Следующее утверждение содержит необходимое нам для дальнейшего изложения свойство группы Aute(G). Лемма 1.4. Пусть b - фиксированное натуральное число. Существует полиномиальный алгоритм, который для каждой группы подстановок А Є Ть на множестве {1,..., п), заданной порождающим полиномиальной мощности множеством К, и произвольного множества Y С {1,...,п} строит порождающее множество полиномиальной мощности стабилизатора NA(Y) множества Y в группе А. Доказательство этой леммы можно найти в [18], там же приведен полиномиальный алгоритм нахождения группы NA(Y). Точная оценка сложности алгоритма нахождения NA(Y) не приводится по причинам, аналогичным тем, которые обсуждались после леммы 1.1. В заключение этого приведем результат, родственный лемме 1.4 для р-групп [18]. Он будет использоваться в 5-й главе диссертации. Лемма 1.5. Пусть нам известно порождающее множество К для р-группы подстановок А на п-элементном множестве X. Тогда существует алгоритм, который для любого подмножества Y множества X строит порождающее множество стабилизатора множества Y в группе А за время 0(\К\ п2 + п6 logp). Алгоритм, который упоминается в лемме 1.5 можно найти в [18]. Заметим, что в результате работы этого алгоритма, мы получаем порождающее множество мощности 0(п2) для стабилизатора множества Y в группе А. В этом параграфе приводятся некоторые свойства цветных графов (определение цветного графа см. на с. 4) с ограниченной кратностью цветов и необходимые для дальнейшего изложения сведения об алгоритме Бабаи распознавания цветного изоморфизма для класса цветных графов, кратности цветов в которых не превосходят некоторой наперед заданной натуральной константы к. Во введении мы уже упомянули этот результат. Там же мы ввели обозначение ВСк для этого класса графов. Как уже указывалось во введении, в процессе работы алгоритма Бабаи значительную роль играют результаты из теории групп подстановок. Возможность их применения достигается сведением задачи распознавания цветного изоморфизма цветных графов, кратности цветов в которых не превосходят к, к задаче поиска группы цветных автоморфизмов цветного графа, кратность каждого цвета, в котором не превышает 2к. Прежде чем рассказать как осуществляется это сведение, введем следующие понятия. Определение. Объединением цветных графов (Gi,/i) и (G2,f2) будем называть цветной граф (G, /) такой, что G = G\ U G2 и для каждой вершины v Є VG если v Є VGi, то f(v) = fi(v), а если v Є VG2, то f(y) = f2(v). Дополнительным графом или дополнением к цветному графу (G, /) будем называть цветной граф (#,/і) такой, что Я = G и f(v) — fi(v) для каждой вершины v графа Я. Цветной граф (Я,/і) будем называть цветным подграфом или просто подграфом цветного графа (G, /) если граф Н является подграфом графа G и цвет каждой вершин графа Я совпадает с ее цветом в G. Повсюду, если не оговорено противное, под изоморфизмом цветных графов мы будем понимать цветной изоморфизм. Определение. Пусть ((?ь /х), (G2, /г) — цветные графы. Биективное отображение ф : VGi — VG2 будем называть О-изоморфизмом цветных графов G\ и G2, если для любой пары вершин и и v графа Gi их образы ф{и) и ф(у) смежны в графе С?2 тогда и только тогда, когда и и v смежны в G\. Определение. Пусть (Gi,/i), (22,/2) — цветные графы, а і - некоторый цвет. Биективное отображение ф : VG\ - VG2 будем называть г-изоморфизмом цветных графов Gi и G2, если выполнены условия: 1) ф является О-изоморфизмом; 2) fi{v) = г тогда и только тогда, когда /2(Ф(У)) — г для любой вершины v графа G\. Если отображение является г-изоморфизмом, то будем говорить, что оно сохраняет цвет г.
Некоторые свойства древесных разложений по расстоянию
В этом параграфе мы определим древесные разложения графов по расстоянию и обсудим некоторые их свойства. Определение. Древесным разложением связного графа G = (VG,EG) по расстоянию называется тройка ({Хг : і є /}, Т = (/, F), г) такая, что 1) U ХІ — VG и ХІ П Xj — 0 для любых г Ф j, где г, j Є /; ІЄІ 2) Г является корневым деревом с корнем в вершине г Є /; 3) для каждого v Є V если v Є Xit то da(Xr, v) = dT(r, i), 4) для каждого ребра {v,w} Є E существуют такие г, j Є I, что v Є ХІ, W Є XJ ІЛ либо і = j, либо {i,j} 6 F. Если дерево Т — (I, F) является простой цепью, выходящей из корня г, то такое древесное разложение графа по расстоянию будем называть цепным разложением графа по расстоянию. Если множество Хг является одноэлементным, т.е. Xr = {и}, где и - некоторая вершина графа, то такое древесное разложение по расстоянию будем называть древесным разложением по расстоянию с выделенным корнем. На рис. 1 приведен пример древесного разложения по расстоянию для некоторого графа. Множества ХІ, где і Є I, называются компонентами древесного разложения по расстоянию. Множество ХТ мы будем называть корневым множеством или корнем древесного разложения по расстоянию. Очевидно, что всегда существует древесное разложение графа G по расстоянию с корнем в вершине и, но оно не всегда единственно. Сразу заметим, что цепное разложение по расстоянию с заданным корнем строится однозначно причем за линейное время. В соответствии с [12] введем следующие понятия. Если вершины і Є I и j Є І смежны в дереве Т, то будем называть компоненты Хі и Xj древесного разложения по расстоянию D смежными. В случае когда вершина j Є J является сыном вершины г є / в дереве Т, то будем говорить, что компонента древесного разложения Xj является сыном компоненты древесного разложения ХІ, а компонента древесного разложения ХІ является отцом компоненты древесного разло-Оісения Xj. Компоненту ХІ, где і Є I, будем называть листом древесного разложения по расстоянию D, если г - лист в дереве Т. В случае, когда і не является листом в дереве Т, компоненту ХІ будем называть внутренней компонентой древесного разложения по расстоянию D.
Например, в древесном разложении по расстоянию D\ графа G на рис. 1 (см. с. 20) компоненты Х3 и Х6 являются смежными, а Хз и!ц не являются смежными. Компоненты Xi и Х5 являются сыновьями комноненты Х2, a Х2, соответственно является отцом компонент X и Х$. Листья в этом древесном разложении - компоненты X?, Xg, Xg, Хю И ХЦ. Определение. Пусть D = ({ХІ : г Є /},Т = (I,F),r) - древесное разложение графа G по расстоянию. Для каждой компоненты древесного разложения ХІ определим множество V(D,Xi) = У Xj, где ТІ - максимальное корневое поддерево дерева Т с корнем в вершине І. Для древесного разложения по расстоянию D\ графа G на рис. 1 (см. с. 20) множество V(Di,X2) состоит из вершин графа G\, которые лежат в компонентах Х2, Xj, Х5, Х8, Xg и Х10. Подграф Gi(V(Di,X2)) графа G\, порождаемый множеством вершин V{D\, Х2), совпадает с подграфом Gi(X2 U Х4 U Х5 U Х8 U Х9 U Ххо). Множество V(Di,Xi) содержит все вершины графа G\. В частности, подграф G (V(Di,Xi)) графа G , порождаемый множеством вершин V(Di,Xi), совпадает с графом G . Вообще заметим, что на множестве всех древесных разложений графа по расстоянию с одним и тем же корнем можно ввести частичный порядок (древесное разложение Dx D2, если каждая компонента D\ является подмножеством некоторой компоненты D2). Относительно этого порядка цепное разложение с этим корнем будет наибольшим элементом. Бодлендер показал, что существует относительно этого порядка и наименьший элемент. Этот элемент (наименьший) можно определить конструктивно (см. следующее определение) и построить его за время, зависящее линейно от количества вершин и ребер графа. Это наименьшее древесное разложение будем называть минимальным (так как для каждого корневого множества получаются свое наименьшее древесное разложение). Очень важно для использовании конструкции древесных разложений по расстоянию при построении алгоритмов распознавания изоморфизма графов, что цепное разложение и минимальное разложение получаются однозначно. Сформулируем только что изложенные факты более строго. Определение. Пусть D — {{ХІ : г Є 1},Т = (I,F),r) - древесное разложение графа G по расстоянию. D называется минимальным, если для каждого і I порожденный подграф G(V(D, ХІ)) графа G является связным. В [12] доказано следующее утверждение. Предложение. 1. Пусть дан граф G и множество S С VG. Минимальное древесное разложение графа G по расстоянию с корневым множеством S единственно, и существует алгоритм с временной сложностью 0(\EG\ + \VG\), строящий минимальное древесное разложение графа G с корневым множеством S. Например, древесное разложение по расстоянию, изображенное на рис. 1 является минимальным. Алгоритм, который упоминается в предложении 1, можно найти в [12]. Эта глава состоит из трех параграфов.
Основной результат первого параграфа - полиномиальный алгоритм распознавания изоморфизма деревьев Хусими. Во втором параграфе рассматривается класс графов Blocked), т.е. класс графов таких, что каждый их блок порождает подграф из класса Qd- Одним из основных результатов второго параграфа является полиномиальный алгоритм распознавания изоморфизма для класса графов Block(Qd). Он приводится во втором разделе второго параграфа. В третьем разделе второго параграфа показано, что из этого резльтата вытекает существование при подходящем значении d алгоритма распознавания изоморфизма для почти деревьев с параметром к, где к - натуральное число, величина которого зависит только от d. В третьем параграфе рассматривается класс цветных графов Block(BCk), т. е. класс цветных графов таких, что каждый их блок порождает подграф из класса ВС . Основной результат третьего параграфа - полиномиальный алгоритм распознавания изоморфизма в классе графов Block(BCk). Напомним некоторые понятия, которые будут использоваться на протяжении всей этой главы. Определение. Связный граф G называется почти деревом с параметром к, если он обладает таким остовным деревом Т, что каждый блок графа G содержит не более чем к не принадлежащих дереву Т ребер. Почти деревья с параметром 1 называют деревьями Хусими. Легко видеть, что каждый блок дерева Хусими является либо ребром, либо циклом. Определение. Пусть G - связный граф с множеством блоков {Вг,..., Bs} и множеством точек сочленения {ci,... ,Q}. Граф bc(G), вершинами которого являются элементы Bi,...,Ba,ci...,ci и две вершины которого смежны, если одна соответствует блоку Вг, а другая точке сочленения Cj, причем Cj Є ВІ, называется графом блоков и точек сочленения графа G . Нетрудно показать, что граф блоков и точек сочленения любого графа G является деревом и что вершинами степени 1 могут быть только вершины, которые соответствуют блокам графа G. Граф блоков и точек сочленения будем в дальнейшем называть деревом блоков и точек сочленения. Пусть дан граф G и bc(G) - дерево блоков и точек сочленения графа G. Посмотрим, что представляет собой центр дерева bc{G) (определение центра графа можно найти почти в любой монографии по теории графов, например, [4]). Как известно, центр дерева состоит либо из одной, либо из двух смежных вершин. Возможны три случая. 1. Центр состоит из одной вершины Во, которая соответствует некоторому блоку графа G. 2. Центр состоит из одной вершины со, которая соответствует некоторой точке сочленения графа G. 3. Центр состоит из двух вершин Во и со, первая из которых соответствует некоторому блоку графа G, а вторая - точке сочленения. Если для дерева bc(G) выполняются случаи 1 или 2, то будем рассматривать его как корневое дерево, корнем которого является центр.
Алгоритм распознавания изоморфизма деревьев Хусими
Пусть G\ = (Vi,Ei), (?2 = (V2,E2) - деревья Хусими. При построении алгоритма распознавания изоморфизма деревьев Хусими G\ и Gi важную роль играют деревья блоков и точек сочленения bc{G\) и ftc(G2). Естественно имеет смысл рассматривать только следующие три случая. A. Центр bc(G\) состоит из одной вершины, которая соответствует блоку графа G\. Центр 6с(С?2) состоит из одной вершины, которая соответствует блоку графа G . B. Центр bc(Gi) состоит из одной вершины, которая соответствует некоторой точке сочленения графа G\. Центр bc{G2) состоит из одной вершины, которая соответствует некоторой точке сочленения графа G2. C. Центры bc(Gi) и bc{G2) состоят из двух вершин. Если для центров деревьев bc{G{) и bc(G2) не имеет место ни один из этих случаев, то это означает, что деревья Хусими G\ и G2 не изоморфны. Перейдем к изложению алгоритма распознавания изоморфизма деревьев Хусими. В ходе своей работы алгоритм приписывает метки (натуральные числа) вершинам деревьев bc(Gi) и bc(G2). Он делает это таким образом, что корням деревьев будут приписаны одни и те же метки, если и только если графы G\ и G% изоморфны. Сначала приписываются метки узлам деревьев, находящимся на самом нижнем уровне, затем, используя эти метки, приписываем метки вершинам, находящимся на уровень выше и т.д., пока не дойдем до корней. Необходимо иметь в виду, что сопоставление меток узлам, которые соответствуют точкам сочленения, и узлам, которые соответствуют блокам, осуществляется по-разному. Пусть мы приписали метки вершинам, которые находятся на расстоянии k + 1 от корня. Если вершины, расположенные на расстоянии к от корня, соответствуют точкам сочленения, то каждой из этих вершин ставим в соответствие упорядоченный по возрастанию кортеж меток ее сыновей. Вершинам приписываем одинаковые метки тогда и только тогда, когда кортежи, сопоставленные им, имеют одинаковую длину и совпадают поэлементно. В том случае, если вершины, расположенные на расстоянии к от корня, соответствуют блокам, поступаем по-другому. Пусть р - вершина дерева блоков и точек сочленения, находящаяся на расстоянии к от корня, а В = {vi, v2, .. vm} - блок, которому она соответствует. Допустим, что при помечивании вершин, находящихся на расстоянии к + 1 от корня, использовалось t меток. Имеет смысл выделить следующие три случая: 1) р является внутренней вершиной дерева, т. е. р не является ни листом, ни корнем; 2) р является корнем; 3) р является листом. Расмотрим эти случаи по порядку. 1) Пусть р является внутренней вершиной дерева. Обозначим через v , Vi2,... ViT точки сочленения блока В, которые соответствуют сыновьям вершины р в дереве бло ков и точек сочленения, a h,h, ,lr метки этих сыновей. Предположим, что VjQ точка сочленения блока, которая соответствует отцу вершины р в дереве блоков и то чек сочленения. Определим на вершинах цикла В цветную функцию / следующим образом: Полученный цветной цикл будем обозначать Bf. Заметим, что в нем есть только одна вершина цвета t + 2. Каждой внутренней вершине ставим в соответствие признак internal (внутренняя) и цветной цикл Bf. 2) Пусть р является корнем, v jViz,. ..Vir - точки сочленения блока В, которые соответствуют сыновьям вершины р в дереве блоков и точек сочленения, &Іі,І2,...,Іг метки этих сыновей. Определим на вершинах цикла
В цветную функцию / следующим образом: Полученный цветной цикл будем обозначать Bf. Корню р ставим в соответствие признак root и цветной цикл Bf. 3) Если вершина р является листом, то ставим ей в соответствие признак leaf и количество вершин в цикле В. Таким образом, каждая вершина, находящаяся на расстоянии к от корня, получает признак (internal, root или leaf) и ей сопоставляется цветной цикл или натуральное число. Опишем, как осуществляется приписывание меток. Если к — 0, то мы имеем случай 2 и всего два цветных цикла, которые соответствуют корням bc(Gi) и bc(G2). Применяем алгоритм 2.1. Если эти цветные циклы изоморфны, то обоим корням приписывается метка 1, в противном случае они не изоморфны, и им приписываются различные метки. Пусть к 0, Pi,P2, -Pd вершины, находящиеся на расстоянии к от корня, причем первые d\ из них, о?! d, являются внутренними. Сначала приписываем метки вершинам pi,... ,Pdj- С помощью алгоритма 2.3 разбиваем блоки В\,..., Bdl, которые им соответствуют на классы, изоморфных цветных циклов Pi,..., Pmax- Если ВІ Є Pj, то вершине Pi приписываем метку j. Таким образом, каждой внутренней вершине, расположенной на расстоянии к от корня, будет сопоставлено натуральное число из диапазона 1,..., max. Упорядочиваем по возрастанию длины циклов, которые соответствуют листьям: Pdi+b iVd- Вершинам, соответствующим циклам наименьшей длины, приписываем метку max + 1. Вершинам, которым соответствуют циклы со следующей по порядку длиной, отличной от наименьшей, приписываем метку max + 2 и т. д. Алгоритм 2.4. (Изоморфизм деревьев Хусими). Вход: G\ = (Vi,Ei), G2 = (V2,E2) - деревья Хусими. Выход: возвращается true, если G\ и G2 изоморфны; возвращается false, если G\ и G2 не изоморфны. 1. Поиском в глубину находятся блоки и точки сочленения графов G\ и G2 (см. [4]). Для каждого из этих графов строятся деревья блоков и точек сочленения bc{G\) и bc{G2). 2. Находятся центры деревьев bc{G\) и bc(G2)(cu. [3]). Если имеет место один из случаев А или В (см. с. 25), то центры деревьев объявляются bc(Gi) и bc(G2) их корнями, и деревья тем самым превращаются в корневые. Если имеет место случай С (см.с.25), то корнями деревьев bc{G\) и bc(G2) объявляются вершины их центров, которые отвечают точкам сочленения графов G\ и G2 соответственно. Если ни один из этих случаев не имеет место, то алгоритм заканчивает работу, возвращая false. Перейти к п. 3. 3. Находим hi - высоту дерева bc{G\) и h2 - высоту дерева bc(G2). Перейти к п.4. 4. Если hi ф h2, то bc(Gi) и bc(G2) не изоморфны, а, следовательно, и графы G\ и G2 не изоморфны и алгоритм завершает свою работу, возвращая false. В противном случае, если h\ = h2, то h :— h\. 5. Если h = 0, то перейти к п. 6. Иначе перейти к п. 7. 6. Графы G\ и G2 являются циклами. Если Vi = \V2\, то графы изоморфны и алгоритм завершает работу, возвращая true, в противном случае графы не изоморфны и алгоритм завершает работу, возвращая false. 7. к :— h (к будет пробегать значения от h до 0). Перейти к п. 8. 8. Если к — 0 и корни деревьев bc(G\) и bc(G2) соответствуют блокам, то перейти к п. 15. Если к ф 0, то пусть S\ = {p\,...,pl} - список всех вершин дерева bc{Gx), находящихся на расстоянии А; от корня. Аналогично, Sf = {р\,...,р п\ - список всех вершин дерева bc(G2), находящихся на расстоянии к от корня. Если г ф т, то графы Gi и G2 не изоморфны и алгоритм заканчивает свою работу, возвращая false. Если г = т, то перейти к п. 9. 9. Если вершины, находящиеся на расстоянии к от корня, соответствуют блокам, то переходим к п. 10. Если вершины, находящиеся на расстоянии к от корня, соответствуют точкам сочленения, то перейти к п. 13. 10. Предположим, что вершины в списках Si и 5 расположены так, что первые s вершин Si и первые s из Si являются внутренними. Очевидно, что если s ф s , то графы не изоморфны и алгоритм заканчивает работу, возвращая false. Пусть В\,..., В} - блоки графа G\, которые соответствуют вершинам из S\, а В\,..., В - блоки графа G2, которые соответствуют вершинам из . Согласно нашим обозначениям список Internal Blocks = {В\,..., В], В\,..., В%} содержит блоки графов G\ и G2, которые соответствуют внутренним вершинам, а список Leaf Blocks — {B]+l,...,В),, В%+1,..., В?} содержит блоки графов G\ и G2, которые соответствуют листьям. Перейти п .11. 11. Приписываются цвета вершинам блоков В} и ?, i,j Є {1,...,s} так, как это описывалось выше перед алгоритмом. С помощью алгоритма 2.3 множество блоков
Изоморфизмы графов, блоки которых являются графами с ограниченными степенями вершин
В этом разделе мы будем решать следующую задачу. Пусть Qd - класс связных графов, степени вершин которых не превосходят фиксированного натурального числа d. Как было отмечено выше, существует алгоритм распознавания изоморфизма для класса графов Qd- Обозначим через Block(Qd) класс связных графов, блоки которых принадлежат классу Qd- Иными словами, Block(Gd) состоит из связных графов, блоки которых являются графами с ограниченными степенями вершин. В этом разделе представлен алгоритм, решающий задачу распознавания изоморфизма для класса графов Block{gd). Напомним некоторые термины, используемые при рассмотрении корневых деревьев. Вершины степени 1 в bc(G), не принадлежащие центру, называются листьями. Высота дерева - это длина самого длинного пути из корня в какой-нибудь лист. Глубина вершины - это длина пути из вершины в корень. Пусть Gi = (Vi,Ei), Gi = (V2,E2) - графы из Block(Gd)- В приводимом здесь алгоритме, важную роль будут играть деревья блоков и точек сочленения bc(Gi) и 6с(Сг). Очевидно, что необходимым условием изоморфизма любой пары графов, является изоморфизм их деревьев блоков и точек сочленения. Кроме того ясно, что при изоморфизме деревьев центр одного дерева переходит в центр второго. Поэтому имеет смысл рассматривать только следующие три случая. A. Центр bc(Gi) состоит из одной вершины, которая соответствует блоку графа G\. Центр bc(G2) состоит из одной вершины, которая соответствует блоку графа G2 B. Центр bc(Gi) состоит из одной вершины, которая соответствует некоторой точке сочленения графа G\. Центр bc{G2) состоит из одной вершины, которая соответствует некоторой точке сочленения графа G2. C. Центры bc(Gi) и bc(G2) состоят из двух вершин. Если для центров деревьев bc(Gi) и bc(G2) ни один из этих случаев не выполняется, то графы Gi и G2 не изоморфны. Ниже под уровнем вершины будем понимать разность между высотой дерева и глубиной этой вершины. Необходимо отметить, что вершины дерева блоков и точек сочленения, находящиеся на одном уровне, либо все соответствуют точкам сочленения, либо все соответствуют блокам. Перейдем к изложению алгоритма. В ходе своей работы алгоритм приписывает метки (натуральные числа) вершинам деревьев bc(G\) и bc(G2) таким образом, что корням этих деревьев будут приписаны одни и те же метки тогда и только тогда, когда графы G\ и G2 изоморфны. Сначала приписываются метки вершинам, находящимся на самом "нижнем" (нулевом) уровне, затем используя эти метки приписываем метки вершинам, находящимся на уровень выше и т.д., пока не дойдем до корней. Необходимо иметь в виду, что сопоставление меток для вершин, которые соответствуют точкам сочленения, и для вершин, которые соответствуют блокам, осуществляется по-разному. Предположим, что мы приписали метки вершинам, которые находятся на расстоянии к + 1 от корня. Для вершин, находящихся на расстоянии к от корня, производим следующие действия. Сначала рассмотрим случай, когда эти вершины соответствуют точкам сочленения. Каждой из них ставим в соответствие упорядоченный по возрастанию кортеж меток сыновей. Затем, используя алгоритм лексикографической сортировки [2] (гл.З), упорядочиваем все эти кортежи. Получаем упорядоченный набор кортежей.
Вершинам, которые представлены первым кортежем ставим в качестве метки число 1. Вершинам, которые представлены вторым отличающимся кортежем - число 2 и т.д. Таким образом, одинаковые метки получат только те вершины, у которых одинаковые кортежи. Теперь рассмотрим случай когда вершины, находящиеся на расстоянии к, соответствуют блокам. Пусть р - вершина дерева блоков и точек сочленения, находящаяся на расстоянии к от корня, а В - блок графа, которому она соответствует. Допустим, что при помечивании вершин, находящихся на расстоянии к + 1 от корня, использовалось t меток. Имеет смысл выделить следующие два случая: 1) р не является листом; 2) р является листом. Расмотрим эти случаи по порядку. 1) Пусть р не является листом. Обозначим точки сочленения блока В, которые со ответствуют сыновьям вершины р, через Vi,V2,...vr, а метки этих сыновей обозначим через Іі,І2,... ,/г, соответственно. Предположим, что VQ - точка сочленения блока, ко торая соответствует отцу вершины р в дереве блоков и точек сочленения. Определим на вершинах блока В цветную функцию / следующим образом: Полученный цветной граф будем обозначать {B,f). 2) Пусть р является листом. Обозначим точку сочленения блока, которая соответ ствует отцу вершины р в дереве блоков и точек сочленения через vio. Определим на вершинах блока В цветную функцию / следующим образом: Полученный цветной граф будем обозначать (B,f). Таким образом, каждой вершине, находящейся на расстоянии к от корня, сопоставляется цветной граф. Получаем набор цветных графов {(Ві, /і),..., (Bs, fs)} с ограниченными степенями вершин. С помощью алгоритма 2.7 разбиваем их на классы Р1;... Ps, где два цветных графа принадлежат одному и тому же классу тогда и только тогда, когда они изоморфны. Если блок В Є Pi, то вершину р, которой он соответствует, помечаем меткой і. Представим эти рассуждения в виде алгоритма. Алгоритм 2.8.
Распознавание изоморфизма связных графов, блоки которых являются графами с ограниченными степенями вершин. Вход: Gi и G2 - связные графы, блоки которых являются графами с ограниченными степенями вершин. Выход: возвращается true, если Gi и G2 изоморфны, возвращается false, если G\ и G2 не изоморфны. 1. С помощью поиска в глубину находятся блоки и точки сочленения графов G\ и G2 (см. [4]) и строится для каждого из этих графов дерево блоков и точек сочленения bc(Gi) и bc(G2). 2. Находятся центры деревьев bc(G\) и bc(G2) (см. [3]). Если имеет место один из случаев А, В или С (см.с.32), то перейти к п.З. В противном случае графы не изоморфны, и алгоритм заканчивает работу, возвращая false. 3. Находим hi - высоту дерева bc(Gi) и h2 - высоту дерева bc{G2). 4. Если hx ф h2, то bc(Gi) и bc(G2) не изоморфны, поэтому и графы G\ и G2 не изоморфны и алгоритм завершает свою работу, возвращая false. В противном случае, если hi = h2, то h := hi, к := h; (к будет пробегать все значения от 0 до Л) и переходим к п. 5. 5. Если h = 0, то Gi и G2 являются графами степени, вершин которых ограничены. Поэтому можно применить к ним алгоритм Бабаи-Лакса. Если графы изоморфны, то алгоритм возвращает true. В противном случае алгоритм возвращает false. Алгоритм заканчивает работу. 6. Пусть Z\ = {р\,--.,РІ} - множество вершин bc(Gx), находящихся на расстоянии к от корня, a Z\ — {р\,... ,p2s,} - множество вершин bc(G2), находящихся на расстоянии к от корня. Если s ф s , то графы не изоморфны и алгоритм заканчивает работу, возвращая false. Пусть s = s . Если вершины уровня к деревьев bc(Gi) и bc(G2) соответствуют блокам, то перейти к п. 7. В противном случае перейти к п. 8. 7. Пусть В\,... В\ - блоки графа G\, которые соответствуют вершинам из Z\, а В\,... В% - блоки графа G2, которые соответствуют вершинам из Z\. Каждому из блоков сопоставляется цветной граф так, как это описывалось в рассуждениях перед алгоритмом. Получается набор цветных графов {{В}, fl), (В?, fj) : i,j = l,...s}. С помощью алгоритма 2.7 этот набор разбивается на изоморфные классы Р1;...РГ. Если блок В{ попадает в класс Рх, вершине р\ дерева bc(Gj), которая ему соответствует, приписывается метка г . Перейти к п. 9. 8. Каждой вершине р\, г Є {1,... s}, j Є {1,2}, ставим в соответствие упорядоченный по возрастанию кортеж меток ее сыновей. С помощью лексикографической сортировки упорядочиваем эти кортежи. Пусть С = (СЬ...,СГ) - упорядоченная последовательность этих кортежей. Вершинам, которые представлены первым кортежем в С, сопоставляется 1. Вершинам, которые представлены вторым отличающимся кортежем, сопоставляется 2 и т.д. Таким образом, каждая из вершин р\, і = 1,...,г, получает метку. Перейти к п. 9. 9. Если к 0, то к := к — 1 и перейти к п. 6. Если к = 0, то перейти к п. 10. 10. Если метки, приписанные корням bc{G\) и bc(G2), совпадают, то графы Gi и G2 изо морфны и алгоритм заканчивает работу, возвращая true. В противном случае графы
