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

• Автор: Расин, Олег Вениаминович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Екатеринбург
• Количество страниц: 93 с. : ил.

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. Алгоритм распознавания изоморфизма для класса цветных графов ТВС‘к
5. Изоморфизмы графов с простым спектром и цепные разложения по расстоянию
5.1. Некоторые факты и обозначения
5.2. Изоморфизмы графов из класса 5ресх
5.3. Изоморфизмы графов в классе Ра(Л5рес1

Данная диссертация посвящена изучению проблемы изоморфизма графов. Здесь и далее под графами мы понимаем конечные неориентированные графы без петель и кратных ребер. Для графов мы будем пользоваться системой обозначений из книги [1]. Множество вершин графа в будем обозначать через УС или У(С), а множество ребер - через ЕС или Е(С). Обычно через п будем обозначать количество вершин (или порядок) графа, если не оговорено противное, а через тп - число его ребер. Проблема изоморфизма графов состоит в следующем: существует ли полиномиальный алгоритм, который для каждой пары графов распознает изоморфны они или нет.
На данный момент неизвестно никакого полиномиального алгоритма распознавания изоморфизма произвольных графов. Более того, неизвестно - существует ли такой алгоритм вообще. В диссертации рассматривается проблематика, связанная с построением полиномиальных алгоритмов распознавания изоморфизма для некоторых классов графов. Вопросы, имеющие отношение к проблеме существования полиномиального алгоритма распознавания изоморфизма произвольных графов, в диссертации не рассматриваются. Однако, хотелось бы коротко рассказать, какое место занимает задача распознавания изоморфизма графов в иерархии теории сложности.
Доказано, что задача распознавания изоморфизма графов лежит в классе АГР, но неизвестно является ли она УР-полной. Установлено, что задача распознавания изоморфизма двух графов полиномиально эквивалентна задаче поиска числа изоморфизмов между двумя графами [18]. Так как задачи распознавания и перечисления для всех известных УР-полных задач не являются полиномиально эквивалентными, существует гипотеза, что задача распознавания изоморфизма графов не является УР-полной [5], [17].
В силу этого возможно, что при Р ф УР, задача распознавания изоморфизма графов и все задачи, полиномиально эквивалентные ей, образуют отдельный класс так называемых изоморфно полных задач. Примеры таких задач можно найти, в частности, в [18] и [19].
Вернемся к обсуждению алгоритмических аспектов задачи распознавания изоморфизма графов.
Из известных алгоритмов распознавания изоморфизма для класса всех графов наименьшую временную сложность имеет алгоритм Земляченко [5]. Бабаи и Лаксом было показано, что временная сложность этого алгоритма 0(еп^+0^) [19], где п - количество вершин графов.
Поскольку, как уже говорилось выше, построить полиномиальный алгоритм распознавания изоморфизма для класса всех графов не удается, исследования в этой области разделяются на два направления:
1) построение так называемых эвристических алгоритмов распознавания изоморфизма графов;
2) построение полиномиальных алгоритмов распознавания изоморфизма для отдельных классов графов.
Результаты, представленные в диссертации имеют отношение ко второму направлению, но хотелось бы коротко рассказать об основных фактах, касающихся эвристических алгоритмов распознавания изоморфизма графов. Эти алгоритмы основаны на довольно естественной идее расклассифицировать вершины графов таким образом, чтобы избежать полного перебора. Иными словами, если С и <32 - графы, между которыми проверяется наличие изоморфизма, то мы разбиваем множества вершин графов С и
С2 на классы, приписывая вершинам метки или, иными словами, цвета так, что изоморфизм может отображать вершину и графа С] в вершину V графа С2 только если и и V имеют одинаковый цвет. Для этого используются некоторые свойства вершин графов, инвариантные относительно изоморфизма. В качестве простейшего примера можно привести классификацию вершин по их степеням. Алгоритмы, основанные на идее разбиения множества вершин на классы, можно найти, например, в [15], [16], [20], [21]. Необходимо отметить, что хотя в большинстве случаев они и многие подобные им алгоритмы, как правило, достаточно эффективны, время работы в худшем случае у них экспоненциально. Попутно заметим, что алгоритм в статье [20] являлся базовым при написании ее автором программы Ыа^у, которая для пары произвольных графов проверяет являются ли они изоморфными. Многие исследователи (см., в частности, [17]) полагают, что ИаЫу является на данное время наиболее эффективным по быстродействию программным средством распознавания изоморфизма произвольных графов.
В связи с этим представляет интерес задача распознавания изоморфизма цветных графов. Следующее понятие понадобится нам в дальнейшем при изложении результатов диссертации.
Определение. Цветным графом называется пара (С,/), где Ц - обыкновенный граф, а / - функция из множества вершин графа (7 в некоторый начальный отрезок натурального ряда (1 Для вершины V графа (7 число }{и) называется цветом вершины V. Число вершин цвета г называется кратностью цвета г.
Цветной граф (С,/) будем обозначать также через С/. Множество вершин цвета г в цветном графе О/ будем обозначать через С; и называть его г-м цветным классом, а множество всех цветных классов С,... ,Ск обозначим через С и будем называть его разбиением на цветные классы множества вершин цветного графа (7/.
Понятно, что цвета в цветном графе (Ц, /) можно задавать не только с помощью цветной функции /. Очень часто мы будем брать граф б, а потом указывать разбиение С = {С С)} множества его вершин на цветные классы.
Два цветных графа изоморфны, если для них имеется изоморфизм, сохраняющий цвета вершин. Такой изоморфизм мы будем называть цветным изоморфизмом. В дальнейшем под изоморфизмами цветных графов мы всегда будем понимать их цветные изоморфизмы.
Известно, что задача распознавания изоморфизма в классе всех цветных графов полиномиально эквивалентна задаче распознавания изоморфизма графов [18], иными словами она изоморфно полна.
Прежде чем перейти к изложениию результатов диссертации, укажем основные классы графов, для которых различными авторами построены полиномиальные алгоритмы распознавания изоморфизма, и введем обозначения для некоторых из них.
К таким классам графов относятся корневые деревья [2], деревья [3], связные графы, степени вершин которых ограничены натуральной константой [18], графы интервалов [14], графы ограниченной древесной ширины [13], планарные графы [7], графы, род которых ограничен натуральной констаной [18], графы с ограниченной древесной шириной по расстоянию [12], цветные графы, кратность каждого цвета в которых ограничена некоторой константой [18], и графы, у которых кратности собственных чисел ограничены некоторой константой [10].
Хотя алгоритмы в приведенном списке решают частные случаи одной и той же задачи, приемы, которые в них используются, очень сильно различаются. Часть из них использует не только комбинаторные методы, такие как поиск в графе, различные
вид древесных разложений по расстоянию, автор считает уместным привести некоторые обозначения снова.
Пусть С - связный граф, для которого существует древесное сйяі-разложение -0=({Х*:ге/},Г=(/,Пг).
Если вершины і Є I и j Є I смежны в дереве Т, то будем называть компоненты X, и Xі древесного (йаі-разложения В смежными. В случае когда вершина Є / является сыном вершины г Є I в дереве Т, то будем говорить, что компонента древесного разложения X] является сыном компоненты древесного разложения Хі, а компонента древесного разложения Хі является отцом компоненты древесного разложения Ху Компоненту Х{, где і Є I, будем называть листом древесного сй.?4-разложения В, если г - лист в дереве Т. В случае, когда і не является листом в дереве Т, компоненту Хі будем называть внутренней компонентой древесного <йзХ-разложения В.
Если нам дан произвольный связный граф (Зим - некоторая его вершина, то мы можем определить за полиномиальное время существует ли древесное еКаі-разложение графа Є с корнем в вершине и и, если такое разложение существует, можем найти его за полиномиальное время. Имеется в виду алгоритм, который упоминается в предложении

Кроме того, нам понадобится обобщение определения [и, г]-изоморфизма графов.
Определение. Пусть (щ, и2,... м5) - упорядоченный набор различных вершин графа (7, а (щ, гіг, • •. г>„) - упорядоченный набор различных вершин графа Н. Графы биД называются [(«і, и2, • • • и$), (щ, '«2, • • • иа)]-изоморфными, если существует изоморфизм графа Є на граф Н, отображающий для каждого г Є {1 а} вершину щ на вершину в*.
Будем говорить, что древесные Дгь^-разложения X)® и ВЦ графов (7 и Н с корнями в вершинах «и#, соответственно, изоморфны, если [и, г>]-изоморфны графы Є и Н.
Очевидно, что если и и V - вершины графа С, то множество всех {и, п}-автоморфизмов графа О является группой. Это множество является стабилизатором множества {и, у} в группе автоморфизмов графа (7.
Пусть даны два связных графа Є и Н, а и - некоторая вершина графа С. Для каждой вершины V графа Н через А„ обозначим группу {и, г'}-автоморфизмов графа <7 и Я. Очевидно, что если графы Си Я являются [и, н]-изоморфными, то любой [и,и]-изоморфизм этих графов совпадает с ограничением некоторого элемента группы Ау на множество вершин графа (7. В дальнейшем, допуская вольность, в подобных случаях будем говорить, что группа А„ содержит все [и,и]-изоморфизмы графа й на граф Я. Мы будем говорить, что мы можем найти все {и, ь]-изоморфизмы графа й на граф Я, если мы можем найти за полиномиальное время порождающее множество полиномиальной мощности группы Ау.
Очевидно, что если графы (7 и Я изоморфны, то в группах {Ау : и Є V(Я)} содержатся все изоморфизмы графа Є на граф Я. Будем говорить, что мы можем найти все изоморфизмы графа О на граф Я, если известен алгоритм, строящий за полиномиальное время порождающее множество полиномиальной мощности группы Ау, для каждого и Є К(Я).
Введенная только что терминология будет весьма активно использоваться при описании приведенного ниже алгоритма.
Пусть дик- натуральные константы, а (7 и Я - графы из класса ВС)кЛ. Зафиксируем некоторую вершину и графа (7 такую, что существует ^-древесное Фві-разложение Я® графа С. Ясно, что графы (7 и Я будут изоморфны тогда и только тогда, когда найдется