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

• Расин, Олег Вениаминович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Расин, Олег Вениаминович

1. Предварительные сведения

1.1. Некоторые сведения о порождающих множествах в группах подстановок

1.2. Некоторые свойства графов, степени вершин которых ограничены

1.3. Некоторые свойства цветных графов с ограниченной кратностью цветов

1.4. Некоторые свойства древесных разложений по расстоянию.

2. Изоморфизмы графов и двухсвязные компоненты графов

2.1. Изоморфизмы деревьев Хусими.

2.1.1. Вспомогательные алгоритмы.

2.1.2. Алгоритм распознавания изоморфизма деревьев Хусими

2.2. Изоморфизмы почти деревьев.

2.2.1. Изоморфизмы цветных графов с ограниченными степенями вершин

2.2.2. Изоморфизмы графов, блоки которых являются графами с ограниченными степенями вершин.

2.2.3. Изоморфизмы почти деревьев с параметром к.

2.3. Изоморфизмы графов, блоки которых являются графами из класса ВСк.

3. /^¿-разложения и изоморфизмы графов

3.1. Алгоритм распознавания изоморфизма для класса графов ТЯа.

3.2. Алгоритм распознавания изоморфизма для класса графов

4. Изоморфизмы цветных графов

4.1. Цветные двухкомпонентные графы.

4.2. Алгоритм распознавания изоморфизма для класса цветных графов ТВСк

4.3. Алгоритм распознавания изоморфизма для класса цветных графов ТВС1к

5. Изоморфизмы графов с простым спектром и цепные разложения по расстоянию

5.1. Некоторые факты и обозначения

5.2. Изоморфизмы графов из класса Бресх.

5.3. Изоморфизмы графов в классе РаОгБрес1.

Введение диссертации (часть автореферата) на тему «Полиномиальные алгоритмы распознавания изоморфизма в некоторых классах графов»

Данная диссертация посвящена изучению проблемы изоморфизма графов. Здесь и далее под графами мы понимаем конечные неориентированные графы без петель и кратных ребер. Для графов мы будем пользоваться системой обозначений из книги [1]. Множество вершин графа С? будем обозначать через УС или У (С), а множество ребер - через ЕС или Е(С). Обычно через п будем обозначать количество вершин (или порядок) графа, если не оговорено противное, а через т - число его ребер. Проблема изоморфизма графов состоит в следующем: существует ли полиномиальный алгоритм, который для каждой пары графов распознает изоморфны они или нет.

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

Доказано, что задача распознавания изоморфизма графов лежит в классе АТР, но неизвестно является ли она ТУР-полной. Установлено, что задача распознавания изоморфизма двух графов полиномиально эквивалентна задаче поиска числа изоморфизмов между двумя графами [18]. Так как задачи распознавания и перечисления для всех известных NР-полных задач не являются полиномиально эквивалентными, существует гипотеза, что задача распознавания изоморфизма графов не является /УР-полной [5], [17].

В силу этого возможно, что при Р ф ЫР, задача распознавания изоморфизма графов и все задачи, полиномиально эквивалентные ей, образуют отдельный класс так называемых изоморфно полных задач. Примеры таких задач можно найти, в частности, в [18] и [19].

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

Из известных алгоритмов распознавания изоморфизма для класса всех графов наименьшую временную сложность имеет алгоритм Земляченко [5]. Бабаи и Лаксом было показано, что временная сложность этого алгоритма 0(еп^+0^) [19], где п - количество вершин графов.

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

1) построение так называемых эвристических алгоритмов распознавания изоморфизма графов;

2) построение полиномиальных алгоритмов распознавания изоморфизма для отдельных классов графов.

