В.А. Овчинников, Г.С. Иванова
6
Оценим возможность использования этого преобразования в по-
следовательном алгоритме разрезания гиперграфа [4]. Пусть гипер-
граф разрезан на два куска
к
1 1
1
,
H X U
и
к
2 2
2
,
H X U
. Необходимо
проверить, уйдет ли из разреза ребро
1
2
j
u U U
при включении
вершины
x
i
, инцидентной этому ребру и принадлежащей множеству
X
1
, в множество
X
2
. Это произойдет при условии, что справедливо
следующее утверждение: все вершины множества
Г
j
j
X U
будут
принадлежать множеству
X
2
, если добавить в него вершину
x
i
, т. е.
2
j
i
X X x
. Перефразируем утверждение: все вершины множества
Г
j
j
X U
, кроме вершины
x
i
, принадлежат множеству
X
2
, т. е.
2
\
j
i
X x X
.
Таким образом обоснована возможность применения рассматри-
ваемого преобразования в данном алгоритме. В общем случае мы
имеем два логически эквивалентных фрагмента вида
2
j
i
X X X
и
2
\
j
i
X X X
,
первый из которых является заменяемым, а второй — заменяющим.
Формальное описание данного преобразования представляет со-
бой множество синтаксических правил, задающих структуру рас-
смотренных выше заменяемых фрагментов и синтаксическое правило
заменяющего.
Синтаксическое описание заменяемого
2
j
i
X X X
(
2
j
i
X X x
)
и заменяющего
2
\
j
i
X X X
(
2
\
j
i
X x X
) фрагментов имеет вид:
<Заменяемый фрагмент 1> ::= <Объект 1>
<Объект 2> • <Объект 3>,
<Объект 1> ::= <Множество 1>,
<Объект 2> ::= <Множество 2>,
<Объект 3> ::= <Множество 3> \ <Элемент множества>,
<Заменяющий фрагмент> ::= <Объект 1>
\
<Объект 3>
<Объект 2>.
Реализацию оптимизирующего преобразования формально
опишем в виде
правила трансформации
. Это правило должно
включать условие существования, проверять условия контекстной
зависимости, из множества лексем, полученных при разборе заме-
няемого фрагмента, строить заменяющий фрагмент и выполнять
подстановку.
Поскольку рассмотренное выше преобразование является кон-
текстно свободным, его решающее правило будет иметь вид
(
A
) (
),
