WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«Содержание 1 Проблема изоморфизма и родственные ей проблемы 2 1.1 Проблема изоморфизма простых графов........................ 2 1.2 ...»

Проблема изоморфизма графов:

Алгоритмические аспекты

(записки к лекциям)

И.Н. Пономаренко

Санкт-Петербургское отделение

Mатематического института им. В.А.Стеклова

октябрь-декабрь, 2010

Содержание

1 Проблема изоморфизма и родственные ей проблемы 2

1.1 Проблема изоморфизма простых графов........................ 2

1.2 Изоморфно полные классы графов........................... 4

1.3 Проблема изоморфизма для категорий......................... 8

1.4 Проблемы, эквивалентные проблеме изоморфизма.................. 12 2 Комбинаторные алгоритмы проверки изоморфизма 17

2.1 Построение канонической формы почти всех графов................. 17

2.2 Распознавание изоморфизма деревьев......................... 19

2.3 Распознавание изоморфизма групп........................... 22 3 Алгоритмы для работы с группами перестановок 25

3.1 Базовые алгоритмы для групп перестановок..................... 25

3.2 Алгоритм Симса...................................... 28

3.3 Вычисление cтабилизатора множества......................... 32 4 Групповые алгоритмы проверки изоморфизма 36

4.1 Распознавание изоморфизма графов ограниченной степени............. 36



4.2 Графы с ограниченными цветными валентностями и трюк Земляченко...... 39

4.3 Дальнейшие результаты по проблеме изоморфизма................. 42 5 Проблема изоморфизма и когерентные конфигурации 45

5.1 Алгоритм Вейсфейлера-Лемана и когерентные конфигурации........... 45

5.2 Алгебраические леса................................... 50

5.3 Неэффективность комбинаторных алгоритмов.................... 53 1 Проблема изоморфизма и родственные ей проблемы

1.1 Проблема изоморфизма простых графов. Пусть – конечное множество и – подмножество множества его двухэлементных подмножеств. Тогда пара = (, ) называется (простым) графом c множеством вершин и множеством ребер. Будем говорить, что вершины

–  –  –

где и 1 – образы вершин 1 и 1 относительно биекции. Последняя называется изоморфизмом графа 1 на граф 2. Множество всех таких изоморфизмов обозначается через Iso(1, 2 ). Таким образом,

–  –  –

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

Граф = (, ), где и = {(, ) :, }, называется подграфом графа, индуцированным множеством.

Каждый изоморфизм графа = (, ) является перестановкой множества и называется автоморфизмом этого графа. Множество всех его автоморфизмов обозначается через Aut(). Таким образом, Aut() = Iso(, ). (2) Если и – автоморфизмы графа, то их композиция, которая определяется формулой = ( ),, также является автоморфизмом этого графа. Легко видеть, что множество Aut() содержит тождественную перестановку id :, и перестановку 1, обратную к произвольной перестановке Aut() (по определению 1 = id ). Таким образом, множество Aut() является группой; она называется группой автоморфизмов графа. Эта группа

– подгруппа симметрической группы Sym( ), состоящей из всех перестановок множества,

Aut() Sym( ).

Отметим, что если – полный или пустой граф, то Aut() = Sym( ) и граф имеет !

автоморфизмов. Оставляем в качестве упражнения доказать, что | Aut()| = 2, если – цепь длины 2, и | Aut()| = 2, если – цикл длины.

Мы предполагаем известными понятия алгоритма и его сложности. Алгоритмические проблемы, рассматриваемые ниже, описываются входом, обычно состоящим из нескольких графов (или перестановок) того или иного типа, и выходом, который описывается предикатом (для проблем распознавания) или несколькими графами или перестановками. Для заданного входа алгоритм совершает некоторое количество элементарных операций и завершает работу, создавая выход предписанного типа. Количество элементарных операций в худшем случае именуется далее сложностью алгоритма. Вход и выход имеют длину которая, грубо говоря, равна размеру памяти, в которой он может быть записан. Поэтому сложность алгоритма есть функция длины входа. Алгоритм имеет полиномиальную сложность (работает полиномиальное время), если существует полином () такой, что сложность алгоритма на входе длины не превосходит (); в этом случае также говорят, что сложность алгоритма есть (1).

Граф = (, ) на входе алгоритма может быть задан с помощью списка рёбер и тогда вклад в длину входа равен длине этого списка 2|| = (2 ), где = | |. Другой способ состоит в задании матрицы смежности = () графа, т.е.

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