Результаты, представленные в диссертации имеют отношение ко второму направлению, но хотелось бы коротко рассказать об основных фактах, касающихся эвристических алгоритмов распознавания изоморфизма графов. Эти алгоритмы основаны на довольно естественной идее расклассифицировать вершины графов таким образом, чтобы избежать полного перебора. Иными словами, если С?! и С?2 - графы, между которыми проверяется наличие изоморфизма, то мы разбиваем множества вершин графов и

С?2 на классы, приписывая вершинам метки или, иными словами, цвета так, что изоморфизм может отображать вершину и графа в вершину V графа С2 только если и и V имеют одинаковый цвет. Для этого используются некоторые свойства вершин графов, инвариантные относительно изоморфизма. В качестве простейшего примера можно привести классификацию вершин по их степеням. Алгоритмы, основанные на идее разбиения множества вершин на классы, можно найти, например, в [15], [16], [20], [21]. Необходимо отметить, что хотя в большинстве случаев они и многие подобные им алгоритмы, как правило, достаточно эффективны, время работы в худшем случае у них экспоненциально. Попутно заметим, что алгоритм в статье [20] являлся базовым при написании ее автором программы ИаиЬу, которая для пары произвольных графов проверяет являются ли они изоморфными. Многие исследователи (см., в частности, [17]) полагают, что ИаиЬу является на данное время наиболее эффективным по быстродействию программным средством распознавания изоморфизма произвольных графов.

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

Определение. Цветным графом называется пара (С,/), где С - обыкновенный граф, а / - функция из множества вершин графа (7 в некоторый начальный отрезок натурального ряда {1,., ¿}. Для вершины V графа С число /(г>) называется цветом вершины V. Число вершин цвета г называется кратностью цвета г.

Цветной граф (С,/) будем обозначать также через Gf. Множество вершин цвета г в цветном графе 0} будем обозначать через С* и называть его г-м цветным классом, а множество всех цветных классов С1;. ,Ск обозначим через С и будем называть его разбиением на цветные классы множества вершин цветного графа С?/.

