Прямой алгоритм проверки изоморфизма графов

ПРЯМОЙ алгоритм ПРОВЕРКИ ИЗОМОРФИЗМА ГРАФОВ

А.В. Пролубников Омский государственный университет

Аннотация

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

Введение

Задача изоморфизма графов (ИГ) принадлежит к задачам, относительно которых нет ясности: являются ли они полиномиально разрешимыми или нет [1], тогда, как известно, эта задача полиномиально разрешима для некоторых классов графов. В частности для планарных графов, графов с ограниченной степенью вершин, графов с ограниченной кратностью собственных значений из спектра матрицы смежности [2], [3], [4] и некоторых других классов графов построены эффективные алгоритмы решения этой задачи.

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

Алгоритм, представленный в [5], работает со спектральными характеристиками графов и является полиномиальным алгоритмом решения задачи ИГ с наиболее широким классом применения. Но этот класс не покрывает определяемых спектром графов, которые попадают в область эффективного применения предлагаемого алгоритма. Граф называется определяемым спектром (ОС-графом), если ему изоморфен любой граф с таким же спектром матрицы, представляющей граф. Спектр матрицы графа так же называют спектром графа.

Спектр графа не является его полным инвариантом. Так, почти все деревья и сильно-регулярные графы не являются определяемыми спектром. Вместе с тем, спектр содержит в себе разнообразную информацию о структуре графа [6] - такую как число ребер в графе, степенная последовательность графа, род графа и др., что может быть использовано при построении эвристик для решения задачи ИГ. Алгоритм спектрального расщепления [7], работает не напрямую со спектром графа, а со следующим, связанным со спектром, инвариантом:

5 (о)=(( *, ПI 2,-№ п),

где Xк - собственные значения модифицированной

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

удалением / -ой вершины; произведения берутся по всем значениям из спектров. Будем называть граф определяемым спектрами графа и подграфов (ОС2-графом), если ему изоморфен любой граф с таким же значением 5.

Как показывает эксперимент, многие графы, которые не являются ОС-графами, например, деревья являются ОС2-графами. Тогда как всякий ОС-граф является ОС2-графом.

В задаче проверки изоморфизма графов даны два графа ОА и Ов с множествами вершин V(ОА ),

V(Ов) и ребер Е(ОА ), Е(Ов). Мощности множеств вершин и ребер графов равны. Требуется определить, существует ли такое биективное отображение (изоморфизм) ф: VA ^ Vв, что

(/, ]) е Е(Оа ) » (ф(/), ф(])) е Е(Ов),

и представить его, если графы изоморфны.

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

=

[1,(i, j) е Ea , I 0, иначе,

в0 = (Ьу) - матрица смежности графа О в .

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

Алгоритм является прямым, то есть решение производится без использования схемы рекурсии с возвратом, на которой основаны наиболее извест-

ные алгоритмы решения задачи ИГ без каких-либо ограничений на структуру проверяемых на изоморфизм графов - алгоритмы и11тап, МЛиТУ и УГ, экспоненциальные для общего случая задачи.

Алгоритм

Пусть А0 - матрица смежности графа ОА = (УА, ЕА), Б^ - диагональная матрица следующего вида:

0

й,,

0 0

где й1 = ^ а° + й = й1 + й, й -

максимальная сте-

1=1

пень вершин в графе Оа , й1 - степень вершины ' е УА. Матрица БВстроится аналогично в соответствии с матрицей В0. Алгоритм работает с матрицами следующего вида:

А = Л + Вк

в = в0 + Бв1

Матрицы вида (1) - положительно определенные матрицы с диагональным преобладанием. Матрицами графов далее будем называть матрицы вида (1). В ходе работы алгоритма производится возмущение матриц графов при помощи следующих матриц:

"0 ... 0 ... 01- 1

Ек =

- к

0 ... 0 ... 0]- п

На I -ой итерации будем производить следующие возмущения матриц графов:

А' := А'-1 + еЕ', В' := В'-1 + еЕ'', где ' выбирается так, что (О ) = £ (О ). Если Оа и ОВ - ОС2-графы, и ОА изоморфен ОВ , то проведение таких возмущений возможно, поскольку имеет место очевидная лемма.

