щий одну вершину сполустепенью захода, равной нулю, из которой
достижимы все остальные вершины.
Пусть существует вершина
I
i
сполустепенью исхода, не равной ну-
лю. Тогда
семантическим
j
-м подразделом сети
называется множе-
ство вершин, достижимых из вершины
I
i
. Семантические подразделы
называются
пересекающимися
, если существует вершина, принадле-
жащая обоим подразделам. Эта вершина называется
общей
.
Множество вершин из уровня
i
, связанных отношением непосред-
ственной достижимости с вершиной из уровня
i
+ 1
, называется
мно-
жеством родительских вершин
.
Множество вершин из уровня
i
+ 1
, связанных отношением не-
посредственной достижимости с вершиной из уровня
i
, называется
множеством дочерних вершин.
Если нужно, чтобы какие-либо подразделы сети не имели общих
вершин, то используется этот алгоритм. Определяется вершина с по-
лустепенью исхода, не равной нулю (это может быть вершина из ну-
левого уровня), относительно нее строится семантический подраздел
сети. Берется еще одна вершина, принадлежащая тому же уровню, и
относительно нее также строится семантический подраздел сети, и так
поступают со всеми вершинами данного уровня. Далее ищутся общие
вершины. Каждая такая вершина анализируется, так же анализирует-
ся ее связь с родительскими вершинами. В зависимости от решения
разработчика происходит следующие: удаляется одна дуга; вершина
делится на две; ничего не меняется и осуществляется переход к сле-
дующей вершине.
Этот алгоритм применим для всех других уровней
1
.
0. Составить матрицу смежности
B
, посчитать сумму элементов
по всем столбцам, заполнить ими массив
M
.
1. Определить все вершины с полустепенью захода, большей еди-
ницы, т.е.
M
i
>
1
; это будет множество
I
cross
.
2. Для каждой вершины множества
I
cross
анализируются связи с
родительскими вершинами.
3. Из множества дуг
L
= ((
I
p
1
, I
i
cross
)
, . . . ,
(
I
pm
, I
i
cross
))
удаляются
ненужные дуги, а из матрицы
M
— элементы, соответствующие этим
дугам.
4. Если нужно еще делить вершины на две, то переходим к пятому
шагу, иначе — к девятому шагу.
5. Определяем все вершины с полустепенью захода, большей еди-
ницы, т.е.
M
i
>
1
; это будет множество
I
cross
.
1
Для упрощения алгоритма будем считать, что вершины можно делить только на
две части, а если одну из полученных вершин нужно разделить еще раз, то для этого
надо повторить алгоритм разделения.
74 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 1