Понятно, что цвета в цветном графе (С, /) можно задавать не только с помощью цветной функции /. Очень часто мы будем брать граф С, а потом указывать разбиение С = {Сь ., С(} множества его вершин на цветные классы.

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

Известно, что задача распознавания изоморфизма в классе всех цветных графов полиномиально эквивалентна задаче распознавания изоморфизма графов [18], иными словами она изоморфно полна.

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

К таким классам графов относятся корневые деревья [2], деревья [3], связные графы, степени вершин которых ограничены натуральной константой [18], графы интервалов [14], графы ограниченной древесной ширины [13], планарные графы [7], графы, род которых ограничен натуральной констаной [18], графы с ограниченной древесной шириной по расстоянию [12], цветные графы, кратность каждого цвета в которых ограничена некоторой константой [18], и графы, у которых кратности собственных чисел ограничены некоторой константой [10].

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

Пусть d - некоторая натуральная константа. Обозначим через Qd класс связных графов, степени вершин которых не превосходят d. Алгоритм распознавания изоморфизма графов в классе доказательство корректности его работы, оценку его временной сложности и доказательство того, что она (оценка) справедлива, можно, как уже указывалось выше, найти в монографии [18]. Эту оценку сложности алгоритма распознавания изоморфизма для класса графов Q& мы приводить не будем, поскольку она является довольно сложной функцией. Заметим только, что она примерно составляет 0(nd!)[19]. В работах [17] и [18] говорится, что Лаке утверждает о возможности существенного уменьшения этой оценки. Необходимо отметить, что для класса графов С?3 был построен полиномиальный алгоритм распознавания изоморфизма сложности 0(п4) [18]. Этот алгоритм использует по сути дела такие же методы, как и более общий алгоритм. Подробнее об алгоритме Бабаи-Лакса распознавания изоморфизма для класса графов Q& мы расскажем в параграфе 1.2.

Введем обозначение ВСк для класса всех цветных графов, цветная кратность которых не превосходит натурального числа к, т. е. для каждого цветного класса С* графа G 6 ВСк имеем |С,| < к. Бабаи разработал полиномиальный алгоритм распознавания изоморфизма для класса цветных графов ВС к [18]. Временная сложность алгоритма Бабаи 0(п6 • (2&)!6 • (п + (2к)2)). Схема работы этого алгоритма приведена в параграфе 1.3.

Введем обозначение еще для одного класса графов, для которого построен полиномиальный алгоритм распознавания изоморфизма. Пусть дан обыкновенный п-вершинный граф G, и пусть j4(G) - матрица смежности графа G. Спектром графа G называют набор собственных значений Ль Л2,., Хп его матрицы смежности A(G). Вообще говоря, числа Aj, где г = 1,., п, не обязательно попарно различны. Заметим, что числа А¿, где г — 1 ,.,п, называют собственными значениями графа G. Кратностью собственного значения А*, где i = 1,., п, называется число его вхождений в набор Аь А2,., А„ или, что то же самое, кратность корня A* в характеристическом многочлене матрицы A{G).

Далее для каждого k е N через Specf. будем обозначать класс графов, в которых кратность каждого собственного значения не превосходит к. Для любого натурального числа к существует полиномиальный алгоритм распознавания изоморфизма для класса графов Speck [10]. Заметим, что сложность этого алгоритма 0(п4к+с), где с-некоторая положительная константа.

Необходимо отметить, что для класса графов Spec\ существует алгоритм распознавания изоморфизма с временной сложностью 0(п3). Этот алгоритм в отличие от алгоритма распознавания изоморфизма для класса Speck, где к > 1, не использует теоретико-групповой подход. Схема работы алгоритма распознавания изоморфизма графов для класса Specx приводится в параграфе 5.2.

Перейдем теперь к обсуждению задач, рассматриваемых в диссертации.

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

Определение. Пусть G - связный граф с множеством блоков {В\,., Bs} и множеством точек сочленения {ci,., q}. Граф bc(G), вершинами которого являются элементы из {Bi,., Bs, ci., cj и две вершины которого смежны, если одна соответствует блоку Bi, а другая точке сочленения Cj, причем Cj € Д, называется графом блоков и точек сочленения графа б .

Нетрудно показать, что граф блоков и точек сочленения любого графа (? является деревом и что вершинами степени 1 могут быть только вершины, которые соответствуют блокам графа й. Граф блоков и точек сочленения будем в дальнейшем называть деревом блоков и точек сочленения.

Пусть К, - произвольный класс графов, для которого известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, а «? - некоторый тип "древовидных" разложений графов на компоненты. В данной работе мы будем рассматривать следующие типы "древовидных" разложений графа: представление графа в виде дерева блоков и точек сочленения (см. выше); древесные разложения графов по расстоянию [12]; минимальные древесные разложения графов по расстоянию [12]; цепные разложения графов по расстоянию [12] и т. п.

Будем говорить, что граф принадлежит классу Т£1С, если он обладает разложением типа 5 на компоненты, принадлежащие классу /С, а соответствующее дерево компонент принадлежит классу Т. Если класс Т совпадает с классом всех деревьев, то в этом случае класс графов Т5/С будем обозначать просто через ¿>/С.

Диссертация посвящена рассмотрению следующих двух проблем.

Проблема А. Пусть К. - произвольный класс графов, для которого известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, а <5 - некоторый тип "древовидных" разложений графов на компоненты. Существует ли полиномиальный алгоритм распознавания изоморфизма для класса графов 7~<5/С ?

Проблема В. Пусть К - произвольный класс цветных графов, для которого известен полиномиальный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, а «5 - некоторый тип "древовидных"разложений графов на компоненты. Существует ли полиномиальный алгоритм распознавания изоморфизма для класса цветных графов Т8К ?

Отметим, что проблема А фактически уже рассматривалась в работе Бодлендера [13] для случая, когда в качестве Т фигурирует класс всех деревьев, в качестве с> -древесные разложения графов, а в качестве К - класс всех графов, число вершин в которых ограничено некоторой натуральной константой.

Пусть С - некоторый граф, амии- его вершины. Длина кратчайшего маршрута из вершины и в вершину V обозначается через до{и,у) и называется расстоянием между вершинами и и у.

Определение. Пусть С? = (V, Е) - связный граф. Древесным разложением графа (7 по расстоянию называется тройка ({.А^ : г € I}, Т = (/, Г), г) такая, что

1) У Хг — V и Х{ П X,- = 0 для любых г ф где г, з € /; ш

2) Т является корневым деревом с корнем в вершине г £ I;

3) для каждого V € V если V € X¿, то с1о(Хг>ь) = с1т(г,г),

4) для каждого ребра {г>,ги} € Е существуют такие г, з € /, что V 6 Х^ ю е Х^ и либо г =; з, либо {г, ]} € Р.