Лемма 1. Пусть ОА и ОВ - изоморфные ОС2-графы, Р - матрица перестановки, соответствующая изоморфизму ф: Ув ^ УА . Пусть А' и В' -матрицы, получаемые из А и В возмущениями их диагональных элементов в соответствии с последовательностями {'}"=1 и {к' }"п=1, где ф(kj) = ' . Тогда

А = РВР- » V' А' = РВ'Р-.

Обращение матриц производится путем решения систем линейных уравнений А'х = , В'х = , где

{ej }"п=1 - стандартный базис в К". Пусть хк = (хк1,...,хы) - к -й вектор-столбец матрицы (А' )-1. Тогда если графы ОА и ОВ изоморфны, и ф -изоморфизм ОА на ОВ , то:

уф

_У ф(") Ф(1) Пусть

уф

У ф(' )Ф( о

'ф

Уф

Уф

ф

Л' к/ П к

к=1 I к=1

а К(А) = {Л.,...,Л' } - это набор неповторяющихся значений Л,, для матрицы А . Если | К(А) |= п , то есть если все диагональные элементы обратной матрицы к матрице А графа - разные, и ОА и ОВ изоморфны, то, очевидно, изоморфизм может быть установлен без проведения возмущений по следующему правилу:

' = ф(') Л' = Л'.

Докажем следующую лемму.

Лемма 2. Пусть А' = А + еЕ', А'х1 = е,, Л' = х''. Тогда может быть выбрано такое е, что Л( Ф Л' для любого ' Ф ' .

Доказательство. Пусть А - алгебраическое дополнение элемента а матрицы А .

А,

аег а

Поскольку элемент а и матрицы А - единственный изменяемый в ходе возмущения матрицы элемент, то А' = А", тогда как для любого ' Ф' получаем А'м = А' + еАн' , где Аи - - определитель подматрицы матрицы А , получаемой удалением ее ' -ой строки, ' -го столбца, ' -ой строки и ' -го столбца. Изменение определителя при возмущении следующее: detА' = detА +еАи. Получаем, что при надлежащем выборе е для любого ' Ф'

л =. A

A

= Л,.

где xj е Rk (A1), x(f е R, (A1), x(f е R, (A1). Будем

1 det A + sA.. det A + sA..

Лемма доказана.

Учитывая леммы 1 и 2, можно утверждать, что не более чем за n последовательных согласованных возмущений матриц изоморфных ОС2-графов мы можем добиться того, что

| R(An°)|=|R(Bn°)|= n , где n0 - необходимое число возмущений, n0 < n .

Принципиальная схема алгоритма

Шаг 0. i := 1, A0 := A , 5o := B .

Шаг 1. Если | R(A-1) |= n , то перейти на шаг 3, иначе перейти на шаг 2.1.

-я итерация алгоритма:

Шаг 2.0. Выбор е.

Шаг 2.1. A := Ai-1 +еЕ.

Шаг 2.2. Поиск j т. ч.

S(GA ) = S(GBi-1 +E ) .

Шаг 2.3. Если j не найден, то, либо поданные на вход графы не изоморфны, либо - не являются ОС2-графами. Работу алгоритма завершить, иначе перейти на следующий шаг.

Шаг 2.4. i := i +1. Перейти на шаг 1.

Шаг 3. Установить изоморфизм по правилу

i = ф( 1) » Л.. = Л i.

Вычислительная эффективность алгоритма

Локализация элементов множества R

Пусть R(A( 1 >) = {л(1 Лp>} - набор R к j -ой итерации. Обозначим решение системы уравнений AJx = ek, как x'kJ-1, и определим множества R¡ (A(1)) как

R(A1) = {x(f|x(f = Л(1>},i = Vp.

Рассмотрим множества R¡ (A1) в процессе производимых в ходе работы алгоритма возмущений матрицы A . Будем говорить, что Rt (A1 -1) расщепляется на 1 -ой итерации алгоритма, если

x1-1) е R¡ (A1 -1) , |R¡ (A1 -1)|> 1 для некоторого i , но

x1 е Rt (A1), и | Rk (A1) |= 1.

Положим,

д(1) = |vO') _ vO')| kl k1k1 44 '

рассматривать А(ку как расстояние между множествами Як (Ау) и Я, (Ау).

Числом обусловленности матрицы А называется следующая величина ц(А):

|(A) = sup

xí0,^t 0

где Щ - евклидова норма вектора в Я". Пусть Хшах -

наибольшее собственное значение матрицы А, Хшт - наименьшее.

ЧН1/1"

x

x *0

¡;í0

x m

< ж.

Хшт ф 0 , поскольку А - положительно определенная матрица.

Рассмотрим систему (А + С)у = /, полученную из системы Ах = / возмущением А при помощи матрицы С . Пусть

1И11

где

<0.

x*0 x

Ца| = X шах для положительно определенной матрицы А [8]. Имеет место следующая теорема [8].

Теорема 1. Если А) < 1, то

Для числа обусловленности симметричной матрицы выполняется [8]:

П

Х

где

П( A) = max

Х( A) = min

aii +

и

/ Л

На у -ой итерации акк = ё + ёк + ек, где ек - значение возмущения к -го диагонального элемента А , и ек = 0 если к < ] . Пусть / - номер строки, на которой достигается ц(А), /2 - номер строки, на которой достигается %(А). Имеем

п(А) = а.. + е. +£| а.] |= й + е. + й. +

]=1

+й = й + е. + й + й = 3й + е. ,

п

Х(А) = ау2 +е'2 +Х| а4] |=

]=1

= й + е , + й, - й, = й + е ( .

'2 '2 '2 '2

Следовательно,

П( А) = 3й +е,;

ц(А) < -

^ ' х(А) й + е. Если е. = 1/пр , е^ = 1/пР2 , где р1, р2 е Ж, то 3й + е. = 3й +1/пр- =

А) <

й + е,.

й +1/ л

3йпР1 +1 р р 4йпР1 „  < пР2 Р1-= 4 .

йпр2 +1

йпр2

Таким образом, в нашем случае утверждение теоремы 1 принимает следующий вид: Если 9< 1/4, то

' - х < <

4

1 - 49'

х .

Для гарантированного выделения х] ' из К' (А]-1) на ] -ой итерации возмущения должны быть достаточно малы, поскольку необходимо, чтобы после возмущения х] -1 был достаточно удален от

всех остальных значений х'-1 в смысле введенного расстояния А.

Из (2) следует, что

||х(]) - х(]-1)|| < 49(е]) I|х(]-1)"

