В.А. Овчинников
4
или
1
1
1
\
k
k
i
j
X X x x
−
=
⋅
и т. п. Учтем тот факт, что этот способ может
быть применен к алгоритмам, реализующим последовательное форми-
рование графа результата посредством включения / исключения вершин
или ребер. Это еще больше усложняет распознавание заменяемого
фрагмента. Однако существует возможность выявления информации,
которая укажет на принадлежность алгоритма к указанному классу. Та-
кой анализ целесообразно выполнять по уграфу алгоритма [3, 4], по-
скольку он характеризуется высокой степенью формализации. Анали-
зируется наличие в уграфе алгоритма цикла, содержащего операцию
добавления или удаления вершины или ребра и операцию вычисления
ее характеристик. Формальное правило такого анализа имеет вид [5]:
(
)
( )
( )
3 3 3
3
мод
хар
,
/ ,
,
,
G
G
y
i
j
i
j
G X U G t x Op t x Op x x X i j
⎡
⎤
∃
∈
∈
∈
∈ ≠
⎣
⎦
&
где
(
)
3 3 3
,
G X U
— конструкция типа «цикл» уграфа
y
G
алгоритма;
( )
i
t x
— операция, соответствующая вершине этого цикла;
мод
G
Op
—
множество операций модификации графовых моделей;
хар
G
Op
— мно-
жество операций определения характеристик графовых моделей.
При обнаружении подобных конструкций в алгоритме целесооб-
разно выдать разработчику запрос, предоставив ему возможность вы-
полнить соответствующее преобразование вручную.
Второй способ
— использование рекуррентных процедур для
определения состава таких множеств, элементы которых в результате
выполнения преобразований меняются частично. Данный способ реа-
лизован, например, в последовательном алгоритме разрезания гипер-
графа [2]. На текущем шаге алгоритма множеством кандидатов к
X
на
включение в формируемое подмножество
l
X
куска гиперграфа
l
H
являются вершины, которые смежны вершинам, уже вошедшим в ку-
сок. При наличии в аналитическом представлении гиперграфа образа
1
F X
множества вершин относительно предиката смежности множе-
ство вершин-кандидатов определяется по формуле
cм
к
\ ,
l
l
X X X
=
где
cм
l
X —
множество вершин, смежных вершинам:
( )
cм
1
1
,
.
l
i
i
l
l
X F X F X x X
=
= ∪ ∈
Распишем процесс получения множества
cм
l
X
:
( )
{
}
1
1
1
1
1
...
,
l
i
j
k
r
F X F x F x F x
F x
= ∪ ∪ ∪ ∪
где
{
}
, , , ... ,
.
i
j k
r
l
x x x
x X
=