Если дерево Т = (/, F) является простой цепью, то такое древесное разложение связного графа по расстоянию будем называть цепным разложением графа по расстоянию.

Если множество ХТ является одноэлементным, т. е. Хг = {и}, где и - некоторая вершина графа, то такое древесное разложение по расстоянию будем называть древесным разложением по расстоянию с выделенным корнем.

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

Множества Х^ где г £ I, называются компонентами древесного разложения по расстоянию. Множество ХТ мы будем называть корневым множеством или корнем древесного разложения по расстоянию.

Будем говорить, что компонента X^ является сыном компоненты X,, если в корневом дереве Т вершина i является сыном вершины

Определение. Пусть И = ({Хг : г 6 /},Т = (7,.Р),г) - древесное разложение графа (? по расстоянию. Для каждой компоненты древесного разложения Хг определим множество У{0, X¿) = Xj, где - максимальное корневое поддерево дерева Т с корнем в вершине г.

Определение. Пусть В — ({^ : г € 1},Т — (/,- древесное разложение графа С по расстоянию. £> называется минимальным, если для каждого г € / порожденный подграф Хг)) графа (7 является связным.

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

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

1) - разложение графов на блоки и точки сочленения;

2) ¿>2 цепные разложения графов по расстоянию, корневые множества которых одноэлементны (заметим, что в этом случае естественно считать, что соответствующий класс Т совпадает с классом цепей);

3) 5з - минимальные древесные разложения графов по расстоянию, корневые множества которых одноэлементны.

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

1) каждая компонента порождает подграф, который принадлежит классу графов где в, - некоторая натуральная константа (глава 3);

2) каждая компонента порождает подграф, который принадлежит классу графов ВС к, где к - некоторая натуральная константа (глава 4);

3) каждая компонента порождает подграф, который принадлежит классу графов вресх (глава 5).

То, что нами рассматриваются только классы графов, алгоритмы распознавания изоморфизма которых были получены теоретико-групповыми методами, не случайно. В частности, это обосновывается следующим. Пусть К, - класс графов, в котором задача распознавания изоморфизма решается за полиномиальное время чисто комбинаторными методами. С помощью небольшой модернизации соответствующего алгоритма обычно удается решить за полиномиальное время и задачу распознавания изоморфизма в классе ТЭуК, даже в случае, когда класс Т совпадает с классом всех деревьев. Кроме того, отметим, что для некоторых классов К имеет место равенство К — 8\К (например, если К - класс планарных графов).

Для разложений типов <5>2 и ¿>з в случае, если /С - класс графов, в котором задача распознавания изоморфизма решается за полиномиальное время чисто комбинаторными методами, ситуация не столь проста и скорее всего тоже требует применения теоретико-групповых методов.

