Способы снижения вычислительной сложности алгоритмов …
3
множествами
X
1
и
X
2
, на
k-
м шаге алгоритма для каждой перестановки
1
1
k
i
x X
−
∈
с
1
2
k
j
x X
−
∈
множества ребер
1
k
U
и
2
k
U
должны определяться
по формулам
( )
1
1
Г
k
k
U X
=
,
( )
2
2
Г
k
k
U X
=
. Здесь
{
}
1
1
1
\
,
k
k
i
j
X X x x
−
=
∪
{
}
1
2
2
\
k
k
j
i
X X x x
−
=
∪
. Тогда показатель
,
k
i j
S
определяется по формуле
( )
( )
,
1
2
Г
Г
k
k
k
i j
S
X
X
=
∩
S
.
Вычислительная сложность определения количества ребер по
данной формуле составит
O
(
n
2
) при
n m
>
и
O
(
m
2
) при
m n
>
, где
,
n X m U
=
=
[2].
Выполнение операции попарного перемещения двух вершин
x
i
и
x
j
приводит к тому, что в разрез попадают или из разреза уходят
только ребра, связанные с этими вершинами. Поэтому для каждого
парного обмена достаточно определить количество ребер, приходя-
щих в разрез и уходящих из него, и рассчитать их приращение. Тогда
(
)
1
,
,
,
k
k
i
j
i j
i j
S S
S x x
−
= + Δ
,
где
(
)
( )
( )
( )
( )
,
i
j
i
j
i
j
S x x
S x S x
S x S x
+
+
−
−
Δ
= Δ + Δ
− Δ − Δ
— прираще-
ние количества ребер в разрезе при перестановке вершин
x
i
и
x
j
;
( )
( )
,
i
j
S x S x
+
+
Δ
Δ
— количество ребер, приходящих в разрез;
( )
i
S x
−
Δ
,
( )
j
S x
−
Δ
— количество ребер, уходящих из разреза. Подсчет количе-
ства ребер, инцидентных, например вершине
1
1
k
i
x X
−
∈
, и уходящих
из разреза или приходящих в него, подразумевает реализацию сле-
дующего фрагмента алгоритма:
Г :
f
i
u x
∀ ∈
(
: Г ,
f
f
X u
=
(
)
r
f
x X
∀ ∈
(
)
1
2
k
r
i
x X x
−
∈ ⋅
⇒
( )
( )
:
1,
i
i
S x
S x
−
−
Δ
= Δ +
(
)
r
f
x X
∀ ∈
(
)
1
2
k
r
x X
−
∉
⇒
( )
( )
)
:
1 .
i
i
S x
S x
+
+
Δ
= Δ +
Учитывая, что
Г , Г
i
j
x
u A
= ρ
=
, где
A
— количество ребер, ин-
цидентных вершине,
ρ
— количество вершин, инцидентных ребру, и
считая
1
2
/ 2,
k
k
X X n
= =
получим асимптотическую оценку вычис-
лительной сложности данного варианта определения количества ре-
бер в разрезе
O
(
n
).
Оценим возможность формализации данного способа. Пользователь
может описать приведенные выше вычисления несколькими способами,
например множество
1
k
X
определять как
1
1
1
\ ,
k
k
i
X X x
−
=
1
1
,
k
k
j
X X x
= ⋅
