Алгоритм упорядочивания системы.
G-1(i) включает подмножество N0. Пусть их будет l1 штук.
В результате получим тот же самый граф, но с переставленными номерами вершин. В ру этой матрицы смежности будет иметь треугольный вид такой что aij=0, если i>j. Пример: Рассмотрим неупорядоченный граф. После упорядочивания получаем: Для описания анализа структуры системы и потоков информации в ней будем рассматривать для простоты движение документов в ИС: Источники – документы, которые внутри системы формируются на основании других документов. Следовательно, все документы делятся на 3 класса. 1) исходные – те, которые поступают в систему 2) внешние – которые являются результатом работы системы 3) промежуточные документы, которые будут являться результатом переработки информации, но из системы не выдаются. Совокупность входных и выходных элементов составляет базис системы. Базис не зависит от программ переработки информации и определяется только функциями самой системы. Между документами в системе существуют отношения вхождения и отношения порядка. Отношение вхождения Xj=Xj1, Xj2,…,Xjn означает, что документы Xj образуются непосредственно из множества документов Xj1, Xj2,…,Xj. Отношения порядка Xji означает, что документы Xj следуют за документами Xi следуют Xj, может быть образован только после образования Xi.
Если поставить в соответствие документы вершин графа, а дуги отношения вхождения и пор-ка, то полученные информационный граф, отображает взаимодействие элементов в ИС. Введем понятие порядка элемента. Пусть структура графа задается матрицей смежности А. Из рассмотрения различной степени А получим следующие свойства и параметры графа: 1) Порядком Пj: элементами j называется длина наибольшего пути из элементов i в элемент j для любого i=1,2…,n,i≠j. Функциональный смысл Пj означает номер такта, к которому готовы все документы, формирующие j-ый документ. Формально Пj вычисляется как:
Пример:
П1=0 П2=П3=1 П4=2 П5=3
2) Число N=max П1 для любого j называется порядком информационного графа. N- тактный граф: Свойство: AN=0 AN+1=0 3) Признаком контура служит появление ненулевое элементов на главной диагонали любой из матриц Ак. Появление контура – ошибка информационного графа. 4)
5) Если Если 6) Если i=j и 7) Число путей от документа i к документу j определяется элементом aij, матрицы Ак. 8) Введем Элемент 9) Элементы Сумма элементов j-го столбца определяет все документы, которые участвуют в формировании j-го документа. Аналогично, все элементы i-той строки
10) 11)
Имея порядок элементов получим матрицу 12) Анализ структур всех путей, которые существуют в информационном графе позволяет выявить на дублирование. Связи, так и избыточные документы. Это необходимо для снижения потока информации и повышения его надежности и оперативности системы. R(i) – множество вершин достижимых из вершины i – достижимое множество.
R(i) строится последовательно, начиная слева направо, до тех пор, пока текущей множество R не перестанет увеличиваться. Следовательно, получится полное достижимое множество. Число объединений зависит от графа, Р не должно превосходить число вершин. Q(i) – контрдостижимое множество, это множество вершин из любой, из которых, можно достичь вершины i.
Показатели степени означают длину пути, по которому можно попасть в i. Это объединение множеств выполняется последовательно слева направо до тех пор, пока очередная операция объединения не перестанет изменять множество Q. q≤количества вершин. Если рассмотреть Эти вершины называются существенными относительно i к j.
На этом определении построен алгоритм декомпозиции/определения сильно связанных подграфов. 0) упорядочивание вершин 1) берем первую вершину и для нее строим 2) определяем множество 3) из графа выбрасываем все вершины принадлежащие V1. 4) Повторяем эту процедуру для оставшихся вершин с меньшими номерами.
Это делаем, пока вершины начала графа не будут структурированы в сильно связанный подграф. R(1) = (1,2,4,5,6,7,8,9,10) Q(1) = (1,2,3,5,6)
R(3) = (3,4,7,9) Q(1) = (3) V2 = 3
R(4) = (4,7,9) Q(4) = (4,7,8,9,10) V3 = 4,7,9
R(8) = (8,10) Q(8) = (8,10) V4 = (8,10) Таким образом выделили из подсистемы части графа на основании сильных связей между ними, то есть связи между этими элементами внутри выделенной подсистемы или подграфов значительнее, чем связи между этими элементами и элементами, не входящими в подграф/подсистему. Во время разработки системы большую часть это работы выполняет сам пользователь, даже если этого не осознает, так как он обладает информацией о функциональном назначении каждой подсистемы исследуемого объекта. Но в случае большой размерности системы можно понизить ее размерность в помощью алгоритма декомпозиции, следовательно уменьшив затраты на вычисления.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|