Полиномиальные алгоритмы распознавания изоморфизма в некоторых классах графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Расин, Олег Вениаминович
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Екатеринбург
МЕСТО ЗАЩИТЫ
|
||||
|
2004
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
РАСИН Олег Вениаминович
ПОЛИНОМИАЛЬНЫЕ АЛГОРИТМЫ РАСПОЗНАВАНИЯ ИЗОМОРФИЗМА В НЕКОТОРЫХ КЛАССАХ ГРАФОВ
(01.01.06 - математическая логика, алгебра и теория чисел)
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
Екатеринбург - 2005
Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета им. А М. Горького
Научный руководитель:
доктор физ.-мат. наук, профессор БАРАНСКИЙ В. А.
Официальные оппоненты:
доктор физ.-мат. наук, профессор РОЖКОВ А. В. кандидат физ.-мат. наук, доцент ПЕРМИНОВ Е. А.
Ведущая организация:
Уральский государственный педагогический университет
Защита состоится 25 января 2005 г. в 15.00 на заседании диссертационного совета Д.004006.03 по защите диссертаций на соискание ученой степени доктора наук при Институте математики и механики УрО РАН по адресу: г. Екатеринбург, ул С Ковалевской, 16.
С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.
Автореферат разослан
Ученый секретарь диссертационного совета доктор физ.-мат. наук
Общая характеристика работы
Актуальность темы. Диссертация посвящена изучению проблемы изоморфизма графов. Далее под графами мы понимаем конечные неориентированные графы без петель и кратных ребер. Под цветным графом мы понимаем граф, каждой вершине которого приписан некоторый цвет, обычно обозначав мый натуральным числом
На данный момент неизвестно никакого полиномиального алгоритма распознавания изоморфизма произвольных графов. Более того, неизвестно - существует ли такой алгоритм вообще. В диссертации рассматривается проблематика, связанная с построением полиномиальных алгоритмов распознавания изоморфизма для некоторых классов графов. Вопросы, имеющие отношение к проблеме существования полиномиального алгоритма распознавания изомор физма произвольных графов, в диссертации не рассматриваются.
Поскольку построить полиномиальный алгоритм распознавания изоморфизма для класса всех графов не удается, исследования в этой области разделяются на два направления-
1) построение так называемых эвристических алгоритмов распознавания изоморфизма графов;
2) построение полиномиальных алгоритмов распознавания изоморфизма для отдельных классов графов.
Результаты, представленные в диссертации имеют отношение ко второму направлению, но хотелось бы коротко рассказать об основных фактах, касающихся эвристических алгоритмов распознавания изоморфизма графов. Эти алгоритмы основаны на довольно естественной идее расклассифицировать вершины графов таким образом, чтобы избежать полного перебора Иными словами, если G] и Gi - графы, между которыми проверяется наличие изоморфизма, то мы разбиваем множества вершин графов на классы, приписывая
вершинам метки или, иными словами, цвета так, что изоморфизм может отображать вершину графа в вершину только если имеют одинаковый цвет. Для этого используются некоторые свойства вершин графов, инвариантные относительно изоморфизма. В качестве простейшего примера можно привести классификацию вершин по их степеням. Алгоритмы, основанные на идее разбиения множества вершин на классы, можно найти, например, в [7], (11], [12], |15], [16]. Необходимо отметить, что хотя в большинстве случаев они и многие подобные им алгоритмы, как правило, достаточно эффективны, время работы в худшем случае у них экспоненциально. Попутно заметим, что алгоритм в статье [15] являлся базовым при написании ее автором программы которая для пары произвольных графов проверяет являются ли они изоморфными. Многие исследователи (см., в частности, [13]) полагают, что Nauty является на данное время наиболее эффективным по быстродействию программным средством распознавания изоморфизма произвольных графов.
Прежде чем перейти к изложениию результатов диссертации, укажем основные классы графов, для которых различными авторами построены полиномиальные алгоритмы распознавания изоморфизма.
К таким классам графов относятся корневые деревья [2], деревья [3], связные графы, степени вершин которых ограничены натуральной константой [14], графы интервалов 110], графы ограниченной древесной ширины |9], планарные
1рафы |5| графы род которых ограничен натуральной констаной [14| графы с ограниченной древесной шириной но расстоянию |8j цветные графы крат ность каждою цвета в которых ограничена некоторой константой |14] и графы у которых крааности собственных чисел ограничены некоторой константой [6] Хотя алгоритмы в приведенном списке решают частные случаи одной и той же задачи приемы которые в них используются очень сильно различаются Часть из них использует не только комбинаторные методы такие как поиск в графе различные сортировки итп но также методы теории групп подстано вок и некоторые матричные алгоритмы
Пусть d некоторая натуральная константа Обозначим через Qd класс связ ных графов степени вершин которых не превосходят d
Введем обозначение ВСк для класса всех цветных графов, цветная крат ность которых не превосходит натурального числа к, те для каждого цветного класса С, графа G € В С к имеем |С,| < к
Далее для каждого к € N через Spec* будем обозначать класс графов, в которых кратность каждого собственного значения не превосходит
Пусть 1С - произвольный класс графов, для которого известен полиномиаль ный алгоритм распознавания изоморфизма, Т - некоторый класс деревьев, а S - некоторый тип "древовидных" разложений графов на компоненты В данной работе мы будем рассматривать следующие типы "древовидных" разложений графа представление графа в виде дерева блоков и точек сочленения [1] или |4|, древесные разложения графов по расстоянию |8|, минимальные древесные разложения графов по расстоянию [8), цепные разложения графов по расстоя нию и т п
Будем юворить, что граф G принадлежит классу TSK если он облада ет разложением типа S на компоненты, принадлежащие классу К, а соответ ствующее дерево компонент принадлежит классу Т Если класс Т совпадает с классом всех деревьев, то в этом случае класс графов TSK. буцем обозначать просто через
Диссертация посвящена рассмотрению следующих двух проблем Проблема А Пусть К. - произвольный класс графов, для которого из вестен полиномиальный алгоритм распознавания изоморфизма, Т некото рый класс деревьев, а S - некоторый тип "древовидных"разложений графов на компоненты Существует ли полиномиальный алгоритм распознавания изоморфизма для класса графов TSK $
Проблема В. Пусть К. - произвольный класс цветных графов, для кото рого известен полиномиальный алгоритм распознавания изоморфизма Т некоторый класс деревьев, а S некоторый тип "древовидных'разложений графов на компоненты Существует ли полиномиальный алгоритм распозна вания изоморфизма для класса цветных графов TSK.?
Отметим, что проблема А фактически уже рассматривалась в работе Бод-лендера |9] для случая, когда в качестве Т фигурирует класс всех деревьев в качество древесные разложения графов, а в качестве класс всех графов, число вершин в которых ограничено некоторой натуральной константой
Пусть G некоторый граф, а и и г) его вершины Длина кратчайшего маршрута из вершины в вершину обозначается через и называется
расстоянием между вершинами Нам понадобится следующее
Определение Пусть С = (V Е) связный граф Древесным розложе нием графи О по расстоянию называется тройка ((X, г 6 1},Т = 1)
такая, что
1) и ^ ~ V и Х,ПХ, = 0 для любых г ф ] где м е Л ■6/
2) Т является корневым деревом с корнем в вершине г 6 I,
3) для каждого и € К если у € А,, то ¿с(Хт,у) = г),
4) для каждого ребра {и, ш} € Е существуют такие 1,] € /, что г; 6 Х„ ■и) € Х3 и либо г = либо {г,6 ^
Если дерево Т = (/, Р) является простой цепью, то такое древесное разло жение связного графа по расстоянию будем называть цепным разложением графа по расстоянию
Поскольку древесное разложение по расстоянию определяется только для связных графов, говоря, что граф С? обладает древесным разложением по рас стоянию, мы подразумеваем, что в - связный граф
Множества Х„ где г £ I, называются компонентами древесного разложения по расстоянию Множество ХТ мы будем называть корневым множеством или корнем древесного разложения по расстоянию
Будем говорить, что компонента X, является сыном компоненты Х3, если в корневом дереве Т вершина г является сыном вершины ]
Определение Пусть £> = ({А, г 6 1},Т = (1,Р),г) - древесное разложение графа в по расстоянию Для каящой компоненты древесного разло жения X, определим множество X,) = и Х}, где Т, - максимальное
корневое поддерево дерева с корнем в вершине
Определение Пусть £> = ({.У, г € /} Т = (/, .Р) г) - древесное разложение графа О по расстоянию И называется минимальным, если для каждого г а I порожденный подграф <3(К(£>, X,)) графа в является связным
Шириной древесного разложения по расстоянию называется количество вершин в максимальной по мощности компоненте Древесной шириной графа по расстоянию называется наименьшая ширина древесных разложений по расстоянию
Введем следующие обозначения для типов "древовидных" разложений, которые мы будем рассматривать в диссертации
1) разложение графов на блоки и точки сочленения
2) - ценные разложения графов по расстоянию, корневые множества которых одноэлементны (заметим, что в этом случае естественно считать, что соответствующий класс совпадает с классом цепей),
3) 5з - минимальные древесные разложения графов по расстоянию, корневые множества которых одноэлементны
В диссертации изучаются случаи, когда на компоненты "древовидных"разло жений накладываются условия вида
1) каждая компонента пороящает подграф, который принадлежит классу графов некоторая натуральная константа (глава 3),
2) каждая компонента порождает подграф, который принадлежит классу графов ВС^, где к - некоторая натуральная константа (глава 4),
3) каждая компонента порождает подграф который принадлежит классу
графоз Speci (глава 5)
То, что нами рассматриваются только классы 1рафов алгоритмы распо знавания изоморфизма которых были получены теоретике групповыми мсто дами не случайно В частности, это обосновывается следующим Пусть 1С класс графов в котором задача распознавания изоморфизма решается за по линомиальнос время чисто комбинаторными методами С помощью небольшой модернизации соответствующего алгоритма обычно удается решить за полино миальное время и задачу распознавания изоморфизма в классе TS\ К даже в случае, когда класс Т совпадает с классом всех деревьев Кроме того отметим, что для некоторых классов К. имеет место равенство К, = S\K (например, если 1С - класс планарных графов)
Для разложений типов 52 и S3 в случае, е с лйкл а с с графов, в котором задача распознавания изоморфизма решается за полиномиальное время чисто комбинаторными методами, ситуация не столь проста и скорее всего тоже требует применения теоретико-групповых методов
По поводу разложений типов S2 и Si необходимо заметить следующее Они и аналогичные им разложения, как уже было отмечено, рассматривались в работе Там были построены алгоритмы распознавания изоморфизма для класса графов, древесная ширина по расстоянию которых не превосходит некоторой наперед заданной константы к (или в наших обозначениях для класса S3IC, где 1С совпадает с классом графов, количество вершин в которых не бо лее к) Заметим, что при этом, вообще говоря, не требовалось, чтобы корневое множество было одноэлементно Достаточно было, чтобы оно принадлежало этому классу
Цель работы. Работа посвящена изучению проблем А и В для случая важнейших типов "древовидных" разложений графов и для основных клас сов графов, для которых известны полиномиальные алгоритмы распознавания изоморфизма
Основной метод исследования. В диссертации используются методы дискретной оптимизации, алгоритмы и теоретические результаты из теории групп подстановок
Научная новизна. В работе получены следующие новые результаты Построены полиномиальные алгоритмы, распознающие изоморфизм в сле дующих классах графов
1) Block(Q1дс (I - некоторое натуральное число Связный граф G принадлежит классу Block{Gd), если любой блок графа G порождает в G подграф из класса Qi (в обозначениях проблемы А К — Т - класс всех деревьев, а S = <!>:) Показано, что алгоритм распознавания изоморфизма для таких клас сов графов при подходящем значении d распознает также за полиномиальное время изоморфизм почти деревьев с параметром к, где к фиксированная натуральная константа
2) Block(BCic), гдо к - некоторое натуральное число Связный граф G при надлежит классу В!оск(ВСк), если любой блок графа G порождает в G под граф из класса (в обозначениях проблемы класс всех деревьев, a S = S\)
3) DQld, где d и I - фиксированные натуральные числа Графйринадле жит классу если он обладает минимальным древесным разложением по расстоянию, у которого корневое множество одноэлементно, каждая компонен
та имеет не более I сыновей и каждая компонента порождает в G подграф из класса Qd
4) "PBCk где к некоторое натуральное число Граф G принадлежит классу VBCi если он обладает цепным разложением по расстоянию, у которого кор новое множество одноэлементно и каждая компонента порождает в G подграф из класса BCV
5) ТВС'К, где к и I фиксированные натуральные числа Граф G принадлежит классу ТВС[, если он обладает минимальным древесным разложением по расстоянию, у которого корневое множество одноэлементно, каждая комно нента имеет не более I сыновей и каждая компонента порождает в G подграф из класса ВС*
6) PathSpeci Связный граф (принадлежит к л ай^^е^с ли он обладает цепным разложением по расстоянию, у которого корневое множество одноэлементно и каждая компонента порождает в G подграф из класса Spec\
Теоретическая и практическая ценность. Результаты диссертации но сят теоретический характер
Апробация результатов работы. Результаты диссертации докладыва лись на международном семинаре по теории групп (Екатеринбург, 2001), на международном семинаре "Дискретная математика и ее приложении" (Москва, 2004), на международной конференции "Дискретный анализ и исследование операции" (Новосибирск, 2004) Кроме того, автором был сделан ряд докладов на семинаре Л Н Шсврина "Алгебраические системы" в Уральском государ ственном университете
Публикации. Основные результаты диссертации опубликованы в девяти работах список, которых приведен в конце автореферата Результаты публико вались в следующих изданиях "Известия УрГУ", "Известия ВУЗов Математика" "Дискретный анализ и исследование операции", в материалах конференций "Международный семинар по теории групп посвященный 70 легию А И Старостина и 80 лстию Н Ф Сесекина" (Екатеринбург, 2001) и "Дискретный анализ и исследование операции" (Новосибирск, 2004) Четыре публикации де понированы в ВИНИТИ
Структура и объем диссертации. Дисертация, состоит из введения и 5 глав Каждая из глав разделяется на параграфы Утверждения(тсорсмы, леммы, предложения, следствия) нумеруются парами индексов, из которых первый указывает номер главы, а второй - номер утверждения данного типа в главе Объем диссертации 93 страница машинописного текста Диссертация содержит 21 библиографическую ссылку
Содержание диссертации Первая глава диссертации носит всиомога тельный характер В ней вводятся некоторые понятия и приводятся утверждения, на которые опираются доказательства основных результатов диссертации Во второй главе мы рассматриваем разложения графов на блоки и точки сочленения
Эти разложения при ограничениях на блоки, о которых мы говорили выше, могут быть использованы при построении полиномиального алгоритма распознавания изоморфизма в классе почти деревьев с параметром неко торая натуральная константа
Определение Связный граф G называется почти деревом с парамет
ром к если он обладает таким остовным деревом Т, что каждый ШОК графа О содержит не более чем к не принадлежащих дереву Т ребер
Почти деревья с параметром 1 называют деревьями Хусими Легко видеть что каждый блок дерева Хусими является либо ребром, либо циклом
В разделе 2 12 предлатстся полиномиальный алгоритм с временной сложностью 0(п2) распознавания изоморфизма для к пасса деревьев Хусими, т с доказывается что справедлива следующая
Теорема 2.4 |20] Существует алгоритм с временной сложностью 0(п2) распознавания изоморфизма деревьев Хусими Основным результатом раздела 2 2 2 является
Теорема 2 8 [21| Для каждого натурального с1 существует полиномиалъ ный алгоритм распознавания изоморфизма для класса графов В1оск(@¡¡)
Заметим, что при доказательстве теоремы 2 8 использовались результаты Бабаи и Лакса, полученные при построении полиномиального алгоритма распознавания изоморфизма для класса графов т е связных графов, степени вершин которых не превосходят <1
Основным результатом раздела 2 3 3 является
Теорема 2.10 [21] Для каждого натурального к существует полиноми альный алгоритм распознавания изоморфизма для класса почти деревьев г параметром к
Отметим, что результаты из статьи опубликованы в виде тезисов Следующая теорема является основным результатом параграфа 2 3 Теорема 2.14 [24] Для каждого натурального к существует алгоритм распознаванияизоморфизмадляклассаграфов В1оск(ВСк) с временной слож ностьюО(п8 ((2й)')6 (п + (2/к)2))
В главе 3 рассматриваются древесные ¿^-разложения Фактически это минимальные древесные разложения, у которых каждая компонент порождает связный подграф Заметим, что не все графы обладают разложениями такого рода В качестве примера можно привести цикл длины 4
Более точно, древесное разложение графа в но расстоянию ({X, г £ /}, Т = (/, г) называется древесным (^¿-разложением графа С, если |ХГ| = 1 и для каждого г 6 / подграфы в(Х,) графа в связные
Пусть ¿я1- фиксированные натуральные числа Будем говорить, что связный граф С? является графом из класса если он обладает древесным йЫ-разложением таким, что для каждого подграф
принадлежит ^ и в дереве Т каждая вершина имеет не более I сыновей В параграфе 3 2 рассматривается класс графов и доказывается Теорема 3.6 |25| Для любых натуральных в, и I существует полиноми альный алгоритм распознавания изоморфизма для класса графов
Заметим, что этот результат обобщает результаты автора, опубликованные в статье
В четвертой главе мы будем рассматривать классы цветных графов ТВСь. и ТВС'к, где к и I - натуральные константы
Цветной граф <3 принадлежит классу ТВСь, если он связный и для него существует цепное разложение Р =({.Х, г € /}, Т = (1,Р), т) по расстоянию с выделенным корнем такое, что для каждого г € I цветной граф в(Х,) содержится в классе
Цвпнои 1раф С принадлежит классу ТВС\. ргли он связный п дня нею с)щссгвусг минимальное дрсвссное разложение -О =({Х, г 6 /} Т — (I Р) ч) по расстоянию с выделенным корнем такое что для каждою 4 Ь I цветной граф С(Х,) содержится в к л а ОЮе и каждая вершина в Т имеет не более I сыновей
Основной результат параграфа 4 3 - полиномиальный алгоритм распозна вания изоморфизма для класса графов "РВСь [18| и [22]
Теорема 4.3 Для каждого натурального к существует алгоритм рас познавания изоморфизма для класса графов "РВС% с временной сложностью
0{п8 ((2кУУ (п + {2кУ))
Основной результат параграфа 4 4- полиномиальный алгоритм распознавания изоморфизма для класса графов ТВС^ Более точно справедлива следующая
Теорема 4.7 [22| Для любых натуральных к и I существуеталгоритмрас-познавания изоморфизма для класса графов с временной сложностью
0(/' п3 ((2кУ)6 (га + (2&)2))
Заметим, что для фиксированных чисел к и I класс графов ТВСь не обязательно содержится в классе ТВС\., т е два последних результата не зависят один от другого
В параграфе 5 3 мы рассматриваем класс графов РаЛвреС] Будем говорить, что граф С? принадлежит классу РаМгвреС}, если он связный и для него существует ценное разложение Р I 6 /}, Т — (/, г) по расстоянию
с выделенным корнем такое, чао для каждого содержится в
классе ¿>рес1 В параграфе 5 3 доказывается
Теорема 5.5 |25) Существует полиномиальный алгоритм распознавания изоморфизма для класса графов Р<йк8рес\
Автор выражает глубокую признательность своему научному руководите лю профессору В А Баранскому за постоянное внимание к работе и ценные замечания, способствовать ее улучшению
Литература
1 Асанов М О , Баранский В А , Расин В В Дискретная математика графы, матроиды, алгоритмы -Ижевск НИЦ "Регулярная и хаотическая динамика", 2001
2 Ахо X , Хопкрофт Дж , Ульман Дж Построение и анализ вычислительных алгоритмов -М Мир, 1979
3 Евстигнеев В А , Касьянов В Н Теория графов алгоритмы обработки деревьев -Новосибирск ВО Наука Сибирская издательская фирма, 1994
4 Емсличев В А , Мельников О И , Сарванов В И , Тышкевич Р И Лекции по теории графов-М Наука Гл ред физ-мат лит, 1990
5 Хонкрофт Дж , Тарьян Р Изоморфизм планарных графов// Кибернети
ческий сборник нов сер 1975, Вып 12 С 39-61
6 Babai L GngoiycvD Yu , and David M Mount Isomoiphism of graphs with bounded cigen\aluc multiplicity// In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing San Francisco, California 1982 P 310 324
7 Babai L , Eidos P , Sclkow S M Random graph isomorphism// SIAM J Comput 1980 V 9, B3 P 628- 635
8 Bodlacnder H L , de Fluiter В , Thilikos D M Yama/aki К , Isomorphism for graphs of bounded distance width// Algonthmica, 1999, V 24 P 105 127
9 Bodlaender H L Polynomial algorithms for graph isomorphism and chromatic index on partial /c-trees // Lecture Notes in Computer Science(Spnnger, Berlin), 1988, V 318 P 223-232
10 Colbourn С J , Booth К S Linear time automorphism algorithms for trees, interval graphs, and planar graphs// SIAM J Comput, 1981, V 10, Bl P 203-225
11 Cornell D G , Gotheb С С , An efficient algorithm for graph isomorphism// Journal ACM, 1970, V 17 P 51-64
12 Cornell D G , Kirkpatnck D G , A theoretical analysis of various heuristics for the graph isomorphism// SIAM J Comput, 1980, V 9, B2 P 281- 297
13 Fortin S , I he Graph Isomorphism Problem // Department of Computer Science The University of Alberta, Alberta, Canada, 1996 Technical report TR96 20
14 Hoffmann С М Group-Theoretics Algorithms and Graph Isomorphism Berlin Springer-Vcrlag, 1982 (Lecture Notes in Computer Science, Vol 136)
15 McKay В , Practical graph isomorphism// Congressus Numerantum, 1981 P 45-87
16 Weisfeiler В , On construction and identification of graphs Lecture Notes in Mathematics Vol 558 1976
Работы автора по теме диссертации
17 Расин ОВО проблеме изоморфизма графов//Тезисы докладов семинара "Международный семинар по теории групп посвященный 70 летию А И Старостина и 80-летию Н Ф Сссекина" Екатеринбург, Издательство Уральского университета, 2001 С 194
18 Расин О В Изоморфизмы цветных графов и древесные разложения но расстоянию //Материалы конференции "Дискретный анализ и исследова ние операций", Новосибирск, Издательство Института математики, 2004 С 115
19 Расин О В Ценныс разложения по расстоянию и изоморфизмы ipa фов//Дискретный диализ и исследование операции 2004, серия 1, т 11 ВЗ с 63- /9
20 Расин О В Алгоритм проверки изоморфизма деревьев Хусими //Известия Уральского гос унверситгта Математика и механика, вып 6 2004 ВЗО, с 127-137
21 Расин О В Полиномиальный алгоритм распознавания изоморфизма почти деревьев //Известия Высш учеб заведений Математика, 2004, В9, с 53-60
22 Расин О В Изоморфизмы цветных графов и древесные разложения по расстоянию //Дсп в ВИНИТИ 25 08 2004, В1427-В2004
23 Расин О В Изоморфизмы графов с простым спектром и древесные разложения по расстоянию //Деп в ВИНИТИ 25 08 2004, В1428-В2004
24 Расин О В Об изоморфизмах связных цветных графов //Деп в ВИНИТИ 25 08 2004, В1429-В2004
25 Расин О В Изоморфизмы графов и древесные dibt разложения //Деп в ВИНИТИ 25 08 2004, В1430 В2004
РШ-МоЗ
Подписано в печать \7.42. 2004 г. Формат 60x84/16. Бумага офсетная. Усл. исч. л />#Гираж 100 экз. Заказ №
Отпечатано в ИПЦ "Издательство УрГУ" г. Екатеринбург, ул. Тургенева, 4
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. Н. Шеврина "Алгебраические системы"в Уральском государственном университете.
Автор выражает глубокую признательность своему научному руководителю профессору В. А. Баранскому за постоянное внимание к работе и ценные замечания, способ-ствовашие ее улучшению.
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.
