Методика выбора программного обеспечения компьютерных сетей
5
стадиях выбора структуры ПО. Задача заключается в нахождении
наибольшей по весу частичной трансверсали семейства
, а по-
скольку
,
M p
матроид, то для этого можно применить жад-
ный алгоритм.
Общая комбинаторная схема для нахождения частичной транс-
версали
p
с наибольшим весом такова. Просматриваются все
q
ребер
,
i
j
u v
q
двудольного графа
H
с вершинами
1
,...,
q
u u
,
1
,...,
M
v v
, причем
i
m
O P
,
1, ...,
i
q
. Находится паросочетание
графа
H
. Затем отыскивается чередующаяся цепь относительно па-
росочетания с началом в
i
.
В результате применения жадного алгоритма получается
наибольшая по весу
w
частичная трансверсаль .
p
Разбиение программы.
Допустим, решена задача поиска общей
трансверсали признаков ПО и выполнено расширение подмножеств
'
'
1
,...,
M
до подмножеств
1
,...,
M
, причем
1
...
.
M
Процедура отыскания общего описания
p
архитектуры для
H
се-
мейств признаков, основанная на поиске максимального нуль-
единичного потока в сети
,
N V B
(построение этой сети см.
в [3–5]), вовсе не гарантирует получения разбиения спецификации
согласно найденному представлению. Теперь, на последнем этапе
необходимо найти разбиение
, соответствующее описанию
p
.
Это разбиение назовем окончательным определением семейства
'
1
,...,
M
расширенных подмножеств.
Обозначим через
1
,...,
n
последовательность различных эле-
ментов пересечений множеств
'
'
1
,...,
M
, а через
1
,...,
n
S S
семейство непустых непересекающихся множеств. При этом имеют
место биекции
j
j
S
, где
1,..., ,
j
j
n
совокупность пересе-
кающихся множеств семейства
'
, таких, что
j
элемент пересе-
чения,
1
, ...,
, ...,
j
n
нe обязательно не пересекаются.
Рассмотрим
q
-элементное множество
, для которого
являет-
ся разбиением и
1
n
j
j
q S
. Упорядочим элементы
1
,...,
q
по
невозрастанию
неотрицательных
вещественных
весов:
1
...
q
w
w
.