1 - 49(е . )" '

Поскольку

\\А]-1 \\А]

А]-1

мы можем положить

е..

9(е ]) = ,

Полагая е] = 1/пр , получаем

х(]) - х(]-1) <

4/ п

4/ п

|а] - 4"р

4

\А]\пр - 4'

Л ]-1) -

\\А]\\пр

л ]-1)

Имеем

ц( А1 -1) =

< 4.

где Хтах - максимальное собственное значение А]-1, Хт1п - минимальное. По теореме Гершгорина [9] Xтах > й. Учитывая, что Xт1п < ||А]-11|, получаем

||А]>Хт,п >Хта^/4 > й/4.

Таким образом, из (3) следует 20

х(]) - х(]-1) <-

„

йпр '

Так как все собственные значения А] не меньше 1, и ||ек|| = 1 для любого к, то ||х']-1)|| < 1. Из (3) следует, что для любого ' 20

йпр

х(]) - х(]-1) <-

ЫР - х

следовательно, для любого '

ЫР - х(/-1) <

20

йпр

Неравенство (4) дает оценку локализации векторов из множеств К1 (А]) в процессе работы алгоритма.

Расщепление множеств Я1

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

Пусть х'

К' (А1 ) для некоторого ', то

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

Теорема 2. Если -1) = х]-1) и 0 <е] < 1, то 1

х]) - х(]л >

" ]] \ 1" Л 2

3"й

Доказательство. Пусть А = А

- л]-1

А' = А]

х< = х(]-1),

х' = х(]),

= xС.j-1), х' = xС.j). Если

х' = рх', то х'] = х'и .

А

х =-А_

11 ^ А''

А

аег А'

После возмущения

аег А' = аег А + еАп, А!-^. = Ау ,

так как а.. - единственный изменяемый элемент А на итерации алгоритма. Поскольку

А = А +е А п.,

и А,, = А. , так как х, = ху, получаем А'.

I ху - х/, 1=

А

^А' ^А'

А.

А, +еА, п.-

^ А'

аег А'

еуА,, у

аег А + е.. А..

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

нк и акк1-Х1 а«1 = ёк >0,;'=1

где

