close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
2007
Компьютерная оптика, том 31, №3
ПРЯМОЙ АЛГОРИТМ ПРОВЕРКИ ИЗОМОРФИЗМА ГРАФОВ
А.В. Пролубников
Омский государственный университет
Аннотация
Предлагается алгоритм решения задачи проверки изоморфизма графов. Алгоритм является прямым, в том смысле, что он не является модификацией схемы рекурсии с возвратом,
на основе которой построены наиболее эффективные алгоритмы решения задачи. Решение
задачи находится за число итераций алгоритма, не превышающее число вершин в графах.
Показывается, что алгоритм является полиномиальным по числу используемых элементарных машинных операций и по используемой памяти. Исследуется класс графов, на котором
алгоритм дает решение задачи.
Введение
Задача изоморфизма графов (ИГ) принадлежит к
задачам, относительно которых нет ясности: являются ли они полиномиально разрешимыми или нет
[1], тогда, как известно, эта задача полиномиально
разрешима для некоторых классов графов. В частности для планарных графов, графов с ограниченной степенью вершин, графов с ограниченной кратностью собственных значений из спектра матрицы
смежности [2], [3], [4] и некоторых других классов
графов построены эффективные алгоритмы решения
этой задачи.
Поскольку эти алгоритмы используют специфические структурные характеристики графов, область
их эффективного применения ограничена. Возникает необходимость в алгоритме, который находил бы
решение задачи ИГ для как можно более широкого
класса графов, оставаясь при этом полиномиальным
как по времени, так и по памяти.
Алгоритм, представленный в [5], работает со
спектральными характеристиками графов и является
полиномиальным алгоритмом решения задачи ИГ с
наиболее широким классом применения. Но этот
класс не покрывает определяемых спектром графов,
которые попадают в область эффективного применения предлагаемого алгоритма. Граф называется
определяемым спектром (ОС-графом), если ему изоморфен любой граф с таким же спектром матрицы,
представляющей граф. Спектр матрицы графа так
же называют спектром графа.
Спектр графа не является его полным инвариантом. Так, почти все деревья и сильно-регулярные
графы не являются определяемыми спектром. Вместе с тем, спектр содержит в себе разнообразную
информацию о структуре графа [6] – такую как число ребер в графе, степенная последовательность
графа, род графа и др., что может быть использовано при построении эвристик для решения задачи
ИГ. Алгоритм спектрального расщепления [7], работает не напрямую со спектром графа, а со следующим, связанным со спектром, инвариантом:
S (G ) =
( ∏ λ , ∏ λ ,∏ λ ,…,∏ λ ) ,
k
1
k
2
k
n
k
где λ k – собственные значения модифицированной
матрицы смежности графа, λ ik – собственные значения матриц подграфов, полученных из исходного
86
удалением i -ой вершины; произведения берутся по
всем значениям из спектров. Будем называть граф
определяемым спектрами графа и подграфов (ОС2графом), если ему изоморфен любой граф с таким
же значением S .
Как показывает эксперимент, многие графы, которые не являются ОС-графами, например, деревья
являются ОС2-графами. Тогда как всякий ОС-граф
является ОС2-графом.
В задаче проверки изоморфизма графов даны два
графа GA и GB с множествами вершин V (GA ) ,
V (GB ) и ребер E (GA ) , E (GB ) . Мощности множеств
вершин и ребер графов равны. Требуется определить, существует ли такое биективное отображение
(изоморфизм) ϕ : VA → VB , что
(i, j ) ∈ E (GA ) ⇔ (ϕ(i ), ϕ( j )) ∈ E (GB ) ,
и представить его, если графы изоморфны.
При работе со спектром графа могут рассматриваться различные варианты матриц, представляющих граф. Все они являются некоторыми модификациями матрицы смежности графа A0 . A0 = (aij ) ,
где
⎧⎪1, (i, j ) ∈ E A ,
aij = ⎨
⎪⎩ 0, иначе,
B0 = (bij ) – матрица смежности графа G B .
Чем больше кратность собственных значений в
спектрах графов, тем больше в графах симметрий, и
тем более сложным является нахождение изоморфизма двух изоморфных графов с кратными собственными значениями. Предлагаемый алгоритм решения задачи проверки изоморфизма графов работает с видоизмененными матрицами смежности. В
ходе его работы последовательными согласованными возмущениями диагональных элементов матрицы производится расщепление собственных значений графа, что позволяет решать задачу проверки
ИГ для широкого класса графов за полиномиальное
время в смысле количества используемых машинных операций.
Алгоритм является прямым, то есть решение
производится без использования схемы рекурсии с
возвратом, на которой основаны наиболее извест-
Прямой алгоритм проверки изоморфизма графов
А.В. Пролубников
ные алгоритмы решения задачи ИГ без каких-либо
ограничений на структуру проверяемых на изоморфизм графов – алгоритмы Ullman, NAUTY и VF,
экспоненциальные для общего случая задачи.
–
A0
матрица
смежности
графа
GA = VA , E A , DA0 – диагональная матрица сле-
дующего вида:
⎡ d1
⎢0
⎢
⎢
⎢
⎣0
0
d2
0
–
стандартный
xk = ( xk1 ,…, xkn )
–
базис
в
Rn .
Пусть
k -й вектор-столбец матрицы
i −1
( A ) . Тогда если графы GA и GB изоморфны, и ϕ –
изоморфизм GA на GB , то:
Алгоритм
Пусть
{e j }nj =1
0⎤
… 0 ⎥⎥
,
⎥
⎥
… dn ⎦
…
n
где di = ∑ aij0 + d = di + d , d – максимальная стеj =1
пень вершин в графе GA , di – степень вершины
i ∈ VA . Матрица DB0 строится аналогично в соответствии с матрицей B0 . Алгоритм работает с матрицами следующего вида:
A = A0 + DA0 , B = B0 + DB0 .
(1)
Матрицы вида (1) – положительно определенные
матрицы с диагональным преобладанием. Матрицами графов далее будем называть матрицы вида (1).
В ходе работы алгоритма производится возмущение
матриц графов при помощи следующих матриц:
⎡0 … 0 … 0⎤ − 1
⎢
⎥
⎢
⎥
k
E = ⎢0 … 1 … 0⎥ − k
⎢
⎥
⎢
⎥
⎢⎣ 0 … 0 … 0 ⎥⎦ − n
На i -ой итерации будем производить следующие возмущения матриц графов:
Ai := Ai −1 + εE i , B i := B i −1 + εE j ,
⎡ x11 … x1i … x1n ⎤
⎢
⎥
⎢
⎥
⎢ xi1 … xii … xin ⎥ =
⎢
⎥
⎢
⎥
⎢⎣ xn1 … xni … xnn ⎥⎦
⎡ yϕ(1) ϕ(1) … yϕ(1) ϕ(i ) … yϕ(1) ϕ( n ) ⎤
⎢
⎥
⎢
⎥
= ⎢ yϕ(i ) ϕ(1) … yϕ(i ) ϕ(i ) … yϕ(i ) ϕ( n ) ⎥ .
⎢
⎥
⎢
⎥
⎢ yϕ( n ) ϕ(1) … yϕ( n ) ϕ (i ) … yϕ( n ) ϕ( n ) ⎥
⎣
⎦
Пусть
n −1
Λ i ≡ ∏ λ ik
k =1
n
∏λ
k =1
k
,
а R ( A) = {Λ i1 ,… , Λ i p } – это набор неповторяющихся
значений Λ i для матрицы A . Если | R ( A) |= n , то
есть если все диагональные элементы обратной матрицы к матрице A графа – разные, и G A и G B изоморфны, то, очевидно, изоморфизм может быть установлен без проведения возмущений по следующему правилу:
i = ϕ( j ) ⇔ Λ i = Λ j .
Докажем следующую лемму.
′ .
Лемма 2. Пусть A′ = A + εE i , A′xi = ei , Λ i = xii
Тогда может быть выбрано такое ε , что Λ i ≠ Λ j для
любого j ≠ i .
где j выбирается так, что S (GAi ) = S (GBi ) . Если GA
и GB – ОС2-графы, и GA изоморфен GB , то проведение таких возмущений возможно, поскольку имеет место очевидная лемма.
Лемма 1. Пусть GA и GB – изоморфные ОС2графы, P – матрица перестановки, соответствующая изоморфизму ϕ : VB → VA . Пусть A j и B j –
матрицы, получаемые из A и B возмущениями их
диагональных элементов в соответствии с последовательностями { j}nj =1 и {k j }nj =1 , где ϕ(k j ) = j . Тогда
A = PBP −1 ⇔ ∀j A j = PB j P −1 .
Обращение матриц производится путем решения
систем линейных уравнений Ai x = e j , B i x = e j , где
Доказательство. Пусть Apq – алгебраическое
дополнение элемента a pq матрицы A .
xii =
Aii
.
det A
Поскольку элемент aii матрицы A – единственный изменяемый в ходе возмущения матрицы элемент, то Aii′ = Aii , тогда как для любого j ≠ i получаем A′jj = Ajj + εAii , jj , где Aii , jj – определитель подматрицы матрицы A , получаемой удалением ее
i -ой строки, i -го столбца, j -ой строки и j -го
столбца. Изменение определителя при возмущении
следующее: det A ' = det A + εAii . Получаем, что при
надлежащем выборе ε для любого j ≠ i
87
2007
Компьютерная оптика, том 31, №3
Λj =
Ajj + εAjj ,ii
det A + εAii
≠
Aii
= Λi .
det A + εAii
Лемма доказана.
Учитывая леммы 1 и 2, можно утверждать, что
не более чем за n последовательных согласованных
возмущений матриц изоморфных ОС2-графов мы
можем добиться того, что
| R ( An0 ) |=| R( B n0 ) |= n ,
где n0 – необходимое число возмущений, n0 ≤ n .
Принципиальная схема алгоритма
где xk(1jk)1 ∈ Rk ( A j ), xl(1lj1) ∈ Rl ( A j ) , xl(1lj1) ∈ Rl ( A j ) . Будем
рассматривать ∆ (klj ) как расстояние между множествами Rk ( A j ) и Rl ( A j ) .
Числом обусловленности матрицы A называется
следующая величина µ( A) :
⎧⎪ Ax ⋅ ξ ⎫⎪
µ( A) = sup ⎨
⎬,
x ≠ 0, ξ≠ 0 ⎪ Aξ ⋅ x ⎪
⎩
⎭
где ⋅ – евклидова норма вектора в R n . Пусть λ max –
наибольшее собственное значение матрицы
λ min – наименьшее.
Шаг 0. i := 1 , A0 := A , B 0 := B .
Шаг 1. Если | R ( Ai −1 ) |= n , то перейти на шаг 3,
иначе перейти на шаг 2.1.
i -я итерация алгоритма:
Шаг 2.0. Выбор ε .
Шаг 2.1. Ai := Ai −1 + εE i .
Шаг 2.2. Поиск j т. ч.
S (GAi ) = S (GBi−1 +εE j ) .
Шаг 2.3. Если j не найден, то, либо поданные на
вход графы не изоморфны, либо – не являются ОС2графами. Работу алгоритма завершить, иначе перейти на следующий шаг.
Шаг 2.4. i := i + 1 . Перейти на шаг 1.
Шаг 3. Установить изоморфизм по правилу
i = ϕ( j ) ⇔ Λ i = Λ j .
µ( A) =
C
}
Рассмотрим множества Ri ( A j ) в процессе производимых в ходе работы алгоритма возмущений
матрицы A . Будем говорить, что Ri ( A j −1 ) расщепляется на j -ой итерации алгоритма, если
x (jjj −1) ∈ Ri ( A j −1 ) , | Ri ( A j −1 ) |> 1
для некоторого i , но
x (jjj ) ∈ Rk ( A j ) , и | Rk ( A j ) |= 1 .
Положим,
∆
88
( j)
kl
≡ x
( j)
k1 k1
−x
( j)
l1l1
,
ξ
λ max
< ∞.
λ min
≤θ,
A
где A = sup
x≠0
Ax
x
.
A = λ max для положительно определенной мат-
рицы A [8]. Имеет место следующая теорема [8].
Теорема 1. Если ϑµ( A) < 1 , то
y−x
x
Пусть R( A( j ) ) = {Λ1( j ) ,… , Λ (pj ) } – набор R к j -ой
{
sup Aξ
=
λ min ≠ 0 , поскольку A – положительно определенная матрица.
Рассмотрим систему ( A + C ) y = f , полученную
из системы Ax = f возмущением A при помощи
матрицы C . Пусть
Локализация элементов множества R
Ri ( A j ) = xi(1i1j ) | xi(1ij1) = Λ i( j ) , i = 1, p.
x
x ≠0
ξ≠ 0
Вычислительная эффективность алгоритма
итерации. Обозначим решение системы уравнений
A j x = ek , как xk( j ) , и определим множества Ri ( A( j ) )
как
sup Ax
A,
≤
θµ( A)
.
1 − θµ( A)
Для числа обусловленности симметричной матрицы выполняется [8]:
η( A)
,
µ( A) ≤
χ( A)
где
⎛
⎞
η( A) = max ⎜ aii + ∑ | aij | ⎟ ,
1≤ i ≤ n
j ≠i
⎝
⎠
⎛
⎞
χ( A) = min ⎜ aii − ∑ | aij | ⎟ .
1≤ i ≤ n
j ≠i
⎝
⎠
На j -ой итерации akk = d + d k + ε k , где ε k – значение возмущения k -го диагонального элемента A ,
и ε k = 0 если k < j . Пусть i – номер строки, на ко-
торой достигается η( A) , i2 – номер строки, на которой достигается χ( A) . Имеем
Прямой алгоритм проверки изоморфизма графов
А.В. Пролубников
Имеем
n
η( A) = ai1i1 + εi1 + ∑ | ai1 j |= d + εi1 + di1 +
j =1
µ( A j −1 ) =
+ di1 = d + εi1 + d + d = 3d + ε i1 ,
где λ max – максимальное собственное значение
n
χ( A) = ai2 i2 + εi2 + ∑ | ai2 j |=
A j −1 , λ min – минимальное. По теореме Гершгорина
j =1
[9] λ max ≥ d . Учитывая, что λ min ≤ A j −1 , получаем
= d + εi2 + di2 − di2 = d + εi2 .
A j −1 > λ min > λ max 4 > d 4 .
Следовательно,
η( A) 3d + εi1
=
.
χ( A) d + εi2
µ( A) ≤
Таким образом, из (3) следует
Если εi1 = 1 n , εi2 = 1 n
p1
3d + εi1
µ( A) ≤
=n
Так как все собственные значения A j не меньше
1, и ek = 1 для любого k , то xi( j −1) < 1 . Из (3) следует, что для любого i
3dn p1 + 1
4dn p1
≤ n p2 − p1
=4.
p2
dn + 1
dn p2
p2 − p1
Для
4
x .
1 − 4θ
(2)
гарантированного
выделения
x (jjj −1)
из
j −1
Ri ( A ) на j -ой итерации возмущения должны
быть достаточно малы, поскольку необходимо, чтобы после возмущения x (jjj ) был достаточно удален от
( j)
ii
в смысле введенного
всех остальных значений x
расстояния ∆ .
Из (2) следует, что
xi( j ) − xi( j −1) ≤
4θ(ε j )
xi( j −1) .
1 − 4θ(ε j )
A
j −1
εjE j
=
A
=
j −1
εj
A j −1
,
мы можем положить
εj
θ(ε j ) =
Полагая ε j = 1 n p , получаем
( j)
i
x
=
=
( j −1)
i
−x
<
4 np
Aj − 4 np
4
A n −4
j
p
4 np
Aj − 4 np
( j −1)
i
x
5
A np
20
.
dn p
(4)
Неравенство (4) дает оценку локализации векторов из множеств Ri ( A j ) в процессе работы алгоритма.
Расщепление множеств Ri
Производимые возмущения должны быть достаточны для расщепления множеств Ri . Алгоритм является вычислительно эффективным только в том
случае, если для любого j и любых k и l , не рав-
xii( j ) − x (jjj ) >
(3)
j
xii( j ) − xii( j −1) <
Теорема 2. Если xii( j −1) = x (jjj −1) и 0 < ε j < 1 , то
=
xi( j −1) =
xi( j −1) ≤
следовательно, для любого i
есть перед j -ой итерацией в этом множестве имеется по меньшей мере два элемента, препятствующих
установлению взаимнооднозначного соответствия
между вершинами графов.
.
A j −1
xii( j ) − xii( j −1) < xi( j ) − xi( j −1) ,
ных друг другу, ∆ (klj ) будет отличным от нуля машинным числом. Покажем, что необходимая точность решения систем линейных уравнений может
быть обеспечена при помощи машинных чисел с
длиной мантиссы, не превышающей n .
Пусть xii( j −1) , x (jjj −1) ∈ Ri ( A j −1 ) для некоторого i , то
Поскольку
C
20
.
dn p
xi( j ) − xi( j −1) <
Таким образом, в нашем случае утверждение
теоремы 1 принимает следующий вид:
Если θ < 1 4 , то
y−x ≤θ
20 ( j −1)
xi
.
dn p
xi( j ) − xi( j −1) <
, где p1 , p2 ∈ N , то
p2
3d + 1 n p1
=
=
d + 1 n p2
d + εi2
λ max
≤4,
λ min
xi( j −1) .
1
.
3 d (3d / ε j + 1)
n
2
Доказательство. Пусть A = A j −1 , A ' = A j ,
xi = xi( j −1) , xi′ = xi( j ) , x j = x (j j −1) , x′j = x (j j ) . Если
x′j = Pxi′ , то x′jj = xii′ .
89
2007
Компьютерная оптика, том 31, №3
x′jj =
A′jj
det A′
, xii′ =
Aii′
.
det A′
| xii′ − x ′jj |=
После возмущения
>
det A′ = det A + ε j Ajj , A′jj = Ajj ,
>
так как a jj – единственный изменяемый элемент A
на итерации алгоритма. Поскольку
Aii′ = Aii + ε j Aii , jj ,
=
Ajj
det A′
−
A′jj
det A′
−
det A′
=
ε j d n−2
(3d ) n +1 + ε j (3d ) n
ε j Aii , jj
det A + ε j Ajj
.
(5)
,
1
.
3 d (3d / ε j + 1)
n
2
Пусть решение систем линейных уравнений
A x = ek и B j x = ek ( j , k = 1, n) осуществляется методом Гаусса-Зейделя. Метод Гаусса-Зейделя позволяет оценить необходимую длину мантиссы используемых машинных чисел. В действительности не
принципиально, каким методом мы решаем системы
уравнений, необходимо только, чтобы решение находилось с нужной точностью за приемлемое время.
Имеет место [10] следующая теорема.
∑| a
l ≠k
j ≠i
где
ij
|≤ γ | aii | , γ < 1 ,
для каждого i = 1, n . Тогда
⎧ d + ε k , если 1 ≤ k ≤ j ,
d k′ = ⎨
⎩d , если 1 ≤ k ≤ j.
x − x s ≤ γ x − x s −1 ,
Следовательно,
Aii , jj ≥ H1 × … × H i × … × H j × … × H n =
= d1′ × … × d ′i × … × d ′ j × … × d n′ > d n − 2 ,
(6)
черта сверху означает невключение в произведение.
С другой стороны, по теореме Гершгорина максимальное собственное значение λ max матрицы A
можно оценить так:
λ max ≤ 3d + max ε k < 3d + 1 ,
1≤ k ≤ j
где x – точное решение системы уравнений Ax = b ,
xis – приближенное решение этой же системы уравнений на s -ой итерации метода Гаусса-Зейделя.
Если A ≡ A j , то γ ≤ 1 2 . Следовательно, на s -ой
итерации метода Гаусса-Зейделя
xii − xiis ≤ xi − xis <
1 0
δ ,
2s
x jj − x sjj ≤ x j − x sj <
1 0
δ ,
2s
где δ0 – ошибка начального приближения. Если
ε j = 1 n p на j -ой итерации, то, учитывая (9), полу-
если ε k < 1 для любого k . Поэтому
чаем
< (3d + 1) ,
(7)
n −1
Ajj = ∏ λ ′k < λ max
< (3d + 1) n −1 .
1
.
3n d 2 (3dn p + 1)
Значит, если
(8)
1 0
1
δ ≤ n 2
,
2s −1
3 d (3dn p + 1)
k =1
(9)
Теорема 3. Пусть
H k ≡| akk | −∑ | akl | = d k > 0, i = 1, n,
det A = ∏ λ k < λ
>
j
мой удалением из нее i -х строки и столбца и j -х
строки и столбца. A – симметричная положительно
определенная матрица с диагональным преобладанием, для которой выполняются условия Адамара:
n
max
n
n −1
k =1
Пусть λ ′max – максимальное собственное значение подматрицы, получаемой из A удалением строк
и столбцов с номерами i и j . λ ′max ≤ λ max [9]. Используя (6), (7) и (8), из (5) получаем:
90
(3d + 1) n + ε j (3d + 1) n −1
Теорема доказана.
Aii , jj – определитель подматрицы A , получае-
n
>
ε j d n−2
xii( j ) − x (jjj ) >
Aii′
=
det A′
Aii + ε j Aii , jj
det A + ε j Ajj
то есть
и Aii = Ajj , так как xii = x jj , получаем
| x′jj − xii′ |=
ε j Aii , jj
x (jjj ) − xii( j ) >
то разница x (jjj ) − xii( j )
(10)
может быть зафиксирована
машинными числами с длиной мантиссы, не превышающей n . Оценим количество итераций метода
Прямой алгоритм проверки изоморфизма графов
А.В. Пролубников
Гаусса-Зейделя s , необходимых для фиксирования
этого значения.
Формула (10) эквивалентна
3n d 2 (3dn p + 1)δ0 ≤ 2 s −1 .
(11)
Логарифмируя (11), получаем
n log 2 3 + log 2 d 2 (3dn p + 1) + log 2 δ0 ≤ s − 1 ,
то есть число необходимых итераций метода ГауссаЗейделя может быть оценено как
s ≥ n log 2 3 + p log 2 n + 3log 2 d + log 2 δ0 + 3 .
(12)
Пусть p > 0 определяет значение возмущения
ε j = 1 n p . Пусть x (jjj −1) – значение, выделяемое из
Ri ( A j −1 ) на j -ой итерации. Выберем p так, что
20 ∆
< ,
dn p n
2n ⋅ O ( N X ) + O ( n) .
(13)
Оценим O( N X ) для метода Гаусса-Зейделя. На
j -ой итерации алгоритма, находя ε j , мы вычисля-
то есть
p > log n
Общая вычислительная сложность
алгоритма
На каждой итерации алгоритма мы проводим
вычисление наборов R для обоих графов, для чего
мы обращаем матрицы графов. Для обращения матриц необходимо решить 2n систем линейных уравнений. Пусть O( N X ) – число элементарных машинных операций, которые необходимо совершить для
решения систем линейных уравнений с заданной
точностью. Тогда сложность процедуры обращения
матриц составит 2n ⋅ O( N X ) .
Проверка равенства значений из R ( A) и R ( B )
(проверка равенства значений S ( A) и S ( B ) ) для
пары матриц A и B осуществима за O(n) элементарных машинных операций. Следовательно, общая
сложность одной итерации алгоритма составляет
ем p такое, что 20 dn p < ∆ j n , где ∆ j = min ∆ (klj ) ,
20
+1 ,
d∆
k ≠l
то есть
где ∆ = min ∆ (klj ) .
p = log n
k ≠l
Из (4) следует, что для любого i
x ii( j −1) − x ii( j ) <
20
dn p
<
∆
.
n
Получаем
1
∆
< xii( j ) − x (jjj ) <
3n d 2 (3d / ε j + 1)
n
после j -ой итерации. Это означает, что на j -ой
итерации мы можем выбрать такое возмущение, которое давало бы выделение x (jjj −1) из содержащего его
j −1
множества Ri ( A ) (если его мощность не равна 1),
фиксируемое при помощи машинных чисел с длиной мантиссы равной n при сохранении локализации значений xii , i = 1, n . То есть могут быть заданы
интервалы, в пределах которых будут происходить
расщепления множеств Ri . Возмущения могут проведены таким образом, что после выделения x jj из
некоторого Ri ( A
j −1
) , x jj не попадает на следующей
итерации в другое такое множество с мощностью
отличной от 1.
В результате, если для решения систем линейных уравнений производится число итераций метода Гаусса-Зейделя, определяемое (12), то при n0 ≤ n
мы получаем | R ( An0 ) |= n , и расщепление элементов
из R фиксируется машинными числами с длиной
мантиссы, не превышающей n .
16
+1 .
d∆ j
После чего, в соответствии с (12), выполняется
s итераций метода Гаусса-Зейделя. Пусть N Xj –
сложность нахождения решений систем линейных
уравнений на j -ой итерации алгоритма проверки
изоморфизма графов. Тогда, с учетом (13),
⎛
⎞
1
N Xj = O(n 2 ) ⋅ ( n log 2 3 + ⎜ log n
+ 1⎟ log 2 n +
⎜
⎟
∆j
⎝
⎠
0
+3log 2 d + log 2 δ + 3) ,
поскольку одна итерация метода Гаусса-Зейделя
требует O(n 2 ) элементарных машинных операций.
Точные решения систем линейных уравнений принадлежат отрезку [0,1]n ∈ R n , следовательно, мы
можем положить δ0 = O ( n ) . С учетом (13) общая
вычислительная сложность алгоритма может быть
оценена как
⎛
⎛
⎞⎞
1
O ⎜ n × max ⎜ n 2 n + log n
log 2 n + log 2 n ⎟ ⎟ =
⎟⎟
⎜ 1≤ j ≤ n ⎜
∆j
⎝
⎠⎠
⎝
(14)
= O(n ).
4
Заключение
В класс ОС2-графов, для которых алгоритм решает задачу проверки изоморфизма графов, как и в
класс ОС-графов, не попадают известные серии
сильно-регулярных графов и некоторые другие, традиционно сложные для решения задачи ИГ графы.
91
2007
Компьютерная оптика, том 31, №3
Но, как показывает вычислительный эксперимент, в
класс ОС2-графов попадают не только ОС-графы,
но и многие графы, таковыми не являющиеся. Так, в
библиотеке тестовых задач [11], использовавшейся
для сравнения алгоритмов решения задачи ИГ на
основе рекурсии с возвратом, не найдено примеров
неправильного решения задачи ИГ представляемым
алгоритмом для деревьев, случайных, планарных
графов, регулярных n -мерных сеток (n ≤ 4) и некоторых других. Установлено также, что алгоритм решает и те задачи ИГ из этой библиотеки, на которых
время работы алгоритмов Ullman и NAUTY становится экспоненциальным.
Несмотря на то, что в обосновании алгоритма
длина мантиссы предполагается равной n , при проведении вычислительных экспериментов достаточным было использование числового типа extended,
реализованного в языках Object Pascal и С++, позволяющего работать с машинными числами в диапазоне от 3,6×10-4951 до 1,1×104932.
Литература
1.
2.
92
Гэри М., Джонсон Д. Вычислительные машины и
труднорешаемые задачи. - М.: Мир, 1982.
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.
Документ
Категория
Без категории
Просмотров
22
Размер файла
316 Кб
Теги
алгоритм, проверка, графов, изоморфизм, прямой
1/--страниц
Пожаловаться на содержимое документа