соединение компонент связности добавлением ребер, кроме проверки
условия соединения разных компонент требует коррекции имен или
номеров компонент в
Р
X
или
B
соответственно.
Вычислительная сложность операции коррекции равна
O
(
n
)
. По-
кажем это. Пусть рассматривается операция добавления в неориенти-
рованный граф, состоящий из нескольких компонент связности, ребра
u
j
, у которого
Γ
u
j
=
{
x
3
, x
6
}
,
Γ
u
j
∈
Γ
U
. Определив, что
Р
x
3
=
Р
x
6
,
мы установили возможность соединения компонент связности, мно-
жества вершин которых
Y
1 =
{
x
1
, x
3
, x
5
}
и
Y
2 =
{
x
4
, x
6
}
соответ-
ственно. Если подмножеству вершин новой компоненты связности мы
хотим дать имя
Y
1
, то образы
Р
x
i
необходимо переопределить:
Р
x
i
=
Y
1 :
Р
x
i
=
Y
2
/x
i
∈
X.
Таким образом, вычислительная сложность слияния
n
компонент,
каждая из которых содержала по одному элементу, будет равна
O
(
n
2
)
.
Для уменьшения числа операций просмотра элементов образа
Р
X
нужно иметь возможность за одну операцию определять первый эле-
мент каждого подмножества и непосредственно переходить от теку-
щего элемента подмножества кследующему. Для достижения этой
цели можно задать два предиката. Первый из них должен позволять с
вычислительной сложностью
O
(1)
находить начальный элемент под-
множества, а второй — для каждого элемента подмножества указывать
следующий.
Обозначим эти предикаты
F
(
Y,
{
Y j
1
}
)
и
N
(
X, X
)
. Истинность
F
(
Y j, x
k
)
означает, что первым элементом подмножества
Y j
при за-
дании его перечислением элементов является элемент
x
k
. Значение
N
(
x
i
, x
l
)
будет истинным, если для элемента
x
i
следующим при пе-
речислении элементов подмножества будет элемент
x
l
. Для нашего
примера образом множества
Y
относительно предиката
F
(
Y,
{
Y j
1
}
)
будет
FY
=
{
x
1
, x
4
, x
2
}
, а образом множества
X
относительно преди-
ката
N
(
X, X
)
будет
NX
=
{
x
3
,
0
, x
5
, x
6
,
0
,
0
}
.
Число операций слияния подмножеств зависит от соотношения
мощностей подмножеств и порядка их переименования. Если после-
довательно выполнять слияние двух подмножеств, первое из которых
состоит из одного элемента, а второе из
i
элементов, где
i
= 1
, n
−
1
,
то число операций переименования будет равно
n
(
n
−
1)
/
2
. Число
этих операций можно существенно сократить, если при слиянии двух
подмножеств переименовывать подмножество меньшей мощности. То-
гда при соединении двух компонент связности ребром
u
j
, у которого
Γ
u
j
=
{
x
l
, x
k
}
и
Р
x
l
=
Р
x
k
, необходимо проверить
|
Y t
|
>
|
Y r
|
, где
Y t
=
Р
x
l
и
Y r
=
Р
x
k
, и при удовлетворении этого условия выполнить
процедуру
(
∀
x
i
∈
Y r
)
Р
x
i
:=
Р
x
l
,
60 ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4