ё' =

ё + ек, если 1 < к < у,

ё, если 1 < к < у. Следовательно,

Л, уу ^ Н1 х — Х HJ Х-х Нп =

= ё'х — х ё' , х — х ё'у х — х > ё"-2,

черта сверху означает невключение в произведение.

С другой стороны, по теореме Гершгорина максимальное собственное значение Xшах матрицы А можно оценить так:

Хшах < 3ё + шахе, < 3ё +1,

ш 1< к < у к

если ек < 1 для любого к. Поэтому

<1е1 А =ПХк <Хшах <

к=1

Ау^ИXк <Хш-аХ <

к=1

Пусть Хшах - максимальное собственное значение подматрицы, получаемой из А удалением строк и столбцов с номерами , и у . Хшах <Хшах [9]. Используя (6), (7) и (8), из (5) получаем:

| х' - х у |= еуЛ-уу >

у уу

ц"-2

е уё"

> (3ё +1)" + еу (3ё +1)"-1 >

е уё"-2

(3ё )"+' + еу (3ё)"

то есть

хС) - х(уЦ >-

1

3"ё

Теорема доказана.

Пусть решение систем линейных уравнений Аух = ек и в'х = ек (у, к = 1, п) осуществляется методом Гаусса-Зейделя. Метод Гаусса-Зейделя позволяет оценить необходимую длину мантиссы используемых машинных чисел. В действительности не принципиально, каким методом мы решаем системы уравнений, необходимо только, чтобы решение находилось с нужной точностью за приемлемое время. Имеет место [10] следующая теорема.

Теорема 3. Пусть

X1 а,у |< у 1 а,,1, у < ^

у *'

для каждого , = 1, п . Тогда

где х - точное решение системы уравнений Ах = Ь , х* - приближенное решение этой же системы уравнений на 5 -ой итерации метода Гаусса-Зейделя.

Если А = Ау, то у < 1/2 . Следовательно, на 5 -ой итерации метода Гаусса-Зейделя

1

х,, -х и < \х, -х, 11<-

|х„ - у <1 |ху - х5 II < — 50 \ у и\ II у у II 2''

где 5 - ошибка начального приближения. Если

е у

у

чаем

= 1/пр на у -ой итерации, то, учитывая (9), полу-1

х 1) - х(Л >

Г у Хп Г Ш Л2

3"ё

Значит, если

1

50 <

1

3"ё

может быть зафиксирована

то разница х) - х^

машинными числами с длиной мантиссы, не превышающей п . Оценим количество итераций метода

Гаусса-Зейделя 5, необходимых для фиксирования этого значения.

Формула (10) эквивалентна

3nd2

Логарифмируя (11), получаем

n log2 3 + log2 d2 (3dnp +1) + log2 5° < 5 -1,

то есть число необходимых итераций метода Гаусса-Зейделя может быть оценено как

5 > n log23 + p log2 n + 3log2 d + log2 5° + 3 .

Пусть p > 0 определяет значение возмущения ej = 1/np . Пусть xjj-1) - значение, выделяемое из R (Aj-1) на j -ой итерации. Выберем p так, что

20 < Д dn p n

то есть

1 20 ,

p > log+ ^

d Д

где Д = min Д [j).

k il

Из (4) следует, что для любого i

j - хУ}\ <-<

20 Д

n

dn

p

Получаем 1

3nd

< X/5 - xj Ч <-

после ] -ой итерации. Это означает, что на ] -ой

итерации мы можем выбрать такое возмущение, которое давало бы выделение х]]-1) из содержащего его

множества К (А]-1) (если его мощность не равна 1),

фиксируемое при помощи машинных чисел с длиной мантиссы равной п при сохранении локализации значений х„, ' = 1, п . То есть могут быть заданы интервалы, в пределах которых будут происходить расщепления множеств К . Возмущения могут проведены таким образом, что после выделения х]] из некоторого К (А]-1), хм не попадает на следующей

итерации в другое такое множество с мощностью отличной от 1.

В результате, если для решения систем линейных уравнений производится число итераций метода Гаусса-Зейделя, определяемое (12), то при п0 < п

мы получаем | К(Ап°) |= п , и расщепление элементов из К фиксируется машинными числами с длиной мантиссы, не превышающей п .

Общая вычислительная сложность алгоритма

