ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
139
В результате объединения по вершинам
yv
i
=
zd
j
графов
DL
G
G
({
Z
D
,
Z
L
}, {
Y
D
,
Y
L
},
FZ
D
,
FZ
L
)
и
V
G
G
(
Z
V
,
Y
V
,
FZ
V
)
получим модель ком-
бинированной структуры –
двусвязный список двусвязных списков с
вектором прямого доступа:
DLV
G
G
(
Z
1,
Y
1,
FZ
1)
=
DL
G
=
G
({
Z
D
,
Z
L
}, {
Y
D
,
Y
L
},
FZ
D
,
FZ
L
)
∪
V
G
G
(
Z
V
,
Y
V
,
FZ
V
),
где
Z
1
= {
Z
D
,
Z
L
,
Z
V
},
Y
1
= {
Y
D
,
Y
L
,
Y
V
},
FZ
1
= {
FZ
D
,
FZ
L
,
FZ
V
}.
На рис. 3 показана модель после удаления «пустого» ребра
u
k
.
Рис. 3. Модель двухуровневой структуры двусвязный список двусвяз-
ных списков с вектором прямого доступа:
yd
j
′
↔ <
u
j
,
w
j
,
⎢
Г
u
j
⎢
,
r
= |
U
|
В структуре поиск вершины в образе ребра
требует
⎜
Г
u
⎜
=
A
≤
n
операций сравнения. С учетом числа
⎜
Г
x
⎜
=
ρ ≤
m
ребер, инцидентных
вершине
x
i
,
ее поиск и удаление будет осуществляться с вычислитель-
ной сложностью
Q = A
ρ
.
Поиска удаляемой вершины
x
i
в образе Г
u
j
можно избежать, если задать принадлежность элемента
x
i
множеству
образов Г
U
отношением
i
R
G
«
координата элемента в подмножестве
X
j
–
координата этого элемента в следующем подмножестве».
По-
скольку количество элементов каждого подмножества
X
j
различно, для
представления значения
i
R
G
целесообразно использовать односвязные
списки
S
i
.
Подмножество
K
i
координат элементов
x
i
является адресами