ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
136
С учетом сказанного выше множество ребер гиперграфа
U
целе-
сообразно представить в виде двусвязного списка
L
D
[1].
Также в ви-
де двусвязных списков {
L
j
/
j
= 1,
m
}
представим множества вершин
X
j
= Г
u
j
,
инцидентных каждому ребру
u
j
(
рис. 1).
Рис. 1. Двусвязный список двусвязных списков для хранения множеств
<
U
,
W
,
⎢
Г
U
⎢>
и Г
U
Обозначим через
x
i
вершину, удаляемую на
i
-
м шаге алгоритма.
Поиск удаляемой вершины
x
i
во множестве Г
U
подразумевает опре-
деление ребер
U
i
= Г
xi
,
инцидентных этой вершине. Определение
множества ребер
U
i
выполняется по множеству образов Г
X
,
т. е. не
относится к синтезируемой структуре.
На
i
-
м шаге алгоритма над множеством ребер
U
и множеством
подмножеств их образов Г
U
будут выполняться следующие опера-
ции:
•
определение в множестве
U
ребра
u
k
с максимальным весом;
•
поиск каждого ребра
u
j
∈
U
i
в множестве
U
;
•
поиск удаляемой вершины
x
i
в образах Г
u
j
;
•
удаление этой вершины;
•
определение «пустых» ребер;
•
поиск «пустого» ребра в множестве
U
;
•
удаление «пустого» ребра.
Для определения «пустых» ребер необходимо знать мощность
множества Г
u
j
каждого ребра
u
j
∈
U
i
.
Вычислительная сложность та-