По поводу разложений типов 52 и <5з необходимо заметить следующее. Они и аналогичные им разложения, как уже было отмечено, рассматривались в работе [12]. Там были построены алгоритмы распознавания изоморфизма для класса графов, древесная ширина по расстоянию которых не превосходит некоторой наперед заданной константы к (или в наших обозначениях для класса где К совпадает с классом графов, количество вершин в которых не более к). Заметим, что при этом, вообще говоря, не требовалось, чтобы корневое множество было одноэлементно. Достаточно было, чтобы оно принадлежало этому классу /С.

Более точно, пусть к - некоторое натуральное число. Если графы обладают древесными разложениями по расстоянию, в которых каждая компонента по мощности не превосходит А; (этот класс графов будем обозначать через 1~Т>У^к), то существует полиномиальный алгоритм распознавания их изоморфизма с временной сложностью 0((к\)2к2пк+2), где п - количество вершин в графах [12]. В случае же если графы обладают цепными разложениями по расстоянию, в которых каждая компонента по мощности не превосходит к (этот класс графов будем обозначать через РТУУУк), то существует полиномиальный алгоритм распознавания их изоморфизма с временной сложностью 0((к\)2к2пк+1) [12]. Если же мы ограничимся разложениями по расстоянию с выделенным корнем, в которых каждая компонента по мощности не превосходит к, то получим алгоритм сложности 0((к\)2к2п3) для древесных разложений и 0((к\)2к2п2) для цепных разложений [12]. Соответствующие классы графов будем обозначать через Т1ТТ>УУк и

Цель наших исследований проблемы А и проблемы В состоит в рассмотрении ситуаций, когда на компоненты накладываются более общие условия вида:

1) каждая компонента порождает подграф, который принадлежит классу графов Я а, где с? - некоторая натуральная константа (глава 3);

2) каждая компонента порождает подграф, который принадлежит классу графов ВС к, где к - некоторая натуральная константа (глава 4);

3) каждая компонента порождает подграф, который принадлежит классу графов Бресх (глава 5).

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

Нетрудно увидеть, что древесных разложений графа по расстоянию даже с одноэлементным корневым множеством может быть несколько. Ясно, что всегда существует цепное разложение графа по расстоянию для заданного корня. Если для некоторого корневого множества цепное разложение совпадает с минимальным древесным разложением, то можно показать, что множество древесных разложений по расстоянию для заданного корня состоит только из одного элемента - цепного разложения по расстоянию. Хотя в общем случае при выборе древесного разложения даже при заданном корневом множестве может возникать довольно большой произвол. Поскольку мы применяем древесные разложения графов по расстоянию к задаче распознавания изоморфизма графов, нам важно устранить этот произвол. Можно показать, что для заданного корневого множества однозначно получается только цепное разложение графа по расстоянию и минимальное древесное разложение графа по расстоянию. Поэтому в дальнейшем мы будем рассматривать для заданного корня только случаи цепного разложения по расстоянию и минимального древесного разложения по расстоянию.

Введем обозначения для некоторых классов графов, которые встречаются в диссертации.

1) Block(Qd), где d - некоторое натуральное число. Связный граф G принадлежит классу Block(Q,i), если любой блок графа G порождает в G подграф из класса Qd (в обозначениях проблемы А: К — Qd, Т - класс всех деревьев, а «S = <Si).

2) Block(BCk), где к - некоторое натуральное число. Связный граф G принадлежит классу Block(BCk), если любой блок графа G порождает в G подграф из класса BCk (в обозначениях проблемы В: К = ВС к, Т - класс всех деревьев, а «S = <Si).

3) DQld, где d и I - фиксированные натуральные числа. Граф G принадлежит классу DQld, если он обладает минимальным древесным разложением по расстоянию, у которого корневое множество одноэлементно, каждая компонента имеет не более I сыновей и каждая компонента порождает в G подграф из класса

4) VBCk, где к - некоторое натуральное число. Граф G принадлежит классу VBCk, если он обладает цепным разложением по расстоянию, у которого корневое множество одноэлементно и каждая компонента порождает в G подграф из класса ВС к.