На каждой итерации алгоритма мы проводим вычисление наборов К для обоих графов, для чего мы обращаем матрицы графов. Для обращения матриц необходимо решить 2п систем линейных уравнений. Пусть 0( Жх) - число элементарных машинных операций, которые необходимо совершить для решения систем линейных уравнений с заданной точностью. Тогда сложность процедуры обращения матриц составит 2п • 0( Жх).

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

2п • 0

Оценим 0(Ых) для метода Гаусса-Зейделя. На ] -ой итерации алгоритма, находя е), мы вычисля-

ем p такое, что 20/dnp <Д./n, где Дj = min Д

то есть

p = log n

16

d Д..

+1 .

После чего, в соответствии с (12), выполняется 5 итераций метода Гаусса-Зейделя. Пусть Ы]х -сложность нахождения решений систем линейных уравнений на ] -ой итерации алгоритма проверки изоморфизма графов. Тогда, с учетом (13),

( Л Л

NJX = O(n2) •(n log2 3 +

+3 log2 d + log2 50 + 3),

log „ Д- +1

, Д J .

log2 n +

поскольку одна итерация метода Гаусса-Зейделя требует 0(п2) элементарных машинных операций. Точные решения систем линейных уравнений принадлежат отрезку [0,1]п е Кп, следовательно, мы

можем положить 80 = 0(4п). С учетом (13) общая вычислительная сложность алгоритма может быть оценена как

ГА, Л

O

n х max

1< j <n

nn + log n -1 log2 n + log2 n

Д f

//

= O(n4).

Заключение

В класс ОС2-графов, для которых алгоритм решает задачу проверки изоморфизма графов, как и в класс ОС-графов, не попадают известные серии сильно-регулярных графов и некоторые другие, традиционно сложные для решения задачи ИГ графы.

Но, как показывает вычислительный эксперимент, в класс ОС2-графов попадают не только ОС-графы, но и многие графы, таковыми не являющиеся. Так, в библиотеке тестовых задач [11], использовавшейся для сравнения алгоритмов решения задачи ИГ на основе рекурсии с возвратом, не найдено примеров неправильного решения задачи ИГ представляемым алгоритмом для деревьев, случайных, планарных графов, регулярных n -мерных сеток (n < 4) и некоторых других. Установлено также, что алгоритм решает и те задачи ИГ из этой библиотеки, на которых время работы алгоритмов Ullman и NAUTY становится экспоненциальным.

Несмотря на то, что в обосновании алгоритма длина мантиссы предполагается равной n , при проведении вычислительных экспериментов достаточным было использование числового типа extended, реализованного в языках Object Pascal и С++, позволяющего работать с машинными числами в диапазоне от 3,6х10-4951 до 1,1х104932

Литература

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982.

2. Hopcroft, Wong A linear time algorithm for isomorphism of planar graphs // Proceedings of the Sixth Annual ACM

Symposium on Theory of Computing, 1974. - Р. 172184.

3. Luks Isomorphism of graphs of bounded valence can be tested in polynomial time // Proceedings of the 21-st IEEE FOCS Symp., 1980. - 42, 49,

4. Hoffmann Group-Theoretic Algorithms and Graph Isomorphism // Lecture Notes in Computer Science 1982. -Chapter V. - P.127-138,

5. Babai L., Grigoryev D., Mount D. Isomorphism of graphs with bounded eigenvalue multiplicity // Proc. 14th ACM symp. On theory of comput, STOC, 1982. -Р. 310-324.

6. Цветкович Д. и др. Спектры графов. Теория и применение. - Киев: Наукова думка, 1984.

7. Faizullin R., A. Prolubnikov An algorithm of the spectral splitting for the double permutation cipher // Pattern recognition and image analysis. MAIK, Nauka. 2002. - Vol. 12. - No. 4. - Р. 365-375.

8. Годунов С.К. и др. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. - Новосибирск: Наука, 1988.

9. Гантмахер Ф.Р. Теория матриц. - М.: Наука, 1976.

10. Бахвалов Н.С. Численные методы. - М.: Наука, 1975. - Т.1.

11. Foggia P., Sansone C., Vento M. A Database of graphs for isomorphism and sub-graph isomorphism benchmarking // Proc. of the 3rd IAPR TC-15 international workshop on graph-based representations, Italy, 2001. -P.157-168.