{ 1, если (, ), = 0, если (, ).

В этом случае вклад в длину входа равен 2. Произвольная биекция : 1 2 задаётся множеством пар (, ); её вклад в длину входа считается равным 2|1 |.

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

ISO(1, 2 ): для графов 1 и 2 определить верно ли, что 1 2.

= Не умаляя общности мы всегда будем предполагать, что оба графа имеют одинаковое число вершин. Поэтому легко проверить, принадлежит ли данная биекции : 1 2 множеству Iso(1, 2 ): проверка условия (1) эквивалентна проверке 2 равенств, 1, (1 ) = (2 ), где 1 = (1 ) и 2 = (2 ). Поэтому проблема изоморфизма принадлежит классу NP.

Однако, до настоящего времени неизвестно, принадлежит ли она классу P проблем, для которых существует алгоритм полиномиальной сложности; неизвестно также, является ли она NP-полной проблемой. Иногда, говоря о проблеме изоморфизма графов, имеют в виду проблему существования такого алгоритма.

Предложение 1.1 Изоморфизм вершинных графов распознаваем за время exp(( log )).

Доказательство. Достаточно для каждой биекций между множествами вершин входных графов 1 и 2 проверить верно ли, что Iso(1, 2 ). Каждая проверка имеет сложность (2 ) и количество проверок равно !. Так что общее число шагов такого алгоритма не превышает 2 ! exp(( log )).

По-видимому, первый анализ проблемы изоморфизма графов возникает в статье Р. Рида и Д. Корнейла (1977), с примечательным названием "Graph isomorphism disease" [33].

Приведенная в ней библиография из 36 работ и последующая библиография из ещё 32 работ [21] содержат ссылки на большое число алгоритмов, которые по предположению их авторов, распознают изоморфизм произвольных графов за полиномиальное время. Однако, все эти предположения оказались несостоятельными. Наилучший результат к настоящему времени получен Л. Бабаи, Ю. Лаксом и В. Кантором (1983) и опирается на классификацию конечных простых групп [9].

Теорема 1.2 Изоморфизм вершинных графов распознаваем за время exp(( log )).

Наилучший алгоритм, не использующий теорию групп, был построен М. Годбергом (1983) и имеет сложность exp () [22]. Упомянем здесь также, что наиболее быстрый с практической точки зрения алгоритм проверки изоморфизма графов принадлежит Б. Маккею и его реализация доступна на его домашней странице.

1.2 Изоморфно полные классы графов. Под классом графов будем понимать произвольное множество графов, инвариантное относительно изоморфизмов. Таким образом, вместе с каждым графом класс содержит также любой изоморфный ему граф. Под проблемой изоморфизма графов из класса мы понимаем следующую проблему.

ISO (1, 2 ): для графов 1, 2 определить верно ли, что 1 2.

= Для некоторых классов указанная проблема может быть решена за полиномиальное время, например, легко проверить, что это так, когда состоит лишь из полных или пустых графов, из цепей или циклов произвольной длины. С другой стороны, как показал Ю. Лакс (1982), сложность проверки изоморфизма в классе -вершинных регулярных графов фиксированной степени не превосходит () (см. [25] и п. 4.1), однако проверить изоморфизм в классе всех регулярных графов ничуть не легче, чем в классе всех графов. Для формализации последней ситуации введём несколько определений.





Будем говорить, что проблема 1 полиномиально сводится к проблеме 2, если существование алгоритма полиномиальной сложности для проблемы 2 влечёт существование алгоритма полиномиальной сложности для проблемы 1 ; в этом случае используется запись

1 2. Таким образом, для произвольного класса графов имеем:

ISO ISO. (3)

Две проблемы называются полиномиально эквивалентными, если любая из них полиномиальна сводится к другой. Класс графов является изоморфно-полным, если проблемы ISO и ISO являются полиномиально эквивалентными.

Упражнение. Цепь графа длины 3, у которой концы равны называется циклом этого графа.

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

Теорема 1.3 Следующие классы графов являются изоморфно-полными: класс связных графов, класс двудольных графов, класс регулярных графов.

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

Тогда следующий алгоритм, решает проблему ISO(1, 2 ):

(1) найдём число компонент связности графа, = 1, 2;

(2) если 1 = 2, то графы 1 и 2 неизоморфны;

–  –  –

(4) положим ISO(1, 2 ) := (1, 2 ).

Корректность алгоритма является следствием следующих очевидных утверждений: изоморфные графы имеют одно и то же число компонент связности, дополнение несвязного графа является связным, графы изоморфны тогда и только тогда, когда изоморфны их дополнения. Время работы приведенного алгоритма складывается из времени работы на шагах 1–3 и времени работы алгоритма. Первое, очевидно, ограничено полиномом от размера входных графов. Поэтому ISO ISO, где – класс связных графов. Так что требуемое утверждение для следует из формулы (3).

Граф = (, ), где = {(, ) : (, ) }, называется дополнением графа.

Предположим, что имеется алгоритм полиномиальной сложности, распознающий изоморфизм любых двух двудольных графов. Для произвольного графа = (, ) определим два новых непересекающихся множества 1 = {} и 2 = { : } и положим 1 = {(, ) :, }, 2 = {(, ) : }.

Построим новый граф = (, ), в котором = 1 2 и = 1 2. Тогда.

Действительно, по построению каждое ребро графа инцидентно точно одной вершине из множества 1 и точно одной вершине из множества 2.

Более того, в предположении, что || 3 и () || для всех, имеет место эквивалентность:

. (4) = = Действительно, импликация очевидна. Обратно, положим = | | и = || и предположим, что. Из построения графа следует, что для всех и выполнены = следующие соотношения:

() = (), () =, ( ) = 3.

–  –  –

Корректность алгоритма следует из эквивалентности (4). Далее, поскольку граф имеет = +2+1 = (2 ) вершин и легко строится из графа за время (( )2 ), мы заключаем, что ISO ISO, где – класс всех двудольных графов, и требуемое утверждение следует из формулы (3).

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

Тогда этот класс является изоморфно-полным. Действительно, как и раньше, достаточно указать эффективную конструкцию, которая по произвольному графу = (, ) строит граф = (, ) из класса, и для которой справедливо утверждение (4). С этой целью возьмём две вершинно непересекающиеся копии 1 = (1, 1 ) и 2 = (2, 2 ) графа.

Возьмем произвольное двухэлементное множество = {, }, непересекающееся c 1 2 и положим = 1 2 и = 1 2 {(, )}, где состоит из всех пар (, ), где и 1 2. Легко видеть, что и что () = 2 + 1 ( 1) + 2 () для всех и как выше. Поэтому каждый изоморфизм на другой граф переводит множество в соответствующее ему подмножество графа. Как и раньше, это позволяет построить изоморфизм графа на граф.

Для завершения доказательства приведём конструкцию, которая по произвольному связному графу = (, ) из класса строит регулярный граф = (, ). Утверждение (4) будет легко следовать из построения; остальная часть доказательства аналогична доказательствам в двух предыдущих случаях и остаётся в качестве упражнения. Возьмём = | | непересекающихся по вершинам копий графа ; пусть = (, ) – копия с номером = 1,...,.

Пусть далее – вершина графа и – множество мощности (). Будем считать, что множества,, попарно не пересекаются. Положим = {(, ) :, = 1,..., },

–  –  –

Множество вершин, смежных с вершиной, состоит из () вершин множества и | | = () вершин множества. С другой стороны, вершина из смежна в точности с вершинами {1,..., }. Таким образом, – регулярный граф степени. Далее, легко видеть, что каждая вершина из множества содержится в некотором треугольнике с вершинами из этого множества, в то время как ни одна вершина из множества не содержится ни в каком треугольнике. Поэтому любой изоморфизм графов и индуцирует изоморфизм графов и.

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

1.3 Проблема изоморфизма для категорий. Класс всех графов является примером категории; для наших целей достаточно понимать категорию как класс конечных объектов (комбинаторных, алгебраических или геометрических), в котором определено понятие изоморфизма и группы автоморфизмов. Проблема изоморфизма ISO естественным образом расширяется на случай, когда является категорией, в которой для каждого объекта можно определить его задание и размер последнего. Будем говорить, что категория изоморфнополная, если проблемы ISO и ISO полиномиально эквивалентны. Приведем несколько примеров.

Пусть = (, ) граф и – произвольная сюръективная функция из в начальный отрезок натурального ряда = {1,..., }, где 1. Будем интерпретировать эту функцию как раскраску вершин в цвета из множества ; таким образом, вершина имеет в этой раскраске цвет (). Множество 1 () называется цветным классом, отвечающим цвету. Под раскрашенным графом будем понимать пару (, ) (опуская в некоторых случаях для сокращения записи). Под изоморфизмом раскрашенного графа (1, 1 ) на раскрашенный граф (2, 2 ) будем понимать изоморфизм Iso(1, 2 ), который сохраняет цвета, т.е.

2 ( ) = 1 (), 1, где 1 – множество вершин графа 1. Такой изоморфизм иногда называют цветным изоморфизмом. Два раскрашенных графа 1 и 2 называются изоморфными, 1 2, если найдётся цветной изоморфизм первого графа на второй. Множество всех цветных изоморфизмов раскрашенного графа 1 на раскрашенный граф 2 также обозначается через Iso(1, 2 ).

Группа Aut() цветных автоморфизмов раскрашенного графа определяется формулой (2).

Наконец, раскрашенный граф с вершинами может быть задан с помощью матрицы смежности = (), т.е. матрицы вида если (, ), 1, если (, ) и =, = 0, (), если =.

В этом случае вклад в длину входа не превосходит (2 log ), где – число цветов раскраски. Множитель log появляется, поскольку длина записи каждого числа из множества = {1,..., } в двоичной системе требует не более log битов.

Теорема 1.4 Категория раскрашенных графов является изоморфно-полной.

–  –  –

. (5) = =

–  –  –

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

Приведём три других категории, в которых проблема изоморфизма сводится к проблеме изоморфизма графов. Пусть – конечное множество и – произвольное бинарное отношение на, т.е.. Тогда пара = (, ) называется ориентированным графом с множеством вершин и множеством дуг. Множество ориентированных графов образует категорию относительно естественным образом определяемых изоморфизмов.

Следствие 1.5 Категория ориентированных графов является изоморфно-полной.

–  –  –

= {{1, 2 } : (, ) } {{1, 3 }, {2, 3 } : }, где и – элементы множеств и, соответствующие вершинам и ориентированного графа. Определим раскраску вершин простого графа (1 2 3, ) в три цвета так, что

– множество всех вершин цвета = 1, 2, 3. Полученный цветной граф обозначим через.

Тогда легко видеть, что тогда и только тогда, когда. Поэтому ISO ISO, = = где – категория раскрашенных графов. Для завершения доказательства остается заметить, что ISO ISO по теореме (1.4), и потому ISO ISO.

Упражнение. Обозначим через категорию всех пар (, ), где – конечное множество порядка и – упорядоченное множество из (1) бинарных отношений на. Изоморфизмами в этой категории считаем биекции, сохраняющие отношения из. Доказать, что категория изоморфно-полная.

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

Можно показать, что для каждой конечной проективной плоскости (, ) существует натуральное число, называемое её порядком, и такое, что каждая прямая содержит + 1 точку, каждая точка принадлежит в точности + 1 прямым и | | = || = 2 + + 1.

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

Следствие 1.6 Пусть категория конечных проективных плоскостей. Тогда ISO ISO.

Доказательство. Пусть (, ) – конечная проективная плоскость. Образуем простой граф с множеством вершин, в котором рёбрами являются пары {, } такие, что, и. Определим раскраску вершин этого графа в два цвета так, что 1 (1) = и 1 (2) =. Полученный таким образом раскрашенный граф обозначим через (, ). Тогда легко видеть, что проективные плоскости (1, 1 ) и (2, 2 ) изоморфны тогда и только тогда, когда изоморфны раскрашенные графы (1, 1 ) и (2, 2 ). Поэтому ISO ISO, где

– категория раскрашенных графов. Для завершения доказательства остается заметить, что ISO ISO по теореме (1.4), и потому ISO ISO.

Отметим, что имеется алгоритм распознавания изоморфизма конечных проективных плоскостей порядка за время (log log ). Поэтому сводимость в следствии 1.6 трудно обратить.

–  –  –

=, = и () = =. Следовательно, – изоморфизм группы на группу. Тем самым мы доказали, что ISO ISO, где – категория раскрашенных графов. Для завершения доказательства остается заметить, что ISO ISO по теореме (1.4), и потому ISO ISO.

В последующих параграфах мы построим алгоритм распознавания изоморфизма конечных групп порядка за время (log ). Поэтому сводимость в следствии 1.7 трудно обратить.

В случае раскрашенных графов индуцированный подграф наследует раскраску исходного графа.

1.4 Проблемы, эквивалентные проблеме изоморфизма. Рассмотрим несколько проблем, полиномиально эквивалентных проблеме изоморфизма графов. Изложение следует статье Р. Матона (1979) [26].

IMAP(1, 2 ): для графов 1 и 2 найти биекцию Iso(1, 2 ) или установить, что последнее множество пусто.

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

Таким образом графы 1 и 2 изоморфны тогда и только тогда, когда IMAP(1, 2 ) =. Это доказывает, что ISO IMAP. Для доказательства обратного включения будем использовать следующую конструкцию индивидуализации вершины раскрашенного графа: для раскрашенного графа (, ) и его вершины пусть (, ) – раскрашенный граф, в котором цвет всех вершин = не меняется, и () = + 1, где – число цветов раскраски. (Если цветной класс графа, содержащий вершину, состоит только из неё самой, то полагаем =.)

Теорема 1.8 Проблемы ISO и IMAP полиномиально эквивалентны.

Доказательство. В силу сказанного выше достаточно проверить, что IMAP ISO. По теореме 1.4 достаточно доказать, что проблема IMAP полиномиально сводится к проблеме ISO, где – категория раскрашенных графов. Предположим далее, что нам дан алгоритм для решения проблемы ISO.

Тогда следующий алгоритм решает проблему IMAP(1, 2 ) для раскрашенных графов 1 и 2 :

–  –  –

(2) если |1 ()| = 1 для всех, то обозначим через единственную биекцию из 1 на 2, сохраняющую цвета вершин. Положим IMAP(1, 2 ) = {}, если Iso(1, 2 ); в противном случае IMAP(1, 2 ) :=.

–  –  –

(4) положим IMAP(1, 2 ) := IMAP(1, 2 ).

Для доказательства корректности достаточно заметить, что корректен выход алгоритма на шаге 2 (конец рекурсии) и в начале шага 4 всегда имеет место равенство

–  –  –

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

Рассмотрим следующую простую конструкцию. Пусть 1 = (1, 1 ) и 2 = (2, 2 ) два простых графа с непересекающимися множествами вершин одного и того же размера. Положим 12 = 1 2 {1, 2 } и 12 = 1 2 {(1, 2 )} {(, ) : = 1, 2, 1 2 }, (7) где 1 и 2 различные элементы, не принадлежащие множеству 1 2. Тогда 12 = (12, 12 ) простой граф с 2 + 2 вершинами, в котором степени вершин 1 и 2, равные + 1, больше степеней всех других вершин (которые ). Отсюда легко следует, что каждый автоморфизм графа 12 либо фиксирует вершины 1 и 2, либо меняет их местами. В первом случае, ограничение его на множество индуцирует автоморфизм графа, = 1, 2; обратно, по любым двум таким автоморфизмам строится единственный автоморфизм графа 12, ограничение которого на совпадает с. Во втором случае, ( ) = 3 и ограничение на является изоморфизмом графа на граф 3 ; обратно любые два таких изоморфизма индуцируют автоморфизм графа 12, меняющий местами 1 и 2. Приведенное рассуждение показывает, что | Aut(12 )| = | Aut(1 )| · | Aut(2 )| + | Iso(1, 2 )|2.

Поскольку, по определению также Aut() = Iso(, ) для любого графа, описанная выше конструкция устанавливает полиномиальную эквивалентность двух следующих проблем.

ICOUNT(1, 2 ): для графов 1 и 2 найти число | Iso(1, 2 )|.

ACOUNT(): для графа найти число | Aut()|.

Заметим, что число изоморфизмов между двумя -вершинными графами не превосходит числа ! всех возможных биекций между их множествами вершин. Поэтому длина выхода в обеих проблемах не превосходит log ! = ( log ).

Теорема 1.9 Проблемы ISO, ICOUNT и ACOUNT полиномиально эквивалентны.

Доказательство. Ясно, что 1 2 если и только если | ICOUNT(1, 2 )| 0. Поэтому = ISO ICOUNT. Для доказательства обратной сводимости (с учётом установленной выше полиномиальной эквивалентности проблем ICOUNT и ACOUNT) достаточно доказать по теореме 1.4, что ICOUNT ISO, где – категория раскрашенных графов. Предположим далее, что нам дан алгоритм для решения проблемы ISO.

Тогда следующий алгоритм, решает проблему ICOUNT(1, 2 ) для раскрашенных (а потому и для простых) графов 1 и 2 :

–  –  –

(2) если |1 ()| = 1 для всех, и единственная биекция из 1 на 2, сохраняющая цвета вершин, принадлежит множеству Iso(1, 2 ), то ICOUNT(1, 2 ) = 1; в противном случае ICOUNT(1, 2 ) := 0.

(3) выберем цвет, для которого цветной класс 1 () содержит более чем одну вершину и пусть 1 (1 ) =. Положим

–  –  –

С другой стороны, для любых двух элементов, из правой части перестановка 1, очевидно, принадлежит группе Iso(1, 1 ) = Aut(1 ). Поэтому | Iso(1, 2 )| = | Aut(1 )| для всех 2. Таким образом, из равенства (8) следует, что

–  –  –

Корректность алгоритма доказана. Тот факт, что время работы является полиномиальным от числа вершин входных графов и времени работы алгоритма для проблемы ISO проверяется также, как и в теореме 1.8.

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

Эта группа совпадает с пересечением всех подгрупп симметрической группы, которые содержат :

=.

Sym( ) <

–  –  –

Теорема 1.10 Проблемы ISO и AGEN полиномиально эквиваленты.

Доказательство. Докажем сначала, что ISO AGEN. С этой целью, пусть 1 и 2 графы с одинаковым числом вершин и 12 – граф, определённый сразу же за формулами (7). Из свойств этого графа, приведённых там, следует, что два графа 1 и 2 изоморфны в том и только в том случае, когда множество когда найдётся такой автоморфизм Aut(12 ), что 2 = (1 ). Однако, легко видеть, что последнее утверждение эквивалентно тому, что каждое множество образующих группы Aut(12 ) содержит такой автоморфизм. Отсюда следует, что ISO AGEN.

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

–  –  –

где – любой элемент из Aut(), переводящий вершину в вершину (если для некоторого не существует ни одного элемента, множество Aut( ) считается пустым).

Поэтому любой элемент из Aut() является произведением некоторого элемента из Aut( ) и одного из элементов, где {}. Так что множество, найденное на шаге 3 действительно является множеством образующих группы Aut(). Корректность алгоритма доказана.

Время работы складывается из проверки размеров цветных классов, построения графов вида, и не более чем 2 обращений к алгоритму IMAP (, ). Так что, AGEN IMAP.

Ещё одна проблема, эквивалентная проблеме изоморфизма графов, использует понятие автоморфного разбиения, определяемого следующим образом. Пусть – простой граф с множеством вершин. Определим бинарное отношение на последнем множестве, полагая в том и только в том случае, если = для некоторого автоморфизма Aut(). Легко видеть, что является отношением эквивалентности и его классы образуют разбиение множества. Это разбиение и называется автоморфным разбиением графа. (В действительности оно есть ничто иное, как разбиение множества на орбиты группы Aut(), см. § 3.1).

APART(): найти автоморфное разбиение графа.

Из свойств графа 12, определённого сразу же за формулами (7), следует, что два графа 1 и 2 изоморфны в том и только в том случае, когда множество {1, 2 } 12 является классом автоморфного разбиения графа 12. Поэтому ISO APART. С другой стороны, как мы увидим в § 3.1, автоморфное разбиение графа полиномиально вычислимо по любому множеству образующих группы Aut(). Следовательно, APART AGEN, и по теореме 1.10 мы заключаем, что APART ISO. Таким образом, имеет место следующее утверждение.

Теорема 1.11 Проблемы ISO и APART полиномиально эквивалентны.

2 Комбинаторные алгоритмы проверки изоморфизма

2.1 Построение канонической формы почти всех графов. Пусть = (, ) – граф и – биекция из множества на некоторое множество. Положим = (, ), где = {(, ) : (, ) } граф с множеством вершин. Ясно, что Iso(, ) и, в частности,. Если = {1,..., }, то биекция называется пометкой графа, а = число – меткой вершины.

Для произвольного класса графов будем обозначать через * совокупность всех графов вида, где и – пометка графа. Каждому графу * сопоставим строку, состоящую из нулей и единиц и определяемую следующим образом () = (11,..., 1, 21,..., 2,..., 1,..., ), (9) где – число вершин графа и = () – его матрица смежности. Это задаёт линейный порядок в *, в котором неравенство 1 2 означает, что либо |1 | |2 |, либо |1 | = |2 | и (1 ) (2 ), т.е. что строка (1 ) лексикографически меньше строки (2 ).

Произвольное отображение CF : * называется каноническим, если выполнены следующие два условия:

(1) для всех имеем: CF(), = (2) для всех, имеем: CF() = CF().

= Заметим, что первое из этих условий влечёт, что CF() = для некоторой пометки графа, и потому для любой пометки вида, где Aut(). Граф CF() и любая из этих пометок называются канонической формой и канонической пометкой графа. Отметим, что, вообще говоря, имеется много канонических отображений, одним из которых, например, является следующее:

–  –  –

Обозначим через, класс всех графов с множеством вершин {1,..., }, для которых () =. Предположим, что и графы из этого класса. Тогда () = {} и () = {} для некоторых пометок и. Если =, то =. Поэтому

–  –  –

при = +1,...,, где 1,..., – вершины графа, мы заключаем, что ( ) = для.

Далее, обозначим через (соотв. ) – множество всех вершин с индексами, смежных с (соотв. ). Тогда состоит из всех, для которых -ая позиция в двоичном разложении числа ( ) равна единице, и аналогичное утверждение верно и для. Поскольку ( ) = при, упорядочение вершин с номерами + 1 на шаге 3 вместе с условием шага 4 показывают, что ( ) = и для. Так что, ( ) =, = 1,...,.

По определению пометки на шаге 5 получаем, что ( ) = = ( ) для всех. Поэтому =. Таким образом, доказано следующее утверждение.

–  –  –

Можно показать, что при = 3 log / log 2, класс состоит из почти всех графов в том смысле, что отношение |, |/| | стремится к единице при, где класс всех 2( 2 ) графов с вершинами. Из этого результата и леммы 2.1 получается следующая теорема.

Теорема 2.2 Для почти-всех графов с вершинами проблема изоморфизма разрешима за время (2 ).

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

Теорема 2.3 Пусть – дерево с вершинами.

Тогда (1) если 2, то содержит по крайней мере один лист, т.е. вершину степени 1, (2) содержит в точности 1 ребер, (3) любые две вершин в являются концами точно одной простой цепи.

Доказательство. Для доказательства утверждения (1) предположим, что любая вершина смежна с по крайней мере двумя другими. Рассмотрим цепь = 0, 1,..., = графа, в которой все вершины различны и число – максимальное из возможных. Тогда 2.

Более того, поскольку () 2, вершина смежна с некоторой вершиной, отличной от

1. Из максимальности следует, что = для некоторого {0,..., 2}. Однако, в этом случае вершины =, +1,..., образуют цикл в графе. Противоречие.

Утверждение (2) легко следует из утверждения (1) индукцией по числу вершин. Наконец, для доказательства утверждение (3) достаточно заметить, что если две вершины являются концами двух различных цепей 1 и 2, то в графе, индуцированном множеством 1 2 найдётся цикл графа.

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

Лемма 2.4 Проблема изоморфизма деревьев полиномиально эквивалентна проблеме изоморфизма корневых деревьев.

–  –  –

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

Здесь будем считать, что минимальный цвет раскраски равен 0.

Лемма 2.5 Пусть и – корневые деревья и и – раскраски их вершин, построенные приведенным выше алгоритмом.

Тогда для любой пары вершин и таких, что () = ( ) корневые деревья () и ( ) изоморфны тогда и только тогда, когда () = ( ).

Доказательство. Необходимость нашего утверждения очевидна. Для доказательства достаточности используем индукцию по уровню () = ( ). Если лист, то () = 0 и потому ( ) = 0. В этом случае () и ( ) – одновершинные деревья и наше утверждение очевидно. В противном случае, пусть 1,..., – сыновья. Поскольку () = ( ), мы имеем () = ( ) и, следовательно, также имеет сыновей, скажем 1,...,. Более того, в силу равенства () = ( ) можно также считать, что ( ) = ( ) для всех = 1,...,. По индукции отсюда следует, что корневые деревья ( ) и ( ) изоморфны. Однако, в этом случае, как легко видеть, изоморфны и корневые деревья () и ( ).

Теорема 2.6 Каноническая пометка корневого дерева с вершинами строится за время (1).

5 Доказательство. Отметим, что алгоритм проверки изоморфизма корневых деревьев индуцирует некоторую раскраску такого дерева: достаточно применить его при =.

Используя такую раскраску определим новую раскраску корневого дерева следующим образом:

–  –  –

Ясно, что () = ( ) влечёт () = ( ) для всех,, и что для всех цвет любой вершины множества меньше цвета любой вершины множества. Более того, справедливо следующее утверждение.

Лемма 2.7 Классы автоморфного разбиения вершин дерева совпадают с цветными классами раскраски.

Если корневое дерево и его раскраска получается описанной выше процедурой, то Iso(, ) = Iso(, ), где = (, ) и = (, ).

–  –  –

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

Опишем алгоритм построения канонической пометки корневого дерева с вершинами.

–  –  –

Пусть дерево с корнем и множеством вершин, и – его пометка, построенная = описанным выше алгоритмом. Тогда достаточно проверить, что найдётся изоморфизм Iso(, ), для которого = : в этом случае = =. Обозначим через 1,..., сыновей корня дерева, упорядоченных в соответствии с шагом 1 алгоритма. Тогда из леммы 2.7 следует, что ( ) ( ), = 1,...,.

= Кроме того, легко видеть, что для каждого цветные классы раскраски, содержащиеся в множестве вершин дерева ( ) совпадают (с сохранением упорядочения по цвету) с цветными классами раскраски, построенной для этого дерева, и аналогичное утверждение справедливо и для деревьев ( ). Поэтому по индукции найдётся изоморфизм Iso(( ), ( )), для которого =, = 1,...,, где – пометка дерева ( ), найденная на шаге 2 алгоритма. Определим биекцию :, ограничение которой на множество вершин дерева ( ) совпадает с. Тогда в силу шага 3, очевидно, Iso(, ) и =. Теорема доказана.

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

Алгебраический взгляд на эту ситуацию будет дан в § 5.2.

2.3 Распознавание изоморфизма групп. В изложении мы следуем статье Г.Миллера (1978) [27]. Конечное множество, с определённой на нём бинарной операцией (, ) · называется квазигруппой, если для любых двух элементов, существуют и единственны элементы,, для которых · = и · =. Заметим, что группы – это в точности те квазигруппы, в которых имеет место ассоциативность. Изоморфизм квазигрупп определяется естественным образом; порядком квазигруппы называется число ||. Ниже мы предполагаем, что квазигруппа порядка имеет = {1,..., } и представляется на вход алгоритма квадратным массивом = () c строками и столбцами, где, = ·,, = 1,....

В этом случае определяющее свойство квазигруппы эквивалентно тому, что каждая строка и каждый столбец этого массива содержит каждое из чисел 1,..., (в точности по одному разу). Массив, удовлетворяющий последнему условию, называется латинским квадратом порядка. Таким образом, квазигруппы и латинские квадраты дают два способа говорить об одном и том же объекте.

Теорема 2.8 Проблема изоморфизма для квазигрупп (а потому и для) групп порядка разрешима за время (log ).

Доказательство. Определяющее свойство квазигруппы позволяет рассмотреть три бинарных операции (, ) ·, (, ) и (, ), где и – элементы квазигруппы, для которых · = и · =. Относительно каждой из них исходное множество, очевидно, является квазигруппой.

Будем говорить, что – множество образующих квазигруппы, если пересечение всех подквазигрупп квазигруппы, содержащих, совпадает с, эквивалентно, если каждый элемент может быть записан в виде:

= (· · · (1 1 2 ) · · · ) 1, (10) где, – одна из трёх определённых выше бинарных операций и – натуральное число.

Лемма 2.9 Каждая квазигруппа порядка обладает множеством из не более чем log образующих.

Доказательство. Пусть – квазигруппа порядка. По индукции достаточно проверить, что любая её собственная подквазигруппа имеет порядок /2. Пусть. Тогда определяющее свойство влечёт, что все элементы множества · различны (иначе 1 · = 2 · для различных 1 и 2 ). Аналогично, множество · не пересекается с (иначе 1 · = 2 для некоторых 1, 2 и потому вопреки выбору ). Таким образом, = || | | + | · | = 2| |,

–  –  –

где 1, 2 и 3 – три бинарных операции, определённые выше. Тогда в силу конечности найдётся натуральное число 0 1, для которого 0 = 0 1. Пусть 0 – минимальное число, для которого выполнено последнее равенство. Тогда, очевидно, что 0 и 0 – подквазигруппа квазигруппы. Если 0 =, то – множество её образующих и вычисление множества 0 можно организовать так, чтобы на выходе было получено представление каждого элемента в виде (10) причём. Используя это замечание, опишем алгоритм распознавания изоморфизма квазигрупп и порядка.

–  –  –

(2) для каждого упорядоченного -подмножества {1,..., } определим отображение из в, которое переводит в и элемент вида (10) в элемент того же вида с, замененным на.

–  –  –

Корректность алгоритма следует из леммы 2.9, а время его работы, очевидно, не превосходит (log ).

Граф латинского квадрата порядка имеет в качестве вершин пары (, ) {1,..., }2, причём пары (, ) и (, ) смежны в том и только в том случае, если ( =, = ) & ( =, = ) & ( =, =,, =, ).

Можно доказать, что графы латинских квадратов и изоморфны тогда и только тогда, когда соответствующие квазигруппы и изотопны, т.е. найдутся три биекции :, для которых 1 · 2 = 3 для всех,,. Мы оставляем в качестве упражнения построение проверки изотопии квазигрупп порядка за время (log ), равно как и построении канонических модификаций алгоритмов этого пункта.

3 Алгоритмы для работы с группами перестановок

3.1 Базовые алгоритмы для групп перестановок. В пункте 2.3 группы задавались таблицами умножения и размер задания был пропорционален квадрату порядка группы. Однако каждая группа является группой перестановок в следующем смысле. Пусть – группа.

Тогда с каждым её элементом можно связать две перестановки множества её элементов:

: 1 и :.

Отображения и являются мономорфизмами группы в симметрическую группу Sym(). Такие представления группы не единственно возможные. Часто можно найти представления Sym( ), в которых размер | | существенно меньше порядка группы.

Например, группа Sym( ) порождается двумя перестановками и, следовательно, размер её задания есть (), где = | |, в то время как её порядок равен !.

Ниже мы рассматриваем группы перестановок на множестве = {1,..., }; его элементы называются точками, а число – степенью группы. Мы полагаем Sym() = Sym( ).

Таким образом, группа перестановок степени это просто подгруппа группы Sym(). Размер задания такой группы определяется выбором её множества образующих и равен ||.

Умножение и нахождение обратного элемента легко реализуется за время ().

Пусть Sym() группа перестановок. Для произвольной точки положим = { : }, = { : = }; (11)

–  –  –

|| = | || |. (12) Лемма 3.1 Пусть Sym(). Тогда по заданному множеству из образующих, множество Orb() может быть найдено за время (3 ).

Доказательство. Пусть – множество из образующих группы. Тогда достаточно суметь за время (2 ) найти орбиту, содержащую данную точку.

Это делается с помощью следующего алгоритма:

(1) положим = {},

–  –  –

(3) если, то положим := и перейдем к шагу 2; в противном случае, – орбита группы, содержащая точку.

Корректность алгоритма следует из того, что каждый элемент группы можно записать как произведение перестановок из. Заметим далее, что на каждой итерации шагов 2–3 размер множества увеличивается. Поэтому число итераций не превосходит. Поскольку при вычислении достаточно применять перестановки из лишь к тем элементам из, которые появились на последнем шаге, каждая итерация реализуется за время (). Так что общее время работы алгоритма нахождения орбиты, содержащей точку не превосходит (2 ).

Множество называется инвариантным (относительно группы ) или -инвариантным, если оно является объединением орбит группы. В этом случае для каждой перестановки можно определить её ограничение Sym( ) и гомоморфизм, ядром и образом которого соответственно являются группы ( ) = { : = для всех }, = { : };

первая группа называется точечным стабилизатором множества. Легко видеть, что если = {}, то ( ) =. По данному множеству образующих группы можно эффективно найти множество образующих группы. Отметим, также, что если 1 и 2 непересекающиеся -инвариантные множества, объединение которых совпадает с, то 1 2, (13) где группа в правой части – прямое произведение групп 1 и 2 и состоит из всех перестановок Sym() таких, что = и, = 1, 2.

Группа перестановок называется транзитивной, если она имеет точно одну орбиту. В этом случае для любых, найдётся перестановка такая, что =. Группа, не являющаяся транзитивной, называется интранзитивной. Таким образом, группа Sym() транзитивна для всех, в то время как тривиальная группа {id } интранзитивна при 2.

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

Лемма 3.1 и формула (13) показывают, что распознавание транзитивности реализуется за полиномиальное время, и что изучение интранзитивных групп сводится к транзитивному случаю.

Пусть – транзитивная группа. Множество называется её блоком, если для любой перестановки либо =, либо =. Легко понять, что одноэлементные множества и само множество являются блоками; они называются тривиальными. Следующее упражнение даёт примеры нетривиальных блоков.

Упражнение. Пусть 1 = (1, 1 ) и 2 = (2, 2 ) – две непересекающиеся по вершинам копии одного и того же связного простого графа с по крайней мере двумя вершинами и транзитивной группой автоморфизмов. Обозначим через граф с множеством вершин 1 2 и множеством рёбер 1 2. Тогда группа Aut() транзитивна и множества 1 и 2 – ее нетривиальные блоки.

Транзитивная группа Sym( ) называется импримитивной, если она имеет нетривиальный блок. Из определения блока легко следует, что (даже без предположения о нетривиальности) множество также является блоком для всех. Поэтому в силу транзитивности множество = { : } образует разбиение множества в непересекающиеся блоки одного и того же размера. Множество называется системой импримитивности группы, а блоки этой системы – сопряжёнными; будем говорить, что система нетривиальна, если нетривиален один (а потому и каждый) её блок. Транзитивная группа перестановок, не являющаяся импримитивной, называется примитивной.

Упражнение. Пусть – цикл длины. Тогда группа Aut() примитивна в том и только в том случае, если число является простым.

Изучение транзитивных групп сводится к примитивному случаю с помощью следующей конструкции. Пусть – нетривиальный блок (транзитивной) группы. Тогда каждая перестановка индуцирует перестановку Sym() системы импримитивности =.

Нетрудно проверить, что отображение является гомоморфизмом группы в группу Sym(). Ядром и образом этого гомоморфизма соответственно являются группы

–  –  –

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

Теорема 3.2 Пусть – транзитивная группа перестановок степени, заданная множеством образующих полиномиального от размера.

Тогда за время (1) можно проверить, является ли группа примитивной, и если нет - то построить нетривиальную систему импримитивности.

Доказательство. Для каждой образующей группы из данного множества образующих определим перестановку Sym( 2 ), которая переводит пару (, ) в пару (, ). Тогда по лемме 3.1 можно за время (1) построить множество орбит группы Sym( 2 ), порождённой образующими. Каждое множество Orb( ), будучи подмножеством множества 2, является бинарным отношением на множестве. Среди таких отношений (в силу транзитивности) имеется единственное рефлексивное отношение 1 = {(, ) : }, и отношение = {(, ) 2 : (, ) }. Поэтому требуемое утверждение вытекает из следующей леммы.

Лемма 3.3 Множество вершин любой компоненты связности простого графа = (, ), где Orb( ), является блоком группы.

Более того, последняя примитивна тогда и только тогда, когда граф связен для каждого нерефлексивного отношения Orb( ).

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

Пусть – система импримитивности группы. Тогда для каждого блока группы объединение блоков группы, принадлежащих множеству, также является блоком группы. Используя это замечание и теорему 3.2, мы получаем следующее утверждение.

Следствие 3.4 Пусть – транзитивная группа перестановок степени, заданная множеством образующих полиномиального от размера. Тогда за время (1) можно построить систему импримитивности, для которой группа примитивна.

3.2 Алгоритм Симса. Одной из наиболее важных проблем, связанных с вычислениями с группами перестановок, является проблема распознавание принадлежности перестановки Sym( ) группе перестановок Sym( ). Алгоритм решения этой проблемы был предложен Ч. Симсом (1970), а его сложность проанализирована М. Фюрстом, Д. Хопкрофтом и Ю. Лаксом (1980) в работе [20]. Ключевой идеей алгоритма является построение по заданному множеству образующих группы Sym( ) нового множества, определяемого следующим образом (напомним, что = {1,..., }).

–  –  –

= +1 · · · 1,. (15) Приведённое утверждение при = 0 означает, что = 0 · · · 1 является множеством образующих группы. Оно называется сильным и состоит из не более чем 2 элементов (здесь мы используем тот факт, что | | для всех ; последнее следует из того, что если, () и =, то = и потому (+1) ). Следует отметить, что определение сильного множества образующих зависит от выбора нумерации точек и от выбора систем представителей. Более того, в действительности, некоторые из групп () могут быть равны, а потому и размер может быть уменьшен. Однако, всё это не столь существенно, если важным является лишь полиномиальная оценка сложности алгоритмов.

Теорема 3.5 Пусть группа перестановок степени задана сильным множеством образующих.

Тогда порядок этой группы может быть найден за время (1). Более того, распознавание принадлежности перестановки группе определяется за то же время.

Доказательство. Пусть – сильное множество образующих группы. Тогда во введённых выше обозначениях из определения сильного множества следует, что | | = [() : (+1) ], = 0,..., 1.

–  –  –

Если на некотором шаге множество не содержит нужной перестановки, то ; в противном случае на последнем шаге 1 · · · 1 = id и мы получаем разложение (15) при = 0.

Для построения сильного множества образующих группы перестановок Sym( ) степени, заданной множеством образующих, используется процедура, называемая каскадом (sift). Эта процедура строит частично заполненный массив размера, в котором заполненная позиция (, ) содержит перестановку, фиксирующую точки 1,..., 1 и переводящую точку в точку. Множество = всех таких перестановок является сильным множеством образующих группы ; перестановки из -ой строки массива образуют множество. Множество всех "пустых"позиций массива включает все поддиагональные.

КАСКАД (1) создаем пустой массив и полагаем := id для = 1,...,.

(2) для каждой перестановки · выполняем шаги 3–4, начиная с (, ) = (1, 1 );

–  –  –

(5) если в процессе выполнения шагов 2–4 к массиву был добавлен по крайней мере один элемент, то полагаем равным множеству всех непустых элементов и переходим к шагу 2.

Условие конца алгоритма (шаг 5) гарантирует, что цикл шагов 2–4 выполняется не более 2 раз. Кроме того, размер множества при каждом выполнении этого цикла не превосходит 2. Наконец, цикл шага 3 имеет сложность (2 ). Так что алгоритм КАСКАД имеет полиномиальную сложность. Далее, каждый элемент группы =, где =, является произведением образующих группы, содержащихся в множестве. Поэтому. С другой стороны, уже после первого выполнения цикла шагов 2–4 каждая перестановка из является произведением некоторых перестановок из. Поэтому. Таким образом, = =, т.е. – множество образующих группы.

Лемма 3.6 Множество образующих является сильным.

–  –  –

Теорема 3.7 Сильное множество образующих группы перестановок степени, заданной множеством образующих полиномиального от размера, может быть построено за время (1).

Более тонкий анализ алгоритма КАСКАД показывает, что сильное множество образующих группы перестановок степени можно построить за время (5 + | |3 log ). Ещё более эффективной оказывается рандомизация этого алгоритма.

Имеется модификация алгоритма КАСКАД, в которой находится сильное множество образующих полиномиально распознаваемой подгруппы группы перестановок, индекс которой ограничен полиномом () (группа называется полиномиально распознаваемой, если имеется алгоритм полиномиальной сложности для проблемы распознавания принадлежности перестановок к этой группе). Основное отличие этой модификации от алгоритма КАСКАД состоит в том, что у массива появляется строка с индексом 0, длина которой равна (): в неё записываются представители левых классов смежности группы по подгруппе. Полное доказательство следующей теоремы аналогично доказательству теоремы 3.7 и остаётся в качестве упражнения.

Теорема 3.8 Пусть группа перестановок степени задана сильным множеством образующих.

Тогда за время (1) можно построить сильное множество образующих полиномиально распознаваемой группы, индекс [ : ] которой ограничен полиномом от.

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

Следствие 3.9 В условиях теоремы 3.5 сильное множества образующих точечного стабилизатора группы может быть найдено за время (1).

3.3 Вычисление cтабилизатора множества. Стабилизатором множества в группе Sym( ) называется группа { } = { : = }.

Легко видеть, что при = {} эта группа совпадает со стабилизатором точки. Отметим, что стабилизатор множества всегда содержит его точечный стабилизатор. Следующее простое утверждение показывает важность проблемы SETSTAB нахождения стабилизатора в контексте проблемы изоморфизма графов.

Предложение 3.10 ISO SETSTAB.

Доказательство. По теореме 1.10 достаточно проверить, что AGEN SETSTAB. Пусть = (, ) – простой граф. Обозначим через Sym( 2 ) группу, состоящую из всех перестановок (, ) (, ), где Sym( ). Тогда каждая перестановка {} (здесь отождествляется с соответствующим подмножеством множества 2 ) индуцируется некоторой Sym( ) такой, что = =. Так что Aut() и требуемое утверждение следует из того, что множество образующих группы эффективно строится из образующих группы Sym( ).

Отметим важный частный случай, в котором проблема SETSTAB имеет простое решение.

Пусть Sym( ) транзитивная группа перестановок степени и пусть – блок этой группы. Тогда, очевидно, группа { } – полиномиально распознаваема и [ : { } ] = ||, где

– система импримитивности группы, содержащая блок. Поскольку ||, образующие группы { } можно найти за полиномиальное от время исходя из образующих группы по теореме 3.8. В общем же случае, когда множество не является блоком, индекс [ : { } ] может быть экспоненциальным и теорема 3.8 (неприменима. Пример: если = Sym( ), ) чётно и | | = /2, то указанный индекс равен /2.

Теорема 3.11 Пусть – класс групп, содержащий вместе с каждой группой все её нормальные подгруппы и фактор-группы.

Предположим, что существует полином () такой, что если – примитивная группа степени, то || (). Тогда проблема SETSTAB разрешима за полиномиальное время.

–  –  –

Для доказательства теоремы мы построим алгоритм полиномиальной сложности, который находит множество STB () для произвольной раскраски, группы из класса, перестановки множества и -инвариантного множества. В этих предположениях справедливо следующее утверждение.

Лемма 3.12 Если 0 STB (), то STB () = STB ()0.

Доказательство. Инвариантность множества влечёт, что множество STB () является подгруппой группы. Далее, пусть 0 STB (). Тогда 0 и потому = 0. С другой стороны, если и, то и, следовательно, цвета точек ( )0 и одинаковы. Таким образом, 0 принадлежит множеству STB () = STB (0 ) тогда и только тогда, когда STB (). Лемма доказана.

В силу леммы 3.12 непустое множество STB () задаётся множеством образующих группы STB () и некоторой перестановкой 0. Отметим также, что алгоритм нахождения множества STB () при = id решает проблему SETSTAB, поскольку, как легко видеть,

–  –  –

Для проверки корректности алгоритма заметим, что при применении рекурсии на шагах 2 и 3 размер множества строго уменьшается и потому алгоритм завершает за конечное число шагов. Далее, при применении рекурсии множество остаётся инвариантным: это очевидно на шаге 2, а на шаге 3 следует из того, что каждый блок системы является 0 -инвариантным.

Наконец, все группы, появляющиеся в процессе работы (, ( ), 0 и, группы, найденные рекурсивно), получаются из группы последовательностью факторизаций и перехода к нормальной подгруппе. Поэтому все они принадлежат классу. В частности, примитивность группы ( ) из шага 3.2 влечёт, что |( ) | (). (18) Таким образом, корректность рекурсии доказана. Для завершения доказательства корректности достаточно воспользоваться формулами (17).

Для оценки сложности алгоритма обозначим через () время его работы для множества размера. Тогда, очевидно, сложность шага 1 не превосходит 1 для некоторой константы 1 0. Далее, на шаге 2 мы используем алгоритм леммы 3.1 для проверки транзитивности группы и нахождения орбиты. Поэтому в силу этой леммы сложность шага 2 не превосходит () + ( ) + 2 для некоторой константы 2 0. Наконец, на шаге 3 используя алгоритмы теоремы 3.2 и следствия 3.4 можно за полиномиальное время распознать примитивность группы и в импримитивном случае найти некоторую нетривиальную систему импримитивности, для которой группа ( ) примитивна. Далее группа 0 также находится за полиномиальное время используя замечание после предложения 3.10. Объединение классов смежности на шаге 3.5 в силу леммы 3.12 также является классом смежности, для его задания достаточно найти с помощью алгоритма КАСКАД образующие группы, порождённой произведениями образующих подгрупп на обратный к любой из перестановок этого объединения. Таким образом сложность шага 3 не превосходит () (/)+3, где 3 – некоторая константа и = || (шаг 3.1). Индукцией по отсюда легко следует, что () = (1).

Имеется много естественных классов групп, удовлетворяющих условиям теоремы 3.11.

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

Теорема 3.13 Для каждого простого числа класс всех -групп удовлетворяет всем условиям теоремы 3.

11.

Доказательство. Заметим, что порядок любой подгруппы или фактор-группы конечной группы делит порядок || группы. Поэтому класс всех -групп содержит вместе с каждой группой все её подгруппы и фактор-группы. Для завершения доказательства покажем, что любая примитивная -группа имеет порядок. Нам потребуются три леммы.

Лемма 3.14 Каждая нетривиальная -группа имеет нетривиальный центр.

Доказательство. Пусть – -группа. Тогда каждый её элемент индуцирует перестановку : 1 её множества элементов. Отображение является гомоморфизмом группы в -подгруппу группы Sym(). В силу равенства (12) длина каждой орбиты группы делит || и потому является степенью числа. С другой стороны, сумма длин всех орбит равна || и тоже является степенью числа. Однако, орбита, содержащая единичный элемент группы имеет длину 1. Поэтому найдётся по крайней мере 1 1 других орбит длины 1.

Остаётся заметить, что если {} – такая орбита, то элемент принадлежит центру группы.

Лемма 3.15 Любая максимальная подгруппа нетривиальной -группы имеет индекс.

Доказательство. Утверждение очевидно, если || =. Предположим, что || и 0 – максимальная подгруппа группы. По лемме 3.14 центр группы содержит подгруппу порядка. Из максимальности группы 0 следует, что либо 0 =, либо 0. В первом случае [ : 0 ] =, что и требовалось. Во втором случае, группа 0 / – максимальная подгруппа нетривиальной -группы /, и требуемое утверждение следует по индукции.

Лемма 3.16 В примитивной группе стабилизатор любой точки является максимальной подгруппой.

Доказательство. Пусть Sym( ) – примитивная группа и. Предположим, что найдётся группа такая, что. Тогда множество = является блоком группы. Действительно, если для некоторой перестановки, то 1 = = 2 для некоторых 1, 2. Но тогда 1 2, и потому. Следовательно, = = =.

Поэтому – блок группы. Более того, если = {}, то, а если =, то [ : ] = [ : ] и, значит =. В силу предположения оба эти случая невозможны и потому – нетривиальный блок группы, что противоречит примитивности последней.

Пусть теперь Sym( ) – примитивная -группа. Тогда по лемме 3.16 для каждой точки группа – максимальна в. По лемме 3.15 отсюда следует, что [ : ] =. В силу равенства (12) это означает, что | | = | | = [ : ] =. Отсюда следует, что каждая орбита

-группы состоит из одной точки. Следовательно, = {id } и || =.

4 Групповые алгоритмы проверки изоморфизма

4.1 Распознавание изоморфизма графов ограниченной степени. В этом пункте для натурального числа мы обозначаем через класс всех простых графов, у которых степень любой вершины не превосходит. Легко видеть, что каждая компонента связности графа из 2 (который, очевидно, содержит класс 1 ) является либо цепью, либо циклом. Поэтому распознавание изоморфизма таких графов не представляет сложности. Алгоритм полиномиальной сложности для распознавания изоморфизма графов из класса для произвольного фиксированного числа был предложен Ю. Лаксом (1982) [25]. Были предложены модификации этого алгоритма, проверяющие изоморфизм -вершинных графов за время (3 log ) при = 3 и за время ( log ) для произвольного. Ниже мы ограничимся лишь случаем, когда = 3, и докажем следующую теорему.

Теорема 4.1 Проблема ISO3 разрешима за полиномиальное время.

Доказательство. Легко видеть, что каждая связная компонента графа из 3 также принадлежит этому классу. Поэтому ISO3 ISO, где класс всех связных графов из 3. Пусть 1 = (1, 1 ) и 2 = (2, 2 ) графы из, непересекающиеся по вершинам и содержащие по крайней мере одно ребро.

Для каждой пары рёбер 1 1 и 2 2 определим новый граф = (, ) следующим образом:

= 1 2 {1, 2 } = 1 2 12 {1, 2 }, и где 1 и 2 – произвольные различные элементы, не содержащиеся в 1 2, и 12 состоит из ребра (1, 2 ) и четырёх других рёбер вида (, ), в которых = 1, 2 и – любая из двух вершин, инцидентных ребру. Заметим, что. Будем считать, что вершины графа раскрашены в два цвета так, что множество {1, 2 } является одним из двух цветных классов.

Лемма 4.2 1 2 тогда и только тогда, когда найдутся рёбра 1 1 и 2 2, для = которых {1, 2 } Orb(Aut()).

Доказательство. Если Iso(1, 2 ), то в качестве 1 выбираем любое ребро графа 1, а в качестве 2 его -образ в 2. Обратно, пусть Aut() такой, что = 2. Из построения графа следует, что любая цепь в графе, начинающаяся в 1 и не содержащая 2, переводится автоморфизмом в цепь графа, начинающуюся в 2 и не содержащую 1. При этом все рёбра первой цепи (за исключением инцидентных 1 ) принадлежат 1 и все ребра её образа (за исключением инцидентных 2 ) принадлежат 2. В силу связности графов 1 и 2 отсюда легко получается, что индуцирует биекцию множества 1 на множество 2, переводящую множество 1 {1 } в множество 2 {2 }. Эта биекция также переводит соседей вершины 1 в соседей вершины 2, а потому и ребро 1 в ребро 2. Так что Iso(1, 2 ).

Леммы 4.2 и 3.

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

Пусть = (, ) – -вершинный граф из класса с выделенным ребром = (, ). Для 1 обозначим через = (, ) подграф этого графа с унаследованной раскраской, состоящий из всех вершин и рёбер, которые появляются на цепях длины не более, проходящих через ребро. Таким образом, 1 = {, } и 1 = {}, = в силу связности графа и для всех = 2,..., имеет место формула () = () 1 =,, (19) где () = () и = 1. В частности, никакие две вершины последнего множества не являются смежными в графе. Более того, () () для всех. Поэтому каждый граф содержится в классе, имеет выделенное ребро, а его группа автоморфизмов = Aut( ) оставляет множество 1 на месте. Используя последнее утверждение легко доказать по индукции следующую лемму.

Лемма 4.3 При множество является -инвариантным.

Для нахождения группы = Aut() мы будем последовательно находить группы, начиная с = 1. Заметим, что 1 имеет порядок 2 и состоит из двух перестановок: тождественной и меняющей местами и. Далее, по лемме 4.3 для любого = 2,..., можно определить естественный гомоморфизм : 1, сопоставляющий каждой перестановке из её ограничение на множество 1.

Лемма 4.4 Ядро гомоморфизма является 2-группой и ее образующие можно найти за время (1).

Доказательство. Определим отношение эквивалентности на множестве полагая () = ().

–  –  –

где – подгруппа группы, фиксирующая каждый из элементов 1,...,. Более того, поскольку |(+1 ) | 2, из формулы (12) следует, что [ : +1 ] 2, = 0,..., 1.

Таким образом, является 2-группой. Для доказательства второго утверждения достаточно заметить, что группа Sym( ) порождается всеми перестановками вида = (, ), где {, } – класс эквивалентности, состоящий из двух различных элементов.

Как уже отмечалось выше, группа 1 является 2-группой. Рассуждая по индукции предположим, что 1 – 2-группа для некоторого 2. Тогда, очевидно, im( ) 1 и потому im( ) – 2-группа. Поскольку | | = | ker( )| · | im( )|, лемма 4.4 влечёт следующий результат, принадлежащий В. Татту.

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

Для нахождения образа гомоморфизма обозначим через совокупность всех подмножеств множества 1, состоящих не более чем из трёх элементов. Определим три подмножества 1, 2 и 3 множества следующим образом:

–  –  –

где – разбиение множества с наименьшим возможным числом классов, для которого каждое из множеств 1, 2 и 3 является объединением некоторых классов. Тогда ( )1 = { 1 : 0 }. (22) Действительно, включение левой части в правую легко следует из того факта, что каждый элемент группы, очевидно, сохраняет каждое из множеств 1, 2 и 3. Для доказательства

–  –  –

Тогда, из условия (C3) следует, что, что завершает доказательство равенства (22).

Лемма 4.6 При 2 за время (1) можно найти множество, для которого ()

– множество образующих образа гомоморфизма.

Доказательство. В силу равенства (22) достаточно указать эффективный алгоритм нахождения множества образующих группы 0. Заметим, что = {1,..., } для некоторого числа 6. Поэтому построение такого алгоритма сводится к последовательному вычислению множеств образующих групп 5 = {1 },..., 0 = (1 ){6 } (см. (21)). С другой стороны, по следствию 4.5 группа, а потому и её подгруппы 5,..., 0, являются 2-группами. По теореме 3.13 класс 2-групп удовлетворяет всем условиям теоремы 3.11. Таким образом, в силу этой теоремы образующие каждой из групп могут быть найдены за время (1).

Для завершения доказательства теоремы 4.1 достаточно заметить, что в силу лемм 4.4 и 4.6 за время (1) можно найти множество образующих для ядра и образа гомоморфизма, а потому и для группы. Повторяя описанный алгоритм для = 2,..., можно эффективно найти и множество образующих группы = Aut().

Алгоритм, лежащий в основе доказательства теоремы 4.1, остаётся практически тем же самым и для класса графов при произвольном 4. Однако, в этом случае группы, возникающие в процессе работы, уже не будут 2-группами. Тем не менее, можно доказать (и это делается в оригинальной статье Ю. Лакса), что все эти группы принадлежат некоторому большему классу групп, который зависит от и удовлетворяет всем условиям теоремы 3.11.6 Это позволяет эффективно решать проблему нахождения образующих для стабилизатора произвольного подмножества в группах из этого класса и, тем самым, строить группу 0, определённую формулой (21).

4.2 Графы с ограниченными цветными валентностями и трюк Земляченко. В этом пункте мы выведем "рекордный" результат в проблеме изоморфизма графов, из теоремы 4.7. Эта теорема, доказанная Л. Бабаи и Ю. Лаксом, представляет собой обобщение теоремы 4.1 на класс раскрашенных графов. Именно, пусть (, ) – раскрашенный граф с цветными классами 1,...,, где – максимальный цвет вершины. Цветной валентностью вершины называется число

–  –  –

где () = | () | и () = | () | (напомним, что () – окрестность вершины в графе, и – граф, дополнительный к ); цветной валентностью (, ) графа (, ) назовём максимальную цветную валентность его вершины. Если = 1, то валентность вершины равна её степени в графе или его дополнении. Поэтому теорема 4.1 является частным случаем следующей теоремы.

Теорема 4.7 Изоморфизм -вершинных стабильных графов цветной валентности, не превосходящей может быть проверен за время ( log ).

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

–  –  –

(2) лексикографически упорядочим множество {() : }, (3) найдём однозначно определённую раскраску, для которой () (), если () (), и () = (), если () = (), (4) если число цветов раскраски больше числа цветов раскраски, то полагаем := и переходим к шагу 1.

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

Пусть – вершина раскрашенного графа. Определим новую раскраску как результат стабилизации раскраски, совпадающей с на {}, и для которой () = +1, где – число цветов раскраски. (В отличие от прежнего определения раскраски на стр. 12, в нашем случае раскраска стабильна и число её классов может быть значительно большим, чем у исходной раскраски.) Для последовательности = (1,..., ) положим = (... (1 )...).

Таким образом, раскраска получается последовательной индивидуализацией вершины, за которой следует стабилизация. Следующий результат принадлежит В. Земляченко.

Используя классификацию конечных простых групп, можно уменьшить экспоненту до (/ log ).

Лемма 4.8 Пусть (, ) – стабильный граф с вершинами.

Тогда для любого натурального числа найдётся последовательность вершин = (1,..., ) длины 2/ такая, что цветная валентность графа (, ) не превосходит.

Доказательство. Не умаляя общности можно считать, что цветная валентность графа (, ) больше чем (в противном случае = 0 и = ). Определим последовательность вершин = (1,...

, ) графа так, чтобы выполнялись следующие условия:

(A1) (, 1 ) = (, 1 ) для = 1,...,,

–  –  –

| | 2| | =. (24) Действительно, из определения множества следует, что оно является объединением цветных классов раскраски для всех. Следовательно, если =, и, в частности если =, то. Однако тогда по определению цветной валентности имеем 2| | | | | |, что и требовалось доказать.

В силу (24) для каждого натурального числа все элементы множества = { : {1,..., }, 2 | | 21 }

–  –  –

Недавний результат Л. Бабаи и П. Коденотти [7] обобщает этот результат на гиперграфы.

Именно они доказали, что изоморфизм -вершинных гиперграфов ранга можно распознать за время exp( 2 log ), где – некоторая константа. Здесь под -вершинным гиперграфом ранга понимается пара, состоящая из множества размера и произвольного семейства его подмножеств мощности (таким образом, каждый граф являются гиперграфом ранга 2);

гиперграф задаётся списком множеств, входящих в это семейство.

4.3 Дальнейшие результаты по проблеме изоморфизма. Пусть = (, ) – простой граф. Подграф графа, индуцированный множеством, будет обозначаться через ;

мы также полагаем := (, ) для всех. Пусть – натуральное число.

Граф = (, ) называется -сепарабельным, если для любых двух различных вершин и найдётся множество размера, такое, что и принадлежат различным компонентам связности графа ( ) ( ) (в оригинальном определении Г. Миллера множество имеет размер ). Легко видеть, что все деревья являются 1-сепарабельными (Теорема 2.3), и что все графы степени являются -сепарабельными. Можно доказать, что группы автоморфизмов 2-связных8 -сепарабельных графов с выделенным ребром образуют класс, для которого выполнены все условия теоремы 3.11. Используя этот результат и редукцию проблемы изоморфизма -сепарабельных графов к вычислению группы автоморфизмов Г.Миллер (1980) доказал следующую теорему [30] (из которой, в частности, следует полиномиальность проверки изоморфизма графов ограниченной степени).

Теорема 4.10 Проблема изоморфизма -сепарабельных графов с фиксированным разрешима за полиномиальное время.

Ещё одно обобщение результата о проверке изоморфизма деревьев возникает из топологической теории графов. Пусть = (, ) – простой граф. Тогда его вложение в ориентированную поверхность (сферу с несколькими ручками) задаётся набором циклических упорядочений каждого множества (); в этой ситуации каждая упорядоченная пара вершин (, ) содержится в однозначно определённом цикле ( = 0, 1 =,..., 1 ), где для каждого = 0,..., 1 в циклическом упорядочении окрестности вершины пара (, +1 ) следует за парой (, 1 ) (сложение производится по модулю ). Неформально говоря, вложение позволяет "нарисовать" граф на поверхности так, что его рёбра пересекаются лишь по концам, а сама поверхность разбивается в объединение граней, т.е. областей, ограниченных Простой граф называется -связным, если связен каждый его подграф, индуцированный множеством { }, где | |.

описанными циклами. Род ориентированной поверхности (число ручек) определяется из формулы Эйлера-Пуанкаре | | || + | | = 2 2, где – множество граней и – число компонент связности графа. Родом графа называется наименьший род ориентированной поверхности, в которую этот граф можно вложить.

Графы рода 0 - это в точности планарные графы, т.е. такие, которые можно нарисовать на плоскости так, чтобы рёбра пересекались только по концам. Легко видеть, что любое дерево является планарным графом. Можно доказать, что 3-связный планарный граф имеет единственное с точностью до зеркального отражения вложение в плоскость. Это вложение можно построить за линейное время и использовать для проверки изоморфизма. В случае произвольного рода ситуация похожа: каждый 3-связный граф имеет не более, чем полиномиальное число "специальных" вложений рода. Множество всех таких вложений можно вычислить за полиномиальное время, а используя их – построить каноническую пометку графа. Эти идеи и были использованы в работе Г. Миллера (1980), где была доказана следующая теорема [28].

Теорема 4.11 Проблема изоморфизма графов ограниченного рода разрешима за полиномиальное время.

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

(Заметим, что матрица смежности простого графа симметрична и потому все её собственные значения вещественны.) Под кратностью спектра графа понимается максимальная кратность собственного значения его матрицы смежности. В крайнем случае, когда спектр равен единице, все собственные значения различны и, можно показать, что группа автоморфизмов графа является абелевой. Более того, в этом случае её, а на её основе и каноническую пометку графа, легко построить за полиномиальное время. Используя теорему 3.8 соответствующие алгоритмы обобщаются на случай ограниченной кратности спектра. Это и было сделано в 1982 г. Л. Бабаи, Д. Григорьевым и Д. Маунтом в [8]. Позднее в работе [16] этот результат был распространён на ориентированные графы с ограниченной кратностью Жордановых блоков матрицы смежности, а оценка сложности алгоритма стала полиномиальной не только при фиксированной кратности, но и в случае, когда кратность медленно растёт с ростом числа вершин.

Теорема 4.12 Изоморфизм двух -вершинных графов можно проверить за время (1), где – кратность спектра любого из них.

Граф = (, ) называется циркулянтом, если он допускает автоморфизм, циклически переставляющий все вершины. Если = {0,..., 1}, то это означает, что вершины графа можно перенумеровать так, что перестановка (0,..., 1) является его автоморфизмом. В случае, когда – простое число, можно доказать, что два циркулянта, допускающие этот автоморфизм, изоморфны в том и только в том случае, если изоморфизмом является одна из перестановок вида, где {1,..., 1} и умножение выполняется по модулю. Однако, для составных это не так. Тем не менее, следующий результат был получен C. Евдокимовым и И. Пономаренко в [4], и независимо М. Музычуком в [31].

Теорема 4.13 Проблема изоморфизма циркулянтов разрешима за полиномиальное время.

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

5 Проблема изоморфизма и когерентные конфигурации

5.1 Алгоритм Вейсфейлера-Лемана и когерентные конфигурации. Значительная часть эвристических алгоритмов проверки изоморфизма графов направлена на нахождение автоморфного разбиения (см. теорему 1.11). В основе таких алгоритмов обычно лежит некоторая процедура, уточняющая раскраску графа. Предполагается, что в начале работы раскраска графа тривиальна, а в конце даёт автоморфное разбиение. В настоящее время, однако, неизвестно ни одного алгоритма, который бы строил автоморфное разбиение за полиномиальное время.

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

Упражнение. Построить регулярный граф степени 3, у которого одна из вершин, скажем, содержится в некотором треугольнике, а другая вершина, скажем, не содержится ни в каком треугольнике.

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

Это и было предложено в работе Б. Вейсфейлера и А. Лемана (1968) [2].

Для описания соответствующего алгоритма удобно рассматривать категорию конфигураций, т.е. полных ориентированных раскрашенных графов: конфигурация на множестве представляет собой пару (, ), где – разбиение множества на цветные классы раскраски :, множеством цветов которой является начальный отрезок натурального ряда. Мы требуем лишь, чтобы (, ) = (, ),,,, т.е. чтобы цвета рёбер отличались от цветов вершин. Таким образом, каждый цветной класс

– есть бинарное отношение, которое можно интерпретировать как множество рёбер некоторого ориентированного графа с множеством вершин ; эти графы называются базисными. Изоморфизмы конфигураций понимаются как биекции множеств вершин, сохраняющих раскраску: каждый изоморфизм является одновременно изоморфизмом каждого базисного графа. Под группой автоморфизмов конфигурации понимается пересечение групп автоморфизмов базисных графов.

Заметим, что каждый ориентированный граф = (, ) однозначно представляется конфигурацией = (, ), где = {1,, }, т.е получается раскраской множества в три цвета: один – для пар отношения 1, представляющих вершины графа, и два – для раскраски рёбер и нерёбер. Следующий алгоритм стабилизации раскраски известен как алгоритм

Вейсфейлера-Лемана:

(1) для каждой пары вершин (, ) найдём строку (, ) = ((, ), (, ), 11,..., 1,..., 1,..., ), (25)

–  –  –

(4) если число цветов раскраски больше числа цветов раскраски, то полагаем := и переходим к шагу 1.

Заметим, что число цветов раскраски возрастает на каждой итерации алгоритма, оставаясь в то же время меньше, чем 2, где = | |. Поэтому алгоритм завершает работу за полиномиальное от время.9 Более того, каждый изоморфизм конфигураций, очевидно, сохраняет строки (, ), построенные на шаге 1 алгоритма, а потому и раскраску, определённую на шаге 3. По индукции отсюда получается следующее утверждение.

Предложение 5.1 Пусть и – конфигурации, полученные из конфигураций и с помощью алгоритма Вейсфейлера-Лемана. Тогда Iso(, ) Iso(, ).

Легко видеть, что для конфигурации = (, ), которая получается на выходе алгоритма Вейсфейлера-Лемана, выполнены следующие четыре условия (первые два из которых – следствие определения, а вторые два обеспечиваются шагами 1 и 3 соответственно):

(C1) – разбиение множества, (C2) 1 – объединение отношений из,

–  –  –

где () и () – окрестности вершин в базисных графах (, ) и (, ) соответственно.

Любая конфигурация, для которой выполняются условия (C1)–(C4), называется когерентной; элементы множеств и называются точками и базисными отношениями, а числа | |, || и – степенью, рангом и числом пересечений. Множество, для которого 1, В работе [11] была предложена модификация этого алгоритма, которая строит стабильную раскраску за время (3 log ). Улучшение этой оценки тесно связано с открытым вопросом о максимальном числе итераций алгоритма (как функции от ).

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

В действительности, объект, построенный Вейсфейлером и Леманом, был не когерентной конфигурацией, а её алгебраическим аналогом – алгеброй смежности, элементами которой являются комплексные линейные комбинации матриц смежности базисных графов (условие (C4) влечёт, что это множество является алгеброй). Такие алгебры они назвали клеточными. Независимо от этой конструкции к понятию когерентной конфигурации пришёл Д. Хигман (1970) [23]. Однако, для него мотивацией была теория групп перестановок (см.

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

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

Именно пусть Sym( ). Тогда каждая перестановка индуцирует перестановку (, ) (, ) множества 2. Обозначим через = Orb(, 2 ) множество орбит этой индуцированной группы. Для пары Inv() = (, ) очевидно, выполнены условия (C1)–(C3). Более того, для всех, и мы имеем равенство ( ()) = ( ). Отсюда получается, что (, ;, ) = (, ;, ) для всех и. Так что условие (C4) также выполняется и Inv() является когерентной конфигурацией. Каждое базисное отношение этой когерентной конфигурации вида 1, будучи орбитой группы (, 2 ), определяет орбиту группы. Это доказывает первую часть следующего утверждения.

Предложение 5.2 Множество фибр когерентной конфигурации Inv() совпадает с множеством орбит группы. В частности, эта конфигурация однородна тогда и только тогда, когда группа транзитивна.

Упражнение. Однородная когерентная конфигурация = (, ) называется примитивной, если 1 и – единственные отношения эквивалентности на множестве, которые являются объединениями базисных. Используя лемму 3.3 проверить, что когерентная конфигурация Inv() примитивна тогда и только тогда, когда примитивна группа.

Когерентные конфигурации и на и называются изоморфными, если существует биекция :, сохраняющая базисные отношения, т.е. отношение является базисным в тогда и только тогда, когда отношение = {(, ) : (, ) } является базисным в. Эта биекция называется изоморфизмом из на, а множество их всех обозначается через Iso(, ). Легко видеть, что группа Iso(, ) содержит нормальную подгруппу

Aut() = { Sym( ) : =, },

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

Теорема 5.3 Пусть – конфигурация и * – когерентная конфигурация, построенная из неё с помощью алгоритма Вейсфейлера-Лемана.

Тогда Aut() = Aut( * ).

Доказательство. Легко видеть, что каждое базисное отношение конфигурации является объединением некоторых базисных отношений конфигурации *. Поскольку каждый автоморфизм последней фиксирует каждое базисное отношение (как множество), отсюда следует, что Aut( * ) Aut(). Обратно, для каждого автоморфизма конфигурации имеем (, ) = (, ),,, где (, ) – строка, определённая на шаге 1 алгоритма Вейсфейлера-Лемана, см. (25). Поэтому = для каждого цветного класса раскраски, определённой на шаге 3. Рассуждая по индукции, мы докажем, что последнее утверждение справедливо и для раскраски, полученной на выходе алгоритма. Поскольку цветные классы этой раскраски совпадают с базисными отношениями конфигурации *, отсюда следует, что Aut( * ). Так что Aut() Aut( * ).

Следствие 5.4 Пусть – граф и – когерентная конфигурация, построенная из него с помощью алгоритма Вейсфейлера-Лемана. Тогда Aut() = Aut().

Когерентная конфигурация называется шуровой, если = Inv() для некоторой группы перестановок. В этом случае базисные отношения этой конфигурациями являются орбитами в её действии на 2, и потому Aut(). Отсюда следует, что конфигурация шурова тогда и только тогда, когда = Inv(Aut()). В общем случае, её шурово замыкание Inv(Aut()) содержит больше базисных отношений; один из первых примеров такой ситуации был построен Г. М. Адельсоном-Вельским, Б. Ю. Вейсфейлером, А. А. Леманом и И.А. Фараджевым в 1969 г. [1]. Отметим, что из утверждения (1) теоремы 5.5 (см. ниже) следует, что если бы все когерентные конфигурации были шуровыми, то изоморфизм графов можно было бы распознать за полиномиальное время с помощью алгоритма Вейсфейлера-Лемана.

Имеется ещё один тип изоморфизма когерентных конфигураций. Именно когерентные конфигурации и называются алгебраически изоморфными, если существует такая биекция :,, что =,,,,.

, Любая такая биекция называется алгебраическим изоморфизмом из на. Она индуцирует биекцию из множества всех объединений базисных отношений конфигурации в множество ( ) всех объединений базисных отношений конфигурации. При этом, как легко убедиться ( ) = ( ) и (1 ) = 1 для всех. Таким образом, алгебраически изоморфные когерентные конфигурации имеют не только одинаковые ранги, но и одинаковые степени. Последнее равенство позволяет доопределить также и на множестве всех объединений фибр так, что (1 ) = 1 для всех.

Отметим, что каждый изоморфизм Iso(, ) индуцирует алгебраический изоморфизм =, который определяется формулой =. Поэтому изоморфные когерентные конфигурации алгебраически изоморфны (однако, обратное утверждение неверно). Для произвольного алгебраического изоморфизма : мы полагаем

–  –  –

Это множество может быть пустым, но Iso(,, id ) = Aut().

Теорема 5.5 Каждая из следующих проблем полиномиально эквивалентна проблеме изоморфизма графов:

(1) SCLOS() : найти шурово замыкание когерентной конфигурации, (2) AUTCC() : найти группу автоморфизмов когерентной конфигурации, (3) ALISO() : для заданного алгебраического изоморфизма : 1 2 проверить непустоту множества Iso(1, 2, ).

Доказательство. Пусть – простой граф и – когерентная конфигурация, построенная из с помощью алгоритма Вейсфейлера-Лемана. Умея находить шурово замыкание Inv(Aut()) когерентной конфигурации, мы также умеем находить и его фибры. Однако по предложению 5.2 множество фибров совпадает с множеством орбит группы Aut() = Aut() и потому образует автоморфное разбиение графа. Таким образом, APART SCLOS и, следовательно, ISO SCLOS (26) по теореме 1.11. Далее, когерентная конфигурация Inv(Aut()) строится по образующим группы Aut() за полиномиальное время по лемме 3.1. Поэтому

SCLOS AUTCC. (27)

В силу (26) и (27) для завершения доказательства того, что проблемы ISO, SCLOS и AUTCC полиномиально эквивалентны, достаточно проверить, что AUTCC ISO. Однако, по теореме 5.3 алгоритм Вейсфейлера-Лемана даёт полиномиальное сведение проблемы AUTCC к проблеме нахождения группы автоморфизмов произвольной конфигурации, а последняя, как нетрудно видеть, полиномиально сводится к нахождению группы автоморфизмов графа (см.

конструкцию теоремы 1.5).

Для доказательства сводимости ALISO ISO пусть : 1 2 алгебраический автоморфизм. Выберем произвольное линейное упорядочение базисных отношений когерентной конфигурации 1 = (1, 1 ) и определим линейное упорядочение базисных отношений когерентной конфигурации 2 = (2, 2 ) так, что 2 2 (2 ) (2 ), 2, 2 2.

Тогда множество Iso(1, 2, ) непусто в том и только в том случае, когда найдётся изоморфизм конфигураций (1, 1 ) и (2, 2 ), сохраняющий порядок. Так что требуемое утверждение следует из упражнения на стр. 10.

Обратно, пусть 1 и 2 – простые графы и 1 = (1, 1 ) и 2 = (2, 2 ) – когерентные конфигурации, построенные из этих графов с помощью алгоритма Вейсфейлера-Лемана. Заметим, что если |1 | = |2 |, то конфигурации 1 и 2, а потому в силу предложения 5.1 и графы 1 и 2, не являются изоморфными. Таким образом, можно считать, что |1 | = |2 |.

Обозначим через биекцию из 1 в 2, сохраняющую цвета. Используя индукцию по числу шагов алгоритма Вейсфейлера-Лемана легко проверить, что если не является алгебраическим изоморфизмом когерентной конфигурации 1 на когерентную конфигурацию 2, то графы 1 и 2 не являются изоморфными. Таким образом, за полиномиальное время можно либо построить алгебраический изоморфизм, для которого в силу предложения 5.1 имеет место равенство Iso(1, 2 ) = Iso(1, 2, ), либо определить, что 1 2. Отсюда следует, что ISO ALISO, что и требовалось = доказать.

Когерентные конфигурации были использованы Л. Бабаи в работе [5] для доказательства верхней оценки на порядок произвольной унипримитивной группы перестановок. Использованный там метод показывает, что если 1 и 2 – примитивные когерентные конфигурации степени, то множество Iso(1, 2 ) можно построить за время ( log ).

Граф = (, ) называется сильно регулярным, если пара (, ), где = {1,, }, является когерентной конфигурацией. К многочисленным примерам сильно регулярных графов относятся и графы латинских квадратов, определённые на 24. Несмотря на то, что сильно регулярные графы являются хорошим тестом эффективности практических алгоритмов проверки изоморфизма графов, Д. Шпильман в [34] построил алгоритм, распознающий изоморфизм -вершинных сильно регулярных графов за время exp((1/3 log )).

5.2 Алгебраические леса. В этом параграфе изложение следует статье [18].

Прямая сумма. Пусть 1 = (1, 1 ) и 2 = (2, 2 ) – когерентные конфигурации, и – дизъюнктное объединение множеств 1 и 2. Не умаляя общности будем считать, что множества 1 и 2 также дизъюнктны. Положим = 1 2 { : =,, = 1, 2}, (28) где – множество фибров когерентной конфигурации. Тогда легко проверить, что пара = (, ) является когерентной конфигурацией; она называется прямой суммой 1 и 2 и обозначается через 1 2. Очевидно, что степень прямой суммы когерентных конфигураций является суммой степеней слагаемых, а множество её фибров состоит из фибров слагаемых.

Из определения также следует, что 1 = 1 и 2 = 2, где = (, )) и = { ( )2 = : }, и когерентная конфигурация является наименьшей когерентной конфигурацией на, обладающей этим свойством.

Более того, определяя прямую сумму 1 2 двух групп перестановок 1 Sym(1 ) и 2 Sym(2 ), как группу перестановок на, индуцированную естественным действием прямого произведения этих групп на этом множестве, получаем следующие равенства:

–  –  –

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

–  –  –

= 1, 2.

Сплетение.

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

,,.

=, (30) Будем говорить в этом случае, что семейства и согласованы. Тогда легко видеть, что = id и 1 = для всех,. Более того, каждая перестановка Sym() индуцирует алгебраический изоморфизм когерентной конфигурации = на себя, определяемый следующим образом:

: ( ),, где. Множество всех алгебраических изоморфизмов образует подгруппу = () группы алгебраических изоморфизмов когерентной конфигурации, изоморфную группе Sym(). Обозначим через множество каждый элемент которого есть объединение всех элементов множества, где – базисное отношение конфигурации. Можно доказать, что пара = Sym() = (, ) является когерентной конфигурацией; она называется сплетением семейства когерентных конфигураций с группой Sym() относительно семейства алгебраических изоморфизмов. Таким образом, каждое базисное отношение сплетения либо содержится в отношении эквивалентности ( )2 и получается объединением отношений,, при фиксированных и, либо получается объединением отношений,,, =, для фиксированных фибр и когерентных конфигурации и. Можно построить примеры нешуровых сплетений, в которых каждый операнд шуров. Однако, справедлив следующий аналог теоремы 5.6.

Теорема 5.7 Пусть = Sym() для некоторых согласованных семейств = { } и = { },.

Тогда для любого алгебраического изоморфизма : существуют и единственны согласованных семейств = { } и = { }, и подобия :,, такие, что = Sym(), = для всех и = для всех,.

Упражнение. Пусть – несвязный граф и – когерентная конфигурация, построенная из с помощью алгоритма Вейсфейлера-Лемана. Тогда является либо нетривиальной прямой суммой, либо нетривиальным сплетением. Здесь нетривиальность означает, что степень любого операнда строго меньше степени когерентной конфигурации.

Лесовидные когерентные конфигурации. Будем говорить, что когерентная конфигурация лесовидна, если она может быть получена из когерентной конфигурации степени 1 с помощью прямых сумм и сплетений. Простейшим примером лесовидной конфигурации является любая когерентная конфигурация ранга 2 (совпадающая со сплетением семейства конфигураций степени 1). Легко видеть, что она является когерентной конфигурацией, построенной из пустого (или полного) графа с по крайней мере 2 вершинами алгоритмом ВейсфейлераЛемана. Более общо, можно доказать, что для каждой лесовидной когерентной конфигурации = (, ) найдется лес10 с множеством листьев такой, что = { : }, где – множество базисных отношений когерентной конфигурации, построенной из алгоритмом Вейсфейлера-Лемана.

Теорема 5.8 Каждая лесовидная когерентная конфигурация является шуровой.

Доказательство. Приведем схему доказательства. Сначала используя индукцию по степени лесовидной конфигурации можно показать, что любой алгебраический изоморфизм этой конфигурации на другую когерентную конфигурацию индуцируется изоморфизмом. Здесь используется тот факт, что в силу лесовидности является либо нетривиальной прямой суммой, либо нетривиальным сплетением: в первом случае утверждение следует из теоремы 5.6, а во втором – из теоремы 5.7. Теперь та же индукция используется, но уже для доказательства шуровости. В случае прямой суммы шуровость следует из шуровости слагаемых, а в случае сплетения кроме шуровости когерентных конфигураций семейства требуется ещё, чтобы каждый алгебраический изоморфизм из семейства индуцировался изоморфизмом.

Однако, последнее было доказано выше.

Граф называется алгебраическим лесом, если когерентная конфигурация, построенная из него с помощью алгоритма Вейсфейлера-Лемана, является лесовидной.

Можно доказать, что класс всех алгебраических лесов включает все леса (и, в частности, все деревья) и более того:

(1) все кографы, т.е такие графы, которые не содержат индуцированной цепи на четырёх вершинах, Лесом называется дизъюнктное объединение деревьев.

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

Отметим, что за полиномиальное время можно легко распознать является ли данная когерентная конфигурация нетривиальной прямой суммой или нетривиальным сплетением. Используя это обстоятельство и полиномиальность алгоритма Вейсфейлера-Лемана можно построить алгоритм полиномиальной сложности, который определяет является ли данный граф алгебраическим лесом.

Теорема 5.9 Проблема изоморфизма алгебраических лесов разрешима за полиномиальное время.

Доказательство. По теореме 1.11 достаточно уметь строить автоморфное разбиение алгебраического леса. Однако, в силу предложения 5.4 и теоремы 5.8 оно совпадает с разбиением множества вершин графа на фибры когерентной конфигурации, построенной из него с помощью алгоритма Вейсфейлера-Лемана.

В заключение этого параграфа отметим, что эффективные алгоритмы проверки изоморфизма деревьев, кографов, интервальных графов и графов орцепей были построены в разное время, разными людьми и разными способами. Теорема 5.9 даёт единый алгоритм проверки изоморфизма для графов из всех этих классов, а теорема 5.8 вскрывает алгебраическую причину, почему такой алгоритм вообще существует. Однако, следует иметь в виду, что прямое использование алгоритма Вейсфейлера-Лемана не приводит к алгоритмам линейной сложности от размера графа.

5.3 Неэффективность комбинаторных алгоритмов. Алгоритм Вейсфейлера-Лемана уточняет разбиение квадрата исходного множества на бинарные отношения. Заменяя бинарные отношения на отношения фиксированной арности 2 мы приходим к -мерному алгоритму Вейсфейлера-Лемана, который стабилизирует раскраску множества следующим образом:

(1) для каждого кортежа = (1,..., ) и элемента найдем строку (, ) = ((, 2,..., ), (1,,..., ),..., (1,..., 1, )).

(2) положим () = ((), (, 1 ),..., (, )), где 1,..., – все элементы множества, упорядоченные так, что (, ) лексикографически не превосходит (+1 ) для всех.

(3) найдём однозначно определённую раскраску, для которой () ( ), если () ( ), и () = ( ), если () = ( ), (4) если число цветов раскраски больше числа цветов раскраски, то полагаем := и переходим к шагу 1.

Нетрудно проверить, что при = 2 это в точности алгоритм Вейсфейлера-Лемана, рассмотренный ранее. Далее, начиная с графа = (, ) можно определить начальную раскраску множества так, что если = (1,..., ) и = (1,...

, ) – два элемента этого множества, то () = (), тогда и только тогда, когда для всех, имеет место эквивалентности:

= = и (, ) (, ).

После нахождения стабильной раскраски множества с помощью -мерного алгоритма Вейсфейлера-Лемана мы можем определить раскраску множества 2 так, чтобы для всех,,, имела место эквивалентность:

(, ) = (, ) (,,..., ) = (,,..., ).

Нетрудно проверить, что конфигурация, отвечающая этой раскраске, является когерентной, и что Aut( ) = Aut() для всех. Более того, определим частичный порядок на множестве всех когерентных конфигураций на множестве так, что (, ) (, ) тогда и только тогда, когда ( ) ; в этом случае каждое базисное отношение меньшей когерентной конфигурации является объединением базисных отношений большей. Тогда = 1 2 · · · = +1 = · · · = = Inv(Aut()), (31) где = | | и – некоторое натуральное число. Таким образом, -мерный алгоритм Вейсфейлера-Лемана решает проблему изоморфизма графов (но за экспоненциальное время). Долгое время был открыт вопрос о том, верно ли, что число в формуле (31) не превосходит некоторой абсолютной константы или хотя бы имеет порядок (log ): в первом случае проблема изоморфизма графов решалась бы за полиномиальное время, а во втором - за время (log ).

К настоящему времени был получен отрицательный ответ на оба вопроса [12, 15].

Теорема 5.10 Существует константа 0 1 такая, что всех достаточно больших натуральных чисел имеются -вершинные графы, для которых Inv(Aut()) при =.

Значительная часть известных алгоритмов проверки изоморфизма графов, не использующих группы перестановок, условно делится на две части в соответствии с тем, используется или нет в них линейная алгебра (в последнем случае, алгоритмы могут использовать собственные значения, отвечающие им собственные вектора или собственные подпространства матрицы смежности исходного графа). В любом случае, чаще всего можно построить соответствующий алгоритм для когерентных конфигураций исходных графов, который пытается построить шурово замыкание. Во всех проанализированных случаях (см. обзор [17] и недавнюю работу [32]) оказалось, что когерентная конфигурация, получающаяся на выходе алгоритма, мажорируется когерентной конфигурацией, которая за то же время строится

-мерным алгоритмом Вейсфейлера-Лемана для подходящего. Однако в этом случае, надежда на то, что построенный алгоритм проверяет изоморфизм графов за полиномиальное время, является несостоятельной в силу теоремы 5.10.

Список литературы [1] Г. М. Адельсон-Вельский, Б. Ю. Вейсфейлер, А. А. Леман, И.А. Фараджев, Об одном примере графа, не имеющего транзитивной группы автоморфизмов, ДАН СССР, 185 (1969), вып. 5, 975–976.

[2] Б. Ю. Вейсфейлер, А. А. Леман, Приведение графа к каноническому виду и возникающая при этом алгебра, Сб.ВИНИТИ, сер.2, 9 (1968), 12–16.

[3] В. Н. Земляченко, Н. М. Корнеенко, Р. И. Тышкевич, Проблема изоморфизма графов, Зап. Научных Сем. ЛОМИ, 118 (1982), 83–158.

[4] С. Евдокимов, И. Пономаренко, Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время, Алгебра и анализ, 15 (2003), 6, 1–34.

[5] L. Babai, On the order of uniprimitive permutation groups, Annals of Math., 113 (1981), 553–568.

[6] L. Babai, Automorphism groups, isomorphism, reconstruction, in R. L Graham, (ed.) et al., Handbook of combinatorics. Vol. 1-2. Amsterdam: Elsevier (North-Holland), (1995), 1447– 1540.

[7] L. Babai, P. Codenotti, Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time, Proc. Ann. Symp. Found. Comput. Sci, 2008, 667–676.

[8] L. Babai, D. Y. Grigor’ev, D. M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proc. 14th ACM STOC, 1982, 310–324.

[9] L. Babai, W. Kantor,E. M. Luks, Computational complexity and the classification of finite simple groups, Proc. 24th Ann. Symp. Found. Comput. Sci, 1983, 162–171.

[10] L. Babai, and E.M. Luks, Canonical labeling of graphs, Proc. 15th ACM STOC, (1983), 171– 183.

–  –  –

[12] J. Y. Cai, M. Frer, N. Immerman, An optimal lower bound on the number of variables for u graph identification, Combinatorica, 12 (1992), 389–410.

[13] J. D. Dixon, B. Mortimer, Permutation groups, Graduate Texts in Mathematics, No. 163, Springer-Verlag New York, 1996.

[14] S. Evdokimov, M. Karpinski, I. Ponomarenko, On a New High Dimensional Weisfeiler-Leman Algorithm, Journal of Algebraic Combinatorics, 10 (1999), 29–45.

[15] S. Evdokimov, I. Ponomarenko, On highly closed cellular algebras and highly closed isomorphisms, Electronic J. of Combinatorics, 6 (1999), #R18 (MR2000e:05160).

[16] S. Evdokimov, I. Ponomarenko, Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks, Combinatorica, 19 (1999), 321–333.

[17] S. Evdokimov, I. Ponomarenko, Permutation group approach to association schemes, European Journal of Combinatorics, 30 (2009), 6, 1456–1476.

[18] S. Evdokimov, I. Ponomarenko, G. Tinhofer, Forestal algebras and algebraic forests (on a new class of weakly compact graphs), Discrete Mathematics, 225 (2000), 149–172.

[19] S. Friedland, Coherent algebras and the graph isomorphism problem, Discrete Applied Math., 25 (1989), 73–98.

[20] M. Furst, J. Hoprcoft, E. Luks, Polynomial time algorithms for permutation groups, the 21st Symp. Found. Comput.Sc1., 1980, p.36–41.

[21] G. Gati, Further annotated bibliography on the isomorphism disease, Journal of Graph Theory, 3 (1979), 95-–109.

[22] M. K. Goldberg, A nonfactorial algorithm for testing isomorphism of two graphs, Discrete Appl. Math., 6 (1983), 229–236.

[23] D. G. Higman, Coherent configurations 1., Rend. Mat. Sem. Padova, 44 (1970), 1–25.

–  –  –

[25] E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J.

Comput. Syst. Sci., 25 (1982), 42–65.

[26] R. Mathon, A note on the graph isomorphism counting problem, Inform. Process. Lett., 8 (1979), 131–132.

[27] G. L. Miller, On the log isomorphism technique, Proc. 10th ACM STOC, 1978, 51–58.

[28] G. Miller, Isomorphism testing for graphs of bounded genus, Proc. 12th ACM STOC, 1980, 225–235.

[29] G. Miller, Isomorphism of k-Contractible Graphs. A Generalization of Bounded Valence and Bounded Genus, Information and Control, 56 (1983), 1–20.

[30] G. Miller, Isomorphism of Graphs Which are Pairwise k-Separable, Information and Control, 56 (1983), 21–33.

[31] M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc., 88 (2004), 1–41.

[32] A. Rahnamai Barghi, I. Ponomarenko, Non-isomorphic graphs with cospectral symmetric powers, Electronic Journal of Combinatorics, 16 (2009), #R120.

[33] R. C. Read, D. G. Corneil, The Graph Isomorphism Disease, J. Graph Theory, 1 (1977), 339–363.

[34] D. A. Spielman, Faster isomorphism testing of strongly regular graphs, Proc. 28th ACM STOC, 1996, 576-–584.

[35] B. Weisfeiler (editor), On construction and identification of graphs, Springer Lecture Notes, 558, 1976.

[36] H. Wielandt, Finite permutation groups, Academic press, New York - London, 1964.

[37] H. Wielandt, Permutation groups through invariant relations and invariant functions, Lect.

Похожие работы:

«А. Агаджанян ГОСУДАРСТВО РЕЛИГИЯ ЦЕРКОВЬ в р о с с и и и з а р уб е ж о м В минувшем году в Издательстве Санкт-Петербургского университета вышел в свет авторский словарь "Социология религии" (Смирнов М. Ю. Социология религии: Словарь. СПб.: Изд-во С.-Петерб. ун-та, 2011. Подробная рецензия на словарь представлена в рубрике "Рецензии" данного...»

«Topical issues of contemporary international relations В.Ю. Вершинина КОНФЛИКТОГЕННЫЙ ПОТЕНЦИАЛ БАЙКАЛА В XXI ВЕКЕ LAKE BAIKAL: POTENTIAL FOR CONFLICTS IN THE 21st CENTURY В статье рассматривается Байкал как вероятный источник конфликтов в XXI столетии. Анализируется совок...»

«Электронный журнал "Труды МАИ". Выпуск № 78 www.mai.ru/science/trudy/ УДК 623.74: (534.1+539.4) Динамическое деформирование конструкции авиационного изделия при аварийном соударении с преградой Вербицкий А. Б.,* Сидоренко А. С.** Московский авиационный институт (национальный исследоват...»

«"Газпромбанк" (Акционерное общество) Банк ГПБ (АО) УСЛОВИЯ ПРЕДОСТАВЛЕНИЯ БАНКОМ ГПБ (АО) БРОКЕРСКИХ УСЛУГ С ОТКРЫТИЕМ И ВЕДЕНИЕМ ИНДИВИДУАЛЬНОГО ИНВЕСТИЦИОННОГО СЧЕТА Москва СОДЕРЖАНИЕ 1. Общие положения 2. Перечень терминов и определений 3....»

«Правила Программы лояльности "Автокарта" утверждены протоколом Правления Банка 15.12.2015 №81 новая редакция утверждена протоколом Правления Банка 26.10.2016 №66 Настоящие правила Программы лояльности "Автокарта" (далее – Правила) определяют порядок пред...»

«УДК 37.037.1 Лушневский А.К. РАЗВИТИЕ СПЕЦИФИЧЕСКИХ КООРДИНАЦИОННЫХ СПОСОБНОСТЕЙ В ПРОЦЕССЕ ФИЗИЧЕСКОЙ ПОДГОТОВКИ ВОЕННОСЛУЖАЩИХ Определены специфические координационные способности, проявляемые военнослужащими в...»

«УДК 111 ПРОБЛЕМА СУБЪЕКТА В ФЕНОМЕНОЛОГИЧЕСКОЙ ФИЛОСОФИИ Рудковский С. В. Научный руководитель д-р филос. наук, проф. Кудашов В. И. Сибирский федеральный университет В центре нашего исследования находится субъект как категория философии, его осмысление, произошедшее в феноменологической философии. В качестве объекта рассмотрения выступают "...»

«Градиентные методы обучения Логистическая регрессия (LR) Балансировка ошибок и ROC-кривая Метод опорных векторов (SVM) Линейные методы классификации К. В. Воронцов vokov@forecsys.ru Этот курс доступен на странице вики-ресурса http://www.MachineLearnin...»

«Женщина под сенью ислама Д-р Абдур-Рахман аш-Шиха Перевод и адаптация русского текста: Надыров Арман Женщина под сенью ислама © W.ISLAMNDCO info @islamland.com Женщина под сенью ислама Содержание Введение 5 Раскрепощение женщины 7...»

«+7 (495) 223-46-50 +7 (812) 448-38-90 +7 (8636) 237-836 www.hostcms.ru info@hostcms.ru support@hostcms.ru HostCMS — удобство управления сайтом в любой точке мира. Система управления сайтом HostCMS v. 6 Руководство по установке Содержание Содержание Общие сведения Системные т...»

«ОцЕНОчНАя зАВИСИМОСть кАк ВОзМОЖНОЕ пОСЛЕДСтВИЕ СОцИАЛьНЫХ ОЖИДАНИЙ Н. Н. Ткаченко В статье дается определение оценочной зависимости и раскрываются основные причины ее возникновения, среди которых могут быть социальные ожида...»

«УДК 811.111:82-398.2 М. В. Рыжих ст. преподаватель каф. стилистики английского языка фак-та ГПН МГЛУ; e-mail: burun@post.ru ГИБРИДНЫЕ СЕМИОТИЧЕСКИЕ ЕДИНИЦЫ В АВТОРСКОЙ АНГЛОЯЗЫЧНОЙ СКАЗКЕ Семиотиче...»

«Приложение №4 к Условиям открытия и обслуживания расчетного счета Перечень тарифов и услуг, оказываемых клиентам подразделений ПАО Сбербанк на территории Кемеровской области (действуют с 01.12.2016) Стоимость услуги1 Наименование услуги в рублях в иностранной валюте2 РАСЧЕТНО-КАССОВОЕ ОБСЛУЖИВАНИЕ СЧЕТОВ В ВАЛЮТЕ РФ...»

«Максим Валерьевич Кисляков Быть войне! Русы против гуннов Серия "Русь изначальная" Текст предоставлен издательством http://www.litres.ru/pages/biblio_book/?art=7121510 Максим Кисляков. Быть войне! Русы против гуннов...»

«1 Проект Венера | Часто задаваемые вопросы Проект Венера Часто задаваемые вопросы Вопрос 1. Что такое Проект Венера? Проект Венера — это организация, которая предлагает реальный план действий для социальных преобразований, направленных на достиже...»

«Муниципальное бюджетное общеобразовательное учреждение города Кургана "Гимназия № 47" 1968-2013 Сборник к юбилею "Ода любимой гимназии" Этакие другие родители. Анастасия Гуцелюк, Ученица 8В класса Наша школа. Да. Сколько времени прошло, а я до сих пор помню, как пошла в первый класс! Ст...»

«Роль дисфункции слуховой трубы в патогенезе хронического гнойного среднего отита. С. С. Зарубин Кафедра оториноларингологии СГМУ Хронический гнойный средний отит – хроническое воспалительное заболевание среднего уха, характеризующееся наличием стойкой перфорации барабанной перепонки, периодической или...»

«Новый имидж. Прежнее качество. Теперь Mobil Ultra вместо Esso Ultra. Содержание Вступительное слово Скотта Ховарда Интернет-поддержка Единый бренд, единая цель Медиаплан В ногу со временем 5 Беспроигрышное предложение 6 Н...»

«ХОЛОДНЫЕ ЗАКУСКИ гр. руб. Ассорти мясное 200/50 320 /колбаса копченая, говядина копченая, язык отварной,карбонад/ Ассорти мясное "Национальное" 190/60/5 330 /казылык, куриный рулет,язык отарной, говядина копченая/ Ассо...»

«RU B 89090-5 Информация Встраиваемый для пользователя духовой шкаф Указания по использованию настоящего руководства Инструкции по технике безопасности ! Пошаговые инструкции Полезные советы Содержание Для вашей безопасности Описание духового шкафа Блок элек...»

«МИНИСТЕРСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ДЕЛАМ ГРАЖДАНСКОЙ ОБОРОНЫ, ЧРЕЗВЫЧАЙНЫМ СИТУАЦИЯМ И ЛИКВИДАЦИИ ПОСЛЕДСТВИЙ СТИХИЙНЫХ БЕДСТВИЙ Академия Государственной противопожарной службы ЛОГИКА ТЕМАТИЧЕСКИЙ ПЛАН ПЛАНЫ СЕМИНА...»

«1 Баланс-Библиотека Выпуск № ПР-5 "НДС: ситуации из практики" Стр.1 Баланс-Библиотека Выпуск № ПР-5 "НДС: ситуации из практики" Стр.1 Баланс-Библиотека Выпуск № ПР-5 "НДС: ситуации из практики" Стр.1 Баланс-Библиотека Выпуск № ПР-5 "НДС: ситуации из практики" Стр.1 АННОТА...»

«ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Питание является основой жизни, главным фактором, определяющим здоровье, долголетие и работоспособность человека. При любых нарушениях питания резко снижается способность противостоять неблагоприятным воздействиям окружающей среды, стрессам, повышенным умственным и физическим нагрузкам. Сегодня, по мнению...»

«Отчёт о работе городской инновационной площадки за 2013 год Обеспечение непрерывного образования, эффективной социализации и достойного трудоустройства лицам с ограниченными возможностями здоровья на основе со...»

«А. Н. Чумиков ИМИДЖ – РЕПУТАЦИЯ – БРЕНД: традиционные подходы и новые технологии Сборник статей Москва-Берлин УДК 659 ББК 65.05 Ч-90 Чумиков, А. Н. Ч-90 Имидж – репутация – бренд: традиционные подходы и новые технологии : сборник статей / А. Н. Чумиков – М.-Берлин: Директ-Медиа, 2015...»

«Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Международная Академия менеджмента International Academy of Management А.Н. Асаул, И.В. Денисова, Ю.Л. Матвеев, В.И. Фролов УПРАВЛЕНИЕ ФИРМОЙ НА ОСНОВЕ РАЗРАБОТКИ СТРАТЕГИЙ ЕЕ РАЗВИТИЯ Под редакцией действитель...»

«Александр Фадеев "Молодая Гвардия" Вперед, заре навстречу, товарищи в борьбе! Штыками и картечью проложим путь себе. Чтоб труд владыкой мира стал И всех в одну семью спаял, В бой, молодая гвардия рабочих и крестьян! Песня молодежи Глава первая Нет, ты только посмотри, Валя, что это за чудо! Прелесть. Точно изваяние, но из какого чудесного матер...»

«УДК 316.77 Вестник СПбГУ. Сер. 12. 2013. Вып. 1 В. В. Сибирев 1 СОЦИАЛЬНО-КОММУНИКАТИВНЫЕ АСПЕКТЫ УПРАВЛЕНИЯ ИМИДЖЕМ ВУЗА Введение Изучением имиджа организаций занимаются такие науки, как маркетинг, связи с общественностью, менеджмент и социология. Каждая наука рассматривает свои аспекты формирования имиджа организаци...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.