Алгоритм упорядочивания системы.

1. Выделяем подмножество 0го уровня N₀, которое содержит вершины, у которых множество левых инциденций G^-1(i)=0. Пусть их будет l₀ штук
2. Нумеруем эти вершины от 1 до l₀.
3. Выделяем подмножество N₁, которое содержит те вершины i, у которых множество

G^-1(i) включает подмножество N₀. Пусть их будет l₁ штук.

1. Нумеруем эти вершины от l₀+1 до l₀+ l₁
2. Выделяем подмножество N₂ тех вершин i, для которого множество левых инциденций включено в объединение множеств N₀ и N₁

Таких вершин l₂

1. Нумеруем эти вершины от l₀+l₁+1 до l₀+l₁+l₂ и так далее, пока не будет пронумерованы все вершины.

В результате получим тот же самый граф, но с переставленными номерами вершин. В ру этой матрицы смежности будет иметь треугольный вид такой что a_ij=0, если i>j.

Пример: Рассмотрим неупорядоченный граф.

После упорядочивания получаем:

Для описания анализа структуры системы и потоков информации в ней будем рассматривать для простоты движение документов в ИС:

Источники – документы, которые внутри системы формируются на основании других документов. Следовательно, все документы делятся на 3 класса.

1) исходные – те, которые поступают в систему

2) внешние – которые являются результатом работы системы

3) промежуточные документы, которые будут являться результатом переработки информации, но из системы не выдаются.

Совокупность входных и выходных элементов составляет базис системы. Базис не зависит от программ переработки информации и определяется только функциями самой системы. Между документами в системе существуют отношения вхождения и отношения порядка.

Отношение вхождения X_j=X_j1, X_j2,…,X_jn означает, что документы X_j образуются непосредственно из множества документов X_j1, X_j2,…,X_j.

Отношения порядка X_ji означает, что документы X_j следуют за документами X_i следуют X_j, может быть образован только после образования X_i.

Если поставить в соответствие документы вершин графа, а дуги отношения вхождения и пор-ка, то полученные информационный граф, отображает взаимодействие элементов в ИС.

Введем понятие порядка элемента.

Пусть структура графа задается матрицей смежности А. Из рассмотрения различной степени А получим следующие свойства и параметры графа:

1) Порядком Пj: элементами j называется длина наибольшего пути из элементов i в элемент j для любого i=1,2…,n,i≠j.

Функциональный смысл Пj означает номер такта, к которому готовы все документы, формирующие j-ый документ. Формально Пj вычисляется как:

, тогда: . В матрице «К» к j-ому элементу есть поступление информации, а в матрице «к+1» к j-ому элементу поступления нет.

Пример:

 

 

П₁=0 П₂=П₃=1 П₄=2 П₅=3

 

2) Число N=max П₁ для любого j называется порядком информационного графа.

N- тактный граф:

Свойство: A^N=0 A^N+1=0

3) Признаком контура служит появление ненулевое элементов на главной диагонали любой из матриц А^к. Появление контура – ошибка информационного графа.

4) – j-ый документ является исходным

– j-ый документ получен на основе элементов

– сумма элементов i-ой строки матрицы А^к

5) Если – j-ый документ является конечным/входящим.

Если – число документов, в которые входит i-ый документ

6) Если i=j и , то i-ый документ является изолированным в нашей системе.

7) Число путей от документа i к документу j определяется элементом a_ij, матрицы А^к.

8) Введем c элементами

Элемент матрицы – число путей всевозможной длины от документа i к документу j.

9) Элементы матрицы определяет все документы, которые участвовали в формировании j-го документа.

Сумма элементов j-го столбца определяет все документы, которые участвуют в формировании j-го документа. Аналогично, все элементы i-той строки определяют все документы, в формировании которых участвовал i-тый документ.

10) - максимальное значение порядков элементов не равных 0, i-той строки. Определяют номер такта, после которого i-тый документ не используется в системе.

11) – число тактов, в течении которых, i-тый документ находился в системе:

Имея порядок элементов получим матрицу

12) Анализ структур всех путей, которые существуют в информационном графе позволяет выявить на дублирование. Связи, так и избыточные документы. Это необходимо для снижения потока информации и повышения его надежности и оперативности системы.

R(i) – множество вершин достижимых из вершины i – достижимое множество.

– множество вершин, достижимых из вершины i по путям длиной k.

R(i) строится последовательно, начиная слева направо, до тех пор, пока текущей множество R не перестанет увеличиваться. Следовательно, получится полное достижимое множество. Число объединений зависит от графа, Р не должно превосходить число вершин.

Q(i) – контрдостижимое множество, это множество вершин из любой, из которых, можно достичь вершины i.

– контрдостижимое множество длиной 1, построенное на контрдостижимом множестве для одной вершины i.

Показатели степени означают длину пути, по которому можно попасть в i.

Это объединение множеств выполняется последовательно слева направо до тех пор, пока очередная операция объединения не перестанет изменять множество Q. q≤количества вершин.

Если рассмотреть – это означает множество вершин, каждая из которых принадлежит по крайней мере одному пути из вершины i в вершину j.

Эти вершины называются существенными относительно i к j.

– означает сильно связный подграф заданного графа j, в который входит вершина i, так как все существенные вершины принадлежат этому множеству достижимых из вершины i и из любой вершины этого множества достижима вершина i.

На этом определении построен алгоритм декомпозиции/определения сильно связанных подграфов.

0) упорядочивание вершин

1) берем первую вершину и для нее строим

2) определяем множество

3) из графа выбрасываем все вершины принадлежащие V₁.

4) Повторяем эту процедуру для оставшихся вершин с меньшими номерами.

Это делаем, пока вершины начала графа не будут структурированы в сильно связанный подграф.

R(1) = (1,2,4,5,6,7,8,9,10)

Q(1) = (1,2,3,5,6)

=(1,2,5,6)

 

R(3) = (3,4,7,9)

Q(1) = (3)

V₂ = 3

 

R(4) = (4,7,9)

Q(4) = (4,7,8,9,10)

V₃ = 4,7,9

 

R(8) = (8,10)

Q(8) = (8,10)

V₄ = (8,10)

Таким образом выделили из подсистемы части графа на основании сильных связей между ними, то есть связи между этими элементами внутри выделенной подсистемы или подграфов значительнее, чем связи между этими элементами и элементами, не входящими в подграф/подсистему.

Во время разработки системы большую часть это работы выполняет сам пользователь, даже если этого не осознает, так как он обладает информацией о функциональном назначении каждой подсистемы исследуемого объекта. Но в случае большой размерности системы можно понизить ее размерность в помощью алгоритма декомпозиции, следовательно уменьшив затраты на вычисления.