close

Вход

Забыли?

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

?

Алгоритм поиска приближенного решения задачи проверки изоморфизма подграфов.

код для вставкиСкачать
Математические
структуры и моделирование
2003, вып. 11, с. 5967
УДК 519.171
АЛОИТМ ПОИСКА ПИБЛИЖЕННОО
ЕШЕНИЯ ЗАДАЧИ ПОВЕКИ ИЗОМОФИЗМА
ПОДАФОВ
А.В. Пролубников
We onsider the subgraph isomorphism problem with the following restrition.
We suppose that both heked graphs have the same number of verties.
Proposed metri represents the distane between heked graphs. This metri
allows to ome to the problem of finding an optimal embedding of one of the
graphs into another. The supposed algorithm is an algorithm for finding an
approximate solution for the problem. Conditions needed for the algorithm
effetiveness are onsidered.
Задача проверки изоморизма подграов представляет собой обобщение
для широкого класса задач, находящих практическое применение, в частности
в таких областях, как распознавание образов и обработка изображений. Однако, помимо практической важности, задача имеет и теоретическую важность,
поскольку задача является N P -полной [1? и к ней могут быть сведены такие
задачи теории граов, как задача поиска гамильтонова цикла в грае, поиска
максимальной клики в грае и некоторые другие.
При этом, если вопрос о принадлежности задачи проверки изоморизма
граов к классу P или N P до сих пор остается открытым [1?, но некоторые дополнительные ограничения на структуру граов позволяют перевести задачу в
класс P [2,3?, [4?, то, например, ограничение задач проверки изоморизма подграов на планарные граы оставляет задачу в классе N P -полных задач [5? в
отличие от подобных задач проверки изоморизма граов. Поэтому возникает
необходимость в построении алгоритмов, находящих приемлемое приближенное
решение задачи за полиномиальное время.
ра GA (VA ; EA ) является подграом граа GB (VB ; EB ), если VA VB и
EA EB . ра GA называется остовным подграом или частичным граом
граа GB , если jVB j = jVA j.
Постановка задачи проверки изоморизма подграов следующая:
ра GA (VA ; EA ) изоморен некоторому подграу граа GB (VB ; EB ), если
существует такая инъекция ' : VA ! VB , что 8(i; j ) 2 VA ) ('(i); '(j )) 2 VB .
2003
А.В. Пролубников
E-mail: prolubnikovmath.omsu.omskreg.ru
Омский государственный университет
60
А.В. Пролубников.
Алгоритм поиска приближенного решения задачи...
Вложением граа GA hVA ; EA i в гра GB hVB ; EB i (jVA j = jVB j, jEA j jEB j)
будем называть произвольное биективное отображение ' : VA ! VB . ра, получаемый из граа GA перенумерацией его вершин, соответствующей биекции
'
', обозначать GA и также назвать вложением.
Любому вложению ' может быть однозначно поставлена в соответствие
некоторая матрица перестановки P и наоборот. То есть P и ' могут быть отождествлены друг с другом. Для произвольной матрицы A под матрицей A(')
будем понимать матрицу P AP 1 , то есть матрицу, полученную из A перестановкой ее строк с такой же перестановкой ее столбцов (перестановкой рядов),
задаваемой P .
Изоморным
вложением
невзвешенного
неориентированного
граа GA hVA ; EA i в гра GB hVB ; EB i (jVA j = jVB j; jEA j jEB j) будем
называть такое биективное отображение ' : VA ! VB , что (i; j ) 2 EA тогда
и только тогда, когда ('(i); '(j )) 2 EB . Если jEB j = jEA j, то существование
изоморного вложения граа GA в гра GB эквивалентно изоморности этих
граов.
Формулировка задачи поиска приближенного решения задачи проверки изоморизма подграов включает в себя целевую ункцию, требующую минимизации, представляющую собой некоторую количественную характеристику
близости граов. Примерами такой ункции могут служить ункции, представленные в [6, 7?.
Пусть A0 ; B0 матрицы смежности граов GA и GB . Матрица C0 = A0 B0
матрица смежности некоторого взвешенного граа с весами ребер, равными
1 и -1. Ее элементы следующие:
8
< 1;
ij =
:
1;
0;
если (i; j ) 2 EA и (i; j ) 62 EB ;
если (i; j ) 62 EA и (i; j ) 2 EB ;
если ((i; j ) 2 EA и (i; j ) 2 EB ); или
((i; j )
62 EA и (i;
j)
62 EB ):
Матрица C0 симметрическая, поскольку матрицы A0 и B0 симметрические.
Задаваемый ей взвешенный гра является дополнением граа GA до граа
GB только в том случае, когда в C0 отсутствуют элементы, равные -1, то есть
когда GA подгра GB . Матрица C0 задает таким образом взвешенный гра
GC , наличию ребра в котором соответствует наличие такого же ребра только в
одном из граов GB или GA , отсутствие наличию такого ребра в обоих граах
либо отсутствие такого ребра в обоих граах.
Чем меньше ребер в грае GC и соответственно меньше ненулевых элементов в матрице C0 , тем гра GB можно считать более близким к грау GA .
Будем в дальнейшем гра GC , соответствующий матрице C0 , называть разно'
стью граов GA и GB и введем метрику, конкретизирующую понятие близости
граов.
ассмотрим робениусову (евклидову) норму матрицы F для матрицы A =
(aij ), определяемую как
F (A) =
n X
n
X
i=1 j =1
a2ij
1=2
:
(4)
Математические структуры и моделирование. 2003. Вып. 11.
61
При перенумерации вершин граа GA , соответствующей биекции ', получаем гра G'A с матрицей смежности P A0 P 1 , обозначаемой далее A0 ('). Матрица
разности граов GB и G'A матрица C0 (') = B0 A0 ('). Значениe F (C0 ('))
равно квадратному корню от числа несовпадающих ребер в граах G'A и GB .
Функция
df
Ж (G A ; G B ) =
min
'2 (GA )
F (C0 ('));
рассматриваемая как ункция расстояния между граами, является метрикой,
поскольку:
1. Ж неотрицательна:
Ж (GA ; GB ) 0,
Ж (GA ; GB ) = 0 , GA = GB .
2. Ж симметрична: Ж (GA ; GB ) = Ж (GB ; GA ).
3. Ж удовлетворяет правилу треугольника: Ж (GA ; GB ) Ж (GB ; GC ) + Ж (GC ; GB ).
После введения метрики Ж задача поиска оптимального вложения граа GA
в гра GB может быть сормулирована так. Необходимо найти вложение '
граа GB в гра GA , при котором F (C0 (')) = Ж (GA ; GB ).
Мы рассматриваем задачу поиска оптимального вложения граа GA в гра
GB с дополнительным условием: jVA j = jVB j; jEA j jEB j.
Предлагаемый нами алгоритм решения задачи поиска оптимального вложения граа является модиикацией алгоритма спектрального расщепления
проверки изоморизма граов и работает с матрицами смежности граов,
аналогично модиицированными до положительно определенных. Матрицы
видоизменяются следующим образом. Пусть A0 матрица смежности граа
GA hVA ; EA i. В соответствии с матрицей A0 строим диагональную матрицу DA0 :
0
B
B
B
dA
11
0
..
.
0
dA
22
0
..
.
0
:::
:::
..
.
0
0
..
.
: : : dA
nn
1
C
C
C
A
со следующими элементами на диагонали:
dA
ii =
n
X
j =1
a0ij + d = di + d;
где d максимальная степень вершин в грае GA , а di степень вершины i.
Аналогично по матрице B0 строится матрица DB0 . Матрицы, с которыми работает алгоритм, имеют следующий вид:
A = A0 + DA0 ; B = B0 + DB0 :
(1)
Эти матрицы могут рассматриваться как матрицы некоторых мультиграов, у
которых допустимы кратные ребра (петли).
Вместо матрицы C0 как матрицу, представляющую разность граов GB и
GA , будем рассматривать матрицу C : C = A B . Если
F (B0
A0 (')) = F (C0 (')) = Ж (GA ; GB );
62
А.В. Пролубников.
Алгоритм поиска приближенного решения задачи...
то и
F (B
A(')) = F (C (')) =
min (F (B
'2 (GA )
A('))):
В самом деле:
B
A(') = (B0
A0 (')) + (DB
DA (')):
Последовательность степеней вершин граа является инвариантом для изоморных граов. Если ' оптимальное вложение, то значит, что количество
несовпадающих ребер у граа вложения GA (') и граа GB минимально, что
также соответствует минимуму разности степеней у соответствующих вершин
граов. Следовательно, минимизация ункционала F (B0 A0 (')) равносильна
минимизации ункционала F (B A(')).
Алгоритм спектрального расщепления проверки изоморизма граов основан на последовательном расщеплении собственных значений видоизмененных
до положительно определенных матриц смежности и решении систем линейных уравнений, определяющих обратные матрицы. Предложена модиикация
алгоритма [8?, работающая сo столбцами обратной матрицы к матрице A, получаемыми при решении систем уравнений:
Ax = ej ; By = ek ; j; k = 1; n;
(2)
где вектор ej = (0; : : : ; 0; 1; 0; : : : ; 0) j -й орт в пространстве Rn . Сравнение
норм столбцов обратных матриц позволяет получить решающую перестановку,
задающую изоморизм. То есть эвристикой, на основе которой строится изоморизм, является обратная матрица к видоизмененной матрице смежности
граа. Отслеживание возмущений обратной матрицы по возмущениям самой
матрицы позволяет определить биекцию, задающую изоморизм.
Если на вход алгоритма поданы изоморные граы, то невозможность
установления однозначного соответствия возникает при наличии среди этих
векторов-решений группы векторов, которые могут быть получены друг из друга с помощью перестановки их компонент и, следовательно, имеют одинаковые
нормы. При этом компоненты этих векторов, образующие диагональ обратной
матрицы, совпадают. При нахождении в матрице B строки и столбца, соответствующих строке и столбцу с номером j матрицы A, на каждой j -й итерации алгоритма последовательно производятся возмущения ее диагональных
элементов. При возмущении матрицы, влекущем расщепление ее собственных
значений, происходит возмущение векторов-столбцов обратной к A матрицы. В
результате группы векторов с одинаковыми нормами расщепляются.
63
Математические структуры и моделирование. 2003. Вып. 11.
Алгоритм спектрального расщепления
проверки изоморизма граов.
Принципиальная схема
Шаг 0. A0 := A, B 0 := B ; j := 1.
Шаг 1.1. Если j n, то перейти на шаг 1.1, иначе перейти на шаг 6.
Шаг 1.2. Выбор "j .
Шаг 1.3. Aj := Aj 1 + "j E j .
Шаг 2. ешение системы линейных уравнений Aj x = ej . xj полученное
решение. k := 1.
Шаг 3.1. Если k n, то перейти на шаг 3.2, иначе граы неизоморны.
аботу алгоритма завершить.
Шаг 3.2. Bk := B j 1 + "j E k .
Шаг 3.3. ешение системы линейных уравнений B k y = ek . yk полученное
решение.
Шаг 3.4. k := k + 1. Перейти на шаг 3.1.
Шаг 4. Сравнение норм векторов xj и yk , где k такие, что 8i < j 6 9i : i $ k .
Если 8k kxj k 6= kyk k, то граы GA и GB неизоморны. аботу алгоритма
завершить.
Если 9k kxj k = kyk k, и 8i 9l : xji = ykl , и xjj = ykk , то kj := k . (Установление
соответствия j $ kj .)
Шаг 5. B j := B j 1 + "j E kj . j := j + 1. Перейти на шаг 1.1.
Шаг 6. аботу алгоритма завершить. Полученное соответствие j $ kj ; j = 1; n
найденный изоморизм граов GA и GB .
Модиикация алгоритма спектрального расщепления проверки изоморизма граов, дающая эвристический алгоритм поиска оптимального вложения одного из граов в другой, осуществляется следующим образом. Так, на каждой
j -ой итерации алгоритма спектрального расщепления проверки изоморизма
граов, если граы GA и GB изоморны и '0 изоморизм, а P 0 соответствующая ему матрица перестановки, то выполняется следующее ключевое
соотношение:
Если Aj = Aj 1 + "j E j , то
B j = B j 1 + "j E '0 (j )
, B j = P0Aj P0 1 (то есть F (B j
P0 Aj P0 1 ) = 0):
(3)
В данном случае, если граы GA и GB близки в соответствии с введенной метрикой Ж и '0 искомое оптимальное вложение, а P 0 соответствующая ему
матрица перестановки, то на каждой j -ой итерации должно выполняться следующее ключевое соотношение:
Если Aj = Aj 1 + "j E j , то
B j = B j 1 + "j E '0 (j )
, F (B j
P0 Aj P0 1 ) =
min
fF (B
P 2 (GB )
g
P AP 1 ) :
(4)
Принципиальная схема алгоритма поиска оптимального вложения граа
следующая.
64
А.В. Пролубников.
Алгоритм поиска приближенного решения задачи...
Алгоритм спектрального расщепления
поиска оптимального вложения граа.
Принципиальная схема
Шаг 0. A0 := A, B 0 := B ; j := 1.
Шаг 1. Если j n, то перейти на шаг 1.1, иначе перейти на шаг 6.
Шаг 1.1. Выбор "j .
Шаг 1.2. Aj := Aj 1 + "j E j .
Шаг 2. ешение системы линейных уравнений Aj x = ej . xj полученное решение.
Шаг 3. k := 1. Если k n, то перейти на шаг 3.1, иначе перейти на шаг 4.
Шаг 3.1. Bk := B j + "j E k .
Шаг 3.2. ешение системы линейных уравнений B k y = ek . yk полученное
решение.
Шаг 3.3. k := k + 1. Перейти на шаг 3.
Шаг 4. Сравнение
норм векторов
x j и yk , где k такие,
что 8i < j 6 9i : i $ k .
n
P
n
n
P
kxjik P kykik = min
kxjik
l i=1
i=1
i=1
соответствия j $ kj ).
Если k
: n
P
i=1
kylik, то kj := k. (Установление
Шаг 4.1. B j := B j 1 + "j E kj .
Шаг 5. j := j + 1. Перейти на шаг 1.
Шаг 6. аботу алгоритма завершить. Полученное соответствие j $ kj ; j
найденное вложение граа GA в гра GB .
Пусть B A('0 ) = C ('0 ). ассмотрим системы линейных уравнений
A('0 )x = ej ; Bx0 = ej ; j = 1; n;
где вектор ej
Если
= (0; : : : ; 0; 1; 0; : : : ; 0)
= 1; n
(5)
j -й орт в пространстве Rn .
kC ('0)k ;
kA('0)k
(6)
(A('0 )) число обусловленности матрицы A('0 ) и (A('0 )) < 1, то для решений x и x0 систем уравнений (4) справедливо [9? неравенство
kx x0k (A('0)) :
kxk
1
(A('0 ))
(7)
Для матрицы A('0 ) число обусловленности (A('0 )) 3 [8?. Поэтому, если выполняется (6) и < 1=3, то для решений x и x0 систем уравнений (5) неравенство
(7) принимает следующий вид:
kx
x0
k 1 33 kxk:
То есть решения систем уравнений (5), задающие обратные матрицы для матриц A('0 ) и B , изменяются непрерывно при малых возмущениях, задаваемых
Математические структуры и моделирование. 2003. Вып. 11.
65
матрицей C ('0 ). А значит, и дополнительные возмущения диагональных элементов матриц "j , производимые на каждой j -ой итерации, с некоторой погрешностью будут сохранять ключевое соотношение (3), выполнению которого будет
соответствовать выполнение соотношения (4).
Возмущая матрицы A и B с помощью матриц "j E j и "j E '0 (j ) , полагая при
этом, что на каждой итерации '0 (j ) = k , где k такое, что
n
X
i=1
kxjik
n
X
i=1
n
X
= min
l kykik
i=1
kxjik
n
X
i=1
;
kylik
мы будем минимизировать n из n2 слагаемых, входящих в ункционал
F ((B j ) 1 P (Aj ) 1 P 1 ).
Стремясь уменьшить на каждой итерации алгоритма значение ункционала F ((B j ) 1 P (Aj ) 1 P 1 ), при неизвестной нам матрице перестановки P мы
исходим из того, что два ункционала ункционал F (B j P Aj P 1 ) и ункционал F ((B j ) 1 P (Aj ) 1 P 1 ) достигают минимума на одной и той же матрице
перестановки, что справедливо, когда GA = GB , так, в этом случае
B
P AP 1 = 0
,B
1
P A 1 P 1 = 0:
Если же Ж (GA ; GB ) мало, то поскольку kC ('0 )k F (C ) [9?, будет мало
и отношение kC ('0 )k=kA('0 )k, а значит, возможно эективное применение
алгоритма спектрального расщепления поиска изоморного вложения граа,
что подтверждается вычислительным экспериментом.
Приведенные ниже результаты представляют собой усреднение по серии
вычислительных экспериментов. Искалось изоморное вложение граа GA в
гра GB , заведомо существующее. енерировался гра GB , по нему строился
остовный подгра G0A , после чего случайным образом перенумеровывались его
вершины и получался гра GA .
В приведенной таблице SB обозначает вероятность, с которой при генерировании случайного граа между двумя вершинами граа проводится ребро
(ѕплотностьї граа GB ). SA (B ) обозначает вероятность, с которой при построении остовного подграа GA между вершинами остается ребро граа GB (ѕплотностьї граа GA относительно граа GB ). NeB число ребер в грае GB . NeA
C (')
число ребер в грае GA . Ne
число несовпавших ребер в найденном вложении граа GA в гра GB грае G'A . Число вершин в граах равнялось
50.
Отметим, что главная трудность при решении поставленной задачи заключается в том, что, не зная оптимального вложения '0 граа GA в гра GB , мы
не можем определить Ж (GA ; GB ) и соответственно kC ('0 )k. Однако, несмотря на
это, при помощи алгоритма спектрального расщепления поиска оптимального
вложения граа может, в частности, эективно решаться задача со следующей содержательной постановкой.
Имеется некоторый набор изображений-шаблонов, в соответствие каждому
из которых, например, по одному из методов, предложенных в [10?, поставлен некоторый гра. Проверяемое (тестовое) изображение является одним из
66
А.В. Пролубников.
Алгоритм поиска приближенного решения задачи...
Таблица 1. езультаты вычислительного эксперимента
SB
0,80
0,85
0,90
0,80
0,85
0,90
0,80
0,85
0,90
SA (B )
0,70
0,70
0,70
0,85
0,85
0,85
0,90
0,90
0,90
NeB
1206
1221
1233
1210
1218
1227
1217
1210
1223
NeA
941
938
926
967
953
970
973
981
983
C (')
Ne
12
7
3
13
6
3
14
11
5
шаблонных изображений, содержащим повреждения. Необходимо определить,
каким шаблонным изображением изначально являлось тестовое изображение.
Повреждения шаблонного изображения, дающие тестовое изображение, могут привести к тому, что построенный по нему гра будет отличаться от граа любого шаблонного изображения. И тогда задача идентиикации тестового изображения, то есть выбора шаблонного изображения, соответствующего
тестовому, будет состоять в поиске граа шаблонного изображения, наиболее
близкого к грау тестового изображения в соответствии с введенной метрикой.
Литература
1. эри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи. М.:
Мир. 1982
2. Hoproft J., Wong J., A linear time algorithm for isomorphism of planar graphs //
Proeedings of the Sixth Annual ACM Symposium on Theory of Computing. 1974.
P.172-184.
3. Luks E.M., Isomorphism of graphs of bounded valene an be tested in polynomial time
// Pro. 21st IEEE FOCS Symp. 1980. P.42-49.
4. Hoffmann C.M. Group-Theoreti Algorithms and Graph Isomorphism // Leture Notes
in Computer Siene (Chapter V). 1982. P.127-138.
5. Baker B.S. Approximation algorithms for NP-omplete problems on planar graphs //
J. Asso. Comput. Mah. 1994. V.41. P.153-180.
6. Bunke H. On a relation between graph edit distane and maximum ommon subgraph
// Pattern Reogn. Lett. 1997. V.18, N.8. P.689-694.
7. Bunke H., Shearer K. A Graph distane metri based on the maximal ommon
subgraph // Pattern Reogn. Lett. 1998. V.19, N.3-4. P.255-259.
8. Пролубников А.В., Файзуллин .Т. Эвристический алгоритм деширования шира двойной перестановки // Математические структуры и моделирование: Сб. научн. тр. Под ред. А.К.уца. Омск: Омск. гос. ун-т, 2002. Вып.9. C.62-69.
9. одунов С.К. и др. арантированная точность решения систем линейных уравнений в евклидовых пространствах // Новосибирск: Наука, 1988.
10. Шикин Е.В., Боресков А.В. Компьютерная граика. М.: Мир,1995.
Математические
структуры и моделирование
2003, вып. 11, с. 6787
УДК 532.5.031+519.632.4
ОБТЕКАНИЕ ЕШЕТОК ПОИЗВОЛЬНЫХ
ЛОПАСТЕЙ ИДЕАЛЬНОЙ НЕСЖИМАЕМОЙ
ЖИДКОСТЬЮ
А.С. Толстуха
Various aspets of the numerial solution using finite element method for
the 3-d potential flow of the ideal fluid through the rotor blades of the
turbomahine are disussed. Paper overed the problem stage, wakes influene
and seondary flow questions. Also onsidered disreet solution tehniques and
its onvergene.
1.
Введение
азвитие турбостроительной техники выдвигает повышенные требования к знаниям гидродинамических характеристик рабочих колес и направляющих аппаратов, что в свою очередь стимулирует развитие их гидродинамической теории. Современная вычислительная техника позволяет описать сложные гидродинамические процессы в проточной части турбомашин в пространственной постановке соответствующих задач. Однако реализация наиболее полной модели
течения, описываемой уравнениями Навье-Стокса, требует слишком больших
затрат машинного времени, поэтому в инженерных расчетах они неприемлемы. езультаты многочисленных исследований показывают, что ряд проблем,
возникающих при проектировании решеток, с достаточной степенью точности
могут быть решены и с помощью более простых моделей. Остается лишь вопрос
о пределах их применимости. К числу таких проблем относятся аэроупругие явления в решетках, нестационарные аэродинамические характеристики которых
при безотрывном обтекании с достаточной степенью точности определяются в
рамках модели идеальной жидкости. Как известно [1?, нестационарные аэродинамические характеристики решеток зависят от стационарного поля скоростей,
расчету которого и посвящена настоящая работа.
аботы по методам определения стационарного пространственного течения
в турбомашинах принято вести от работы [2? квазитрехмерная технология,
расчеты проводятся последовательно для течений в ѕтонкихї слоях. Осесимметричное в меридианальном слое, приближенно являющемся средней поверх-
2003
А.С. Толстуха
E-mail: astuniver.omsk.su
Омский государственный университет
абота выполнена в рамках программы ФЦП ѕИнтеграцияї
Документ
Категория
Без категории
Просмотров
6
Размер файла
211 Кб
Теги
решение, алгоритм, проверка, подграфов, приближённого, задачи, поиск, изоморфизм
1/--страниц
Пожаловаться на содержимое документа