располагаться на одном уровне, чтобы отчетливо было видно распре-
деление этих вершин по уровням [6] для дальнейшей работы сними.
Для вычисления порядковой функции ориентированной сети исполь-
зуется
алгоритм Демукрона
[6].
Наглядно процесс определения уровней вершин можно предста-
вить следующим образом. Нулевой уровень образуют вершины с
по-
лустепеньюзахода
, равной 0. Удалив из сети все вершины нулевого
уровня и исходящие из них дуги, получим сеть, входами которой будут
служить вершины первого уровня исходной сети. Этот процесс нужно
продолжать, пока все вершины не будут распределены по уровням [6].
Алгоритм обрабатывает матрицу смежности
B
вершин графа по-
рядка
n
. В результате получается массив
Ord
порядковых номеров
уровней вершин.
0. Сформировать множество
I
вершин сети. Значение счетчика
уровней
LN
= 0
. Найти суммы элементов матрицы по всем столбцам
матрицы
B
и заполнить ими массив
M
.
1. Если
I
=
∅
, перейти на второй шаг, иначе — к третьему шагу.
2. Определить все вершины с полустепенью захода, равной 0, т.е.
M
= 0
; это будет множество
N
.
3. Присвоить элементам массива
Ord
номера вершин из множества
N
, удалить вершины сэтими номерами из множества
I
.
4. Вычесть из массива
M
строки матрицы
B
, соответствующие
вершинам сномерами из множества
N
(т.е. вершинам из последнего
вычисленного уровня).
5. Увеличить счетчик уровней на единицу:
LN
=
LN
+ 1
.
6. Вернуться к первому шагу.
7. Закончить работу. В результате получено множество
Ord
=
= (
N
1
, . . . , N
LN
)
, где
LN
— число уровней,
N
— множество номеров
вершин данного уровня.
После применения алгоритма фрагмент сети имеет вид, приведен-
ный на рис. 3,
б
.
Преобразование семантическойсети информационных ресур-
сов в граф системы навигации сайта.
По полученной семантической
сети можно построить
граф системы навигации сайта.
Но этот граф
может не отвечать требованиям оптимальной навигации сайта. Поэто-
му следует произвести дельнейшие преобразования.
Граф системы
навигации сайта
— это граф, вершинами которого являются страницы
с навигационной панелью (меню) или отдельными ссылками, по кото-
рым можно переходить на другие страницы (вершины графа). Если по
этому графу строить навигацию сайта, то на каждой странице будет
список ссылок для перехода на следующие страницы и т.д. Опти-
мальная структура навигации веб-сайта должна отвечать следующим
требованиям.
72 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 1
