6. Если
I
cross
=
∅
, то переходим на седьмой шаг, иначе — на
девятый.
7. Делим вершины на две, добавляем в матрицу смежности строку
и столбец, соответствующие этой вершине.
8. Если нужно еще делить вершины на две, то переходим к пятому
шагу, иначе — к девятому шагу.
9. Завершение работы: получение новой матрицы смежности
M
и
графа
G
= (
I, L
)
.
Алгоритм объединения для уменьшения глубины навигации.
Если степень глубины навигации неудовлетворительна, то можно ис-
пользовать следующий алгоритм.
Существует граф информационных ресурсов
G
= (
I, L
)
. Суще-
ствуют две вершины
I
i
,
I
k
и дуга
(
I
i
, I
k
)
, т.е.
I
k
принадлежит более
низкому уровню иерархии, чем
I
i
. Если мы хотим уменьшить степень
глубины навигации или число узлов (понятий) на одном уровне, то эти
вершины можно объединить:
Level
j
— множество вершин
j
-го уровня
иерархии,
j
= (1
, . . . , LN
)
.
1. Существует граф
G
(
I, L
)
, определяем уровень, который будем
объединять споследующим.
2. Определяем множество дуг
(
I
i
, I
k
)
, где
I
i
∈
Level
j
, а
I
k
∈
Level
j
+1
.
3. Объединяем попарно вершины (если необходимо).
4. Если нужно объединять еще, то переходим ко второму шагу, если
не нужно — к пятому шагу.
5. Завершение работы: получение оптимизированного графа
G
=
= (
I, L
)
.
Алгоритм объединения для уменьшения широты навигации.
Если число понятий (пунктов меню) на одном уровне слишком боль-
шое, то можно использовать следующий алгоритм.
Существует граф информационных ресурсов
G
= (
I, L
)
. Суще-
ствует множество вершин, принадлежащих
j
-му уровню иерархии,
имеющих одну и ту же
родительскуювершину
(т.е. имеющих полу-
степень захода, равную единице). Если мы хотим уменьшить число
узлов (понятий) на одном уровне, то эти вершины можно объединить:
Level
j
— множество вершин
j
-го уровня иерархии,
j
= (1
, . . . , LN
)
.
1. Существует граф
G
(
I, L
)
, определяем уровень, число узлов на
котором нужно сократить.
2. Определяем
I
i
∈
Level
j
и множество вершин
(
I
k
)
∈
Level
j
+1
,
где полустепень захода равна единице и все вершины из множества
(
I
k
)
связаны отношением непосредственной достижимости с
I
i
.
3. Объединяем вершины (если необходимо).
4. Если нужно еще объединить вершины, переходим на второй,
если не нужно — на пятый шаг.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 1 75