5) ТВС1к, где к и I - фиксированные натуральные числа. Граф G принадлежит классу 7"ВС1к, если он обладает минимальным древесным разложением по расстоянию, у которого корневое множество одноэлементно, каждая компонента имеет не более I сыновей и каждая компонента порождает в G подграф из класса ВСк

6) PathSpeci. Связный граф G принадлежит классу PathSpecy, если он обладает цепным разложением по расстоянию, у которого корневое множество одноэлементно и каждая компонента порождает в G подграф из класса Speci.

Перейдем к изложению результатов диссертации, но сначала скажем несколько слов о ее структуре. Материал, изложенный в диссертации разделен на 5 глав. Каждая из этих глав разделяется на параграфы. Утверждения (теоремы, леммы, предложения, следствия) нумеруются парами индексов, из которых первый указывает номер главы, а второй - номер утверждения данного типа в главе.

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

Во второй главе мы рассматриваем разложения графов на блоки и точки сочленения.

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

Определение. Связный граф G называется почти деревом с параметром к, если он обладает таким остовным деревом Т, что каждый блок графа G содержит не более чем к не принадлежащих дереву Т ребер.

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

В разделе 2.1.2 предлагается алгоритм с временной сложностью 0(п2) распознавания изоморфизма для класса деревьев Хусими, т. е. доказывается, что справедлива следующая

Теорема 2.4 Существует алгоритм с временной сложностью 0(п2) распознавания изоморфизма деревьев Хусими.

Основным результатом раздела 2.2.2 является

Теорема 2.8 Для каждого натурального в, существует полиномиальный алгоритм распознавания изоморфизма для класса графов В1оск{Я<1)

Заметим, что при доказательстве теоремы 2.8 использовались результаты Бабаи и Лакса, полученные при построении полиномиального алгоритма распознавания изоморфизма для класса связных графов т. е. связных графов, степени вершин которых не превосходят с? [18].

Основным результатом раздела 2.3.3 является

Теорема 2.10 Для каждого натурального к существует полиномиальный алгоритм распознавания изоморфизма для класса почти деревьев с параметром к.

Следующая теорема является основным результатом параграфа 2.3.

Теорема 2.14 Для каждого натурального к существует алгоритм распознавания изоморфизма для класса графов В1оск(ВСк) с временной сложностью 0(п$ • ((2А;)!)6 • (п+ №>)).

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

В главе 3 рассматриваются древесные ¿¿«¿-разложения. Фактически это минимальные древесные разложения, у которых каждая компонента порождает связный подграф. Заметим, что не все графы обладают разложениями такого рода. В качестве примера можно привести цикл длины 4.

