Топологическая декомпозиция структур
Проведение топологической декомпозиции структуры БСУ на основе представления её в виде ориентированного графа G(V) связано с выделением в ней отдельных сильно связанных подсистем.
Мн-во вершин, достижимых из вершины i, называется достижимым мн-вом R(i)
R(i) = i G(i) G2(i) … Gp(i) …; (2-1)
G(i) - мн-во вершин, достижимых из вершины i с использованием путей длиной =1
Gp(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.
V1 = (1,2,5,6)
Аналогично
R(3) = (3,4,7,9);
Q(3) = (3); => V2 = (3);
R(4) = (4,7,9);
Q(4) = (4,7,9); => V3 = (4,7,9);
R(8) = (8,10);
Q(8) = (8,10); => V4 = (8, 10)
