С.В. Вельц
8
ся до тех пор, пока в слое не останется одна вершина, либо мы уже не
сможем уменьшить количество вершин (эта ситуация может возник-
нуть, если граф состоит из нескольких связных компонент, не
связанных между собой).
Рис
. 3.
Пример иерархического представления графа
Каждый слой в представлении состоит из: графа
k
k k
G = V ,E
, ко-
торый задает структуру данного слоя; отображения вершин данного
слоя в родительские вершины в следующем слое
1
:
k k
k+
parents V V
;
отображения вершин данного слоя в множество вершин предыдущего
слоя, которые покрываются данной вершиной
1
:
k k
k
children V V
;
весов вершин, которые равны сумме весов покрываемых вер-
шин:
:
k k
+
weight V R
(для нижнего слоя все веса равны единице).
Алгоритм 2.
buildHierarchicalGraph – жадный алгоритм
построения иерархического представления графа.
Вход
:
:
0,1 .
G= V,E ,w E
Выход:
2
0
0
...
0
L
L L
HG= G = V ,E , ,G = V ,E
,
L
― количество слоев,
1
:
1...
k k
k
parents V V ,k = L
1
:
1...
k k
k
children V V ,k = L
:
1...
k k
+
weight V R ,k = L
1. Инициализация
HG G
0
k
k
G G
1,
1..
k
k
weight i = i = V
2. Построение слоев.
