Способы снижения вычислительной сложности алгоритмов …
5
Обозначим
1
1
1
1
,
,
,
i
i
j
j
k
k
r
r
F x X F x X F x X F x X
=
=
=
=
— множе-
ства вершин, смежных вершинам , , , ... ,
i
j k
r
x x x
x
соответственно.
Будем считать, что
(
)
...
1
i
j
k
r
X X X
X A
= = = = = ρ −
.
В связных гиперграфах количество вершин, одновременно смеж-
ных вершинам
x
i
и
x
j
, будет:
{
}
(
)
(
)
1 1 ,
i
j
i
j
j
j
X X X a X A
a
∪ = +
= ρ − +
где
/
,
j
j
j
j
j
a X X X X
⊆
′ =
— множество вершин, смежных вер-
шине
x
j
и не смежных вершине
x
i
; 0
1.
j
a
≤ ≤
Количество операций сравнения при объединении множеств
X
i
и
X
j
равно
i
j
X X
×
, т. е.
(
)
2
2
1
A
ρ −
. При объединении множеств
{
}
i
j
X X
∪
и
X
k
это количество составит
(
)
i
j
j
k
X a X X
+
×
, т. е.
(
)
(
)
2
2
1 1
j
A
a
ρ − × +
и т. д. Для получения оценки суммарного коли-
чества операций сравнения положим
(
)
...
0 1
j
k
a a
a a
= = = < <
.
Тогда количество операций сравнения, необходимых для определе-
ния
( )
1
l
F X
, будет:
(
)
(
)
2
2
1
2
1 1
2
l
X
i
K A
a i
=
= ρ −
+ −
⎡
⎤
⎣
⎦
∑
.
Асимптотическая оценка сложности формирования множества
cм
l
X
в худшем случае будет
О
(
n
2
), если
1
F x
ограничена константой
и
l
X
ограничена
n
.
Очевидно, что мощность множества
cм
l
X
ограничена величиной
n
. Таким образом, асимптотическая оценка сложности формирования
множества
X
к будет равна
О
(
n
2
).
Однако после включения в множество
l
X
некоторой вершины
x
t
множество
X
к вершин-кандидатов может измениться только за счет
вершин, инцидентных ребрам, приходящим в разрез, и не принадле-
жащих множеству
X
к (рис. 2).
Таким образом, множество
X
к достаточно корректировать, ис-
ключая из него вершину
x
t
и добавляя новые. Если определено мно-
жество
п
t
U
ребер, приходящих в разрез, то множество
п
t
X
инцидент-
ных им вершин определяется по формуле
{
}
п
п
Г \ .
j
t
t
j
t
u U
X
u x
∈
=
U
