СКАЧАТЬ:  3laba-mod-teoriya.zip [60,66 Kb] (cкачиваний: 43)

Топологическая декомпозиция структур АСУ

Проведение топологической структуры АСУ, представленной в виде ориентированной графа G(V), связано с выделением в этой структуре сильно связанных подсистем. Ориентированный граф G(V) называется сильно связанным, если для любых вершин i, j существует путь из вершин i в вершину j.

Для рассмотрения основного  алгоритма декомпозиции целесообразно ввести следующие понятия.

Множество вершин, достижимых из вершин i, называется достижимым множеством R(i). Достижимое множество определяется следующим образом:

                                 (1)

где G(i)- множество вершин, достижимых из вершины i с использованием пути длиной, равной единице; - множество вершин, достижимых из вершины i с помощью путей длиною .

При этом предполагается, что сама вершина i достижима с помощью пути, длиною 0 и включена во множество R(i). Это предположение отражается в соотношении (1) введением (i).

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

Контрдостижимым множеством Q(i) графа G(V) называется множество таких вершин, когда из любой вершины этого множества можно достигнуть вершину i.

Аналогично построению R(i) можно построить Q(i), используя следующее выражение:

 ,                                (2)

где G^-1(i)- множество вершин, из которых можно достигнуть i-ую вершину с помощью путей, длина которых равна единице; G^-2(i)- то же самое, но с помощью путей, длина которых равна двум и т.д.(рис.1).

Так как R(i) является множеством вершин, достижимых из i-ой вершины, а Q(i)-множеством вершин, из которых можно достичь вершину j, то множество R(i) n Q(j) является множеством таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от i-той вершины к j-той, что иллюстрируется рис.2. Эти вершины называется существенными или неотъемлемыми относительно двух кольцевых вершин i и j.

В свою очередь, множество

R(i) Q(j)                                                      (3)

определяет сильно связный подграф графа G(V), содержащий i-тую вершину, поскольку все существенные вершины, принадлежащие множеству (3), достижимы из i-той вершины и, кроме того, из каждой такой вершины достижима вершина i, т.е все эти вершины взаимодостижимы (рис.3).     

Рис.1. Вид достижимых и       Рис.2. Вид существен-    Рис.3. Вид сильно связ-

контрдостижимых мно-          ных вершин                      ного графа

жеств

Из введенных выше определений имеем следующий алгоритм декомпозиции.

Алгоритм декомпозиции:

     1. В  исходном графе G(V) производим нумерацию вершин.

     2. Для i-той вершины (i=1) определяем множество R(1) и множество Q(1).

     3. Находим сильно связный подграф G₁, включающий множество вершин V ₁=R(1) Q(1).

1. Все вершины, принадлежащие G₁(V₁), удаляются из исходного графа G(V).

Далее пункты 2,3,4 повторяются для i=2,3,4…до тех пор, пока все вершины исходного графа не будут сгруппированы с соответствующие сильно связные подграфы.