между куском графа
,
представляющим базовую конструкцию
,
и к ус
-
ком
,
являющимся моделью сложной
,
иерархически вложенной струк
-
турной конструкции
,
с точностью до внутренних вложенных конструк
-
ций
.
Доказательство гомеоморфизма кусков можно выполнить
,
свернув
(
факторизовав
)
вложенные конструкции и установив изоморфизм кус
-
ков
.
Под операцией свертки
(
факторизации
)
структурной конструкции
,
вложенной в данную
,
будем понимать свертку в одну всех вершин
X
j
куска графа
G
j
(
X
j
, U
j
)
,
являющегося моделью этой конструкции
,
та
-
ким образом
,
что
factor
(
G
j
(
X
j
, U
j
)
.
) =
G
j
(
X
j
, U
j
)
,
если
|
X
j
|
= 1
,
G
F
j
(
X
F
j
, U
F
j
)
,
если
|
X
j
|
>
1
,
где
X
F
j
=
{
x
n
}
, x
n
—
единственная вершина
,
заменяющая свертывае
-
мый кусок графа
;
t
(
x
n
)
=“
обработка данных
”,
t
(
x
n
)
—
тип вершины
x
n
;
U
F
j,j
=
∅
,
U
F
j,j
—
множество внутренних ребер
(
петель
)
одновершинно
-
го куска
;
U
F
j
=
U
F
j,k
=
{
u
(
∅
, x
n
)
, u
(
x
n
,
∅
)
}
=
U
j
\
U
j,j
=
U
j,k
,
U
F
j,k
,
U
j,k
—
множества внешних ребер одновершинного и свертываемого кусков
;
U
j,j
—
множество внутренних ребер свертываемого куска
.
При таком преобразовании сохраняется основное свойство моделей
структурных алгоритмов
:
S
(
X
j
) =
P
(
X
j
) =
S
(
X
F
j
) =
P
(
X
F
j
) = 1
.
Формальное описание структуры
“
структурного
”
алгоритма и пра
-
вила разбора таких алгоритмов определяет аксиоматика операций
свертки над сложными структурными конструкциями
:
factor
(
G
0
) =
G
0
F
=
G
0
,
factor
(
G
i
∈ {
G
1
, G
1
F
, G
2
, G
2
F
, G
3
, G
3
F
}
) =
G
0
F
,
factor
(
{
G
k
} ⊂
G
1
С
&
G
k
∈ {
G
2
F
, G
3
F
}
) =
G
1
F
,
factor
(
G
01
, G
02
⊂
G
2
C
&
G
01
, G
02
∈ {
G
1
, G
1
F
, G
2
, G
2
F
, G
3
, G
3
F
}
) =
=
G
2
F
,
factor
(
G
0
⊂
G
3
C
&
G
0
∈ {
G
1
, G
1
F
, G
2
, G
2
F
, G
3
, G
3
F
}
) =
G
3
F
,
где
G
1
C
—
кусок управляющего графа
,
соответствующий линейной
последовательности операторов обработки данных
,
операторов ветвле
-
ния и операторов цикла
-
пока
(
в свою очередь
,
возможно
,
включающих
внутренние структурные конструкции
),
т
.
е
.
G
1
C
=
Ch
(
G
i
, G
j
)
,
где
С
h
—
последовательность кусков
,
являющихся моделями указанных
выше последовательных операторов
,
причем
(
∀
k
=
i, j
)
G
k
∈ {
G
0
, G
2
, G
2
F
, G
3
, G
3
F
}
;
G
2
C
—
кусок управляющего графа
,
соответствующий оператору ветв
-
ления
(
сложной структурной конструкции типа
G
2
)
,
ветви которого
70 ISSN 0236-3933.
ВестникМГТУ им
.
Н
.
Э
.
Баумана
.
Сер
. “
Приборостроение
”. 2005.
№
3
