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

Проведение топологической декомпозиции структуры БСУ на основе представления её в виде ориентированного графа G(V) связано с выделением в ней отдельных сильно связанных подсистем.

Мн-во вершин, достижимых из вершины i, называется достижимым мн-вом R(i)

R(i) = i G(i) G²(i) … G^p(i) …; (2-1)

G(i) - мн-во вершин, достижимых из вершины i с использованием путей длиной =1

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

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

Объединения в (2-1) прекращаются как только R(i) перестанет увеличиваться по размеру при очередной операции объединения.

С этого момента последующие операции не будут давать новых элементов множеству. Образовано достижимое R(i).

Число объединений зависит от графа, но число p не может быть больше числа вершин в графе.

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

Q(i) = (i) G^-1(i) G^-2(i) … G^-p(i) ..; (2-2)

Где G^-2 (i) = G^-1 [G^-1 (i)] - множество вершин, из которых можно достигнуть i-й вершины, при этом длина пути = 2.

Объединение выполняется до тех пор, пока очередная операция не перестанет изменять текущее мн-во Q(i).

Мн-во R(i) Q(j) - мн-во таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от i-й вершины к j-й

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

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

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

Предполагается, что нумерация вершин в графе произведена.

Для первой вершины определяем R(1) и Q(1)

Находим сильно связанный подграф G1, включающий мн-во вершин V1 = R(1) Q(1)

Все вершины, принадлежащие G1(V1), удаляются из первоначального графа G(V)

Повторяем п 2-4 для новой вершины из оставшихся с наименьшим номером.

Процедура повторяется до тех пор, пока все вершины начального графа не будут сгруппированы в соответствующие сильно связанные подграфы

Пример3. Найдем сильно связанный подграф для вершины 1.

141

Рис. 5

Из (2-1) и (2-2) =>

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

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

Отсюда находим мн-во вершин для сильно связного подграфа, содержащего вершину 1.

V₁ = (1,2,5,6)

Аналогично

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

Q(3) = (3); => V₂ = (3);

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

Q(4) = (4,7,9); => V₃ = (4,7,9);

R(8) = (8,10);

Q(8) = (8,10); => V₄ = (8, 10)