Более точно, древесное разложение графа С? по расстоянию ({Х* : г € /}, Т = (/, г) называется древесным (¿^¿-разложением графа (7, если |ХГ| = 1 и для каждого подграфы С{Хг) графа <7 связные.

Пусть в, и I - фиксированные натуральные числа. Будем говорить, что связный граф С является графом из класса если он обладает древесным (¿^¿-разложением {{Хг: г € /}, Т = (/, .Р), г) таким, что для каждого г е I подграф принадлежит ^ив дереве Т каждая вершина имеет не более I сыновей. Такие древесные ¿^¿-разложения будем называть 0¿-древесными длз1-разложениями.

В параграфе 3.2 рассматривается класс графов и доказывается следующий результат.

Теорема 3.6 Для любых натуральных чисел й и I существует полиномиальный алгоритм распознавания изоморфизма для класса графов

В четвертой главе мы будем рассматривать классы цветных графов ТВСк и ТВС1к, где к л I - натуральные константы.

Цветной граф б? принадлежит классу РВСк, если он связный и для него существует цепное разложение Р =({^г : & € Т — (/, г) по расстоянию с выделенным корнем такое, что для каждого г € I цветной граф С(^) содержится в классе ВСк

Цветной граф С принадлежит классу ТВС1к, если он связный и для него существует минимальное древесное разложение И =({Хг : г е /}, Т = (/, г) по расстоянию с выделенным корнем такое, что для каждого г € I цветной граф содержится в классе ВСк и каждая вершина в Т имеет не более I сыновей. В дальнейшем такие древесные разложения по расстоянию с выделенным корнем будем называть ТгееСо1огк-разложениями. Заметим, что если цветной граф (7 е ТВС1к, то множество всех его 7>ееСо/ог£-разложений не обязательно одноэлементно.

Основной результат параграфа 4.3 - полиномиальный алгоритм распознавания изоморфизма для класса графов ТВСк.

Теорема 4.3 Для каждого натурального к существует алгоритм распознавания изоморфизма для класса графов ТВСк с временной сложностью 0{1\ • п8 • ((2А;)!)6 • (п +

2А02))

Основной результат параграфа 4.4 - полиномиальный алгоритм распознавания изоморфизма для класса графов ТВС1к. Более точно, справедлива следующая

Теорема 4.7 Для любых натуральных чисел к и I существует алгоритм распознавания изоморфизма для класса графов TBClk с временной сложностью О (II • пд • ((2А;)!)6 • (п + (2&)2)).

Заметим, что для фиксированных чисел к и I класс графов VBCk не обязательно содержится в классе ТВС1к, т.е. два последних результата не зависят один от другого.

В параграфе 5.3 мы рассматриваем класс графов PathSpec\. Будем говорить, что граф G принадлежит классу PathSpeci, если он связный и для него существует цепное разложение Р =({Xj : г G /}, Т — (/, F), г) по расстоянию с выделенным корнем такое, что для каждого г € I граф G(Xi) содержится в классе Spec\. В параграфе 5.3. доказывается

Теорема 5.5 Существует полиномиальный алгоритм распознавания изоморфизма для класса графов PathSpec\.

Хотелось бы отметить, что скорее всего для класса графов Speci справедливы результаты, аналогичные теоремам 2.14 и 4.7 для класса цветных графов ограниченной цветной кратности (имеется в виду полиномиальность алгоритмов, оценка сложности конечно будет другая). Пока этот вопрос специально автором диссертации не исследовался. Более того, вполне вероятно, что результаты, аналогичные теореме 5.5 и теоремам 2.14 и 4.7 для цветных графов, будут справедливы и для класса графов Speck.

Результаты диссертации докладывались на международном семинаре по теории групп (Екатеринбург, 2001), на международном семинаре "Дискретная математика и ее приложении "(Москва, 2004), на международной конференции "Дискретный анализ и исследование операции" (Новосибирск, 2004). Кроме того, автором было сделан ряд докладов на семинаре JI. Н. Шеврина "Алгебраические системы"в Уральском государственном университете.

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

Список литературы диссертационного исследования кандидат физико-математических наук Расин, Олег Вениаминович, 2004 год

1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матро-иды, алгоритмы.-Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001.

2. Ахо X., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.: Мир, 1979.

3. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев.-Новосибирск: ВО Наука. Сибирская издательская фирма, 1994.

4. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов.-М.: Наука. Гл. ред. физ.-мат. лит., 1990.

5. Земляченко В.Н., Корнеенко Н.М., Тышкевич Р.И. Проблема изоморфизма графов/ /Записки научных семинаров ЛОМИ. Мат. ин-т им. В.А.Стеклова, Ленингр. отд-ние. 1982. Т. 118. С. 83-158.

6. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп.-М.: Наука, 1972.

7. Хопкрофт Дж., Тарьян Р. Изоморфизм планарных графов. Кибернетический сборник нов. сер//1975. Вып. 12. С. 39-61.

8. Цветкович Д., Дуб М., Захс.Х. Спектры графов. Теория и применение.-Киев: Наук, думка, 1984.

9. Arnborg S., Proskurowski A., Canonical representations of partial 2- and 3-trees//Department of Computer and Information Science, Univercity of Oregon, 1998.

10. Babai L., Grigoryev D. Yu., and David M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity//In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, San Francisco, California. 1982. P. 310-324.

11. Babai L., Erdos P., Selkow S. M.,Random graph isomorphism//SIAM J. Comput. 1980. Vol 9(3). P. 628- 635.

12. Bodlaender H. L., de Fluiter В., Thilikos D. M., Yamazaki K., Isomorphism for graphs of bounded distance width//Algorithmica. 1999. Vol.24, P. 105-127.

13. Bodlaender H.L., Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees// Lecture Notes in Computer Science(Springer, Berlin). 1988. Vol.318. P.223-232.

14. Colbourn C. J., Booth K. S. Linear time automorphism algorithms for trees, interval graphs, and planar graphs//SIAM J. Comput. 1981. Vol.lO(Bl), P. 203-225.

15. Corneil D.G., Gotlieb C.C., An efficient algorithm for graph, isomorphism//Journal ACM. 1970. Vol 17. P.51-64.

16. Corneil D.G., Kirkpatrick D.G., A theoretical analysis of various heuristics for the graph, isomorphism//SIAM J. Comput. 1980. Vol 9(2). P.281- 297.

17. Fortin S., The Graph Isomorphism Problem//Department of Computer Science, The University of Alberta, Alberta, Canada. Technical report TR 96-20. 1996.

18. Hoffmann С. M. Group-Theoretics Algorithms and Graph Isomorphism-Berlin: Springer-Verlag, 1982. (Lecture Notes in Computer Science; Vol.136).

19. Leeuwen J. van, Graph Algorithms. Handbook of Theoretical Computer Science. Vol. A: Algorithms and Complexity Theories.-North Holland Publ. Сотр., Amsterdam, 1990.

20. McKay В., Practical graph isomorphism//Congressus Numerantum. 1981. P.45-87.

21. Weisfeiler В., On construction and identification of graphs// Lecture Notes in Mathematics. Vol.558. 1976.Работы автора по теме диссертации

22. Расин О. В. О проблеме изоморфизма графов//Тезисы докладов семинара "Международный семинар по теории групп посвященный 70-летию А. И. Старостина и 80-летию Н. Ф. Сесекина", Екатеринбург, Издательство Уральского университета, 2001. С. 194.

23. Расин О. В. Изоморфизмы цветных графов и древесные разложения по расстоянию //Материалы конференции "Дискретный анализ и исследование операций", Новосибирск, Издательство Института математики, 2004. С. 115.

24. Расин О. В. Цепные разложения по расстоянию и изоморфизмы графов//Дискретный анализ и исследование операций, 2004, серия 1, т.11, ВЗ, с.63-79.

25. Расин О. В. Алгоритм проверки изоморфизма деревьев Хусими //Известия Уральского гос. унверситета. Математика и механика, вып. б, 2004, В30, с. 127-137.

26. Расин О. В. Полиномиальный алгоритм распознавания изоморфизма почти деревьев //Известия Высш. учеб. заведений. Математика., 2004, В9, с.53-60.

27. Расин О. В. Изоморфизмы цветных графов и древесные разложения по расстоянию //Деп. в ВИНИТИ 25.08.2004, В1427-В2004.

28. Расин О. В. Изоморфизмы графов с простым спектром и древесные разложения по расстоянию //Деп. в ВИНИТИ 25.08.2004, В1428-В2004.

29. Расин О. В. Об изоморфизмах связных цветных графов //Деп. в ВИНИТИ 25.08.2004, В1429-В2004.

30. Расин О. В. Изоморфизмы графов и древесные ¿^¿-разложения //Деп. в ВИНИТИ 25.08.2004, В1430-В2004.