Аппроксимация графа произвольной структуры розой

 

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

Рассмотрим эту задачу при следующих ограничениях:

– Анализируются орграфы с конечным числом вершин;

– Из всех вершин выбирают одну и рассматривают ее как центр розы;

– Рассматриваются только простые импульсные процессы, начинающиеся в выделенной вершине.

Будем считать, что роза R с центром в вершине U является аппроксимацией орграфа G(X,E) с выделенной вершиной A, если последовательности {P_A(t)} и {v_A(t)}, порожденные простым импульсным процессом на орграфе G(X,E), начинающимся в вершине A, совпадают с последовательностями {P_U(t)} и {v_U(t)}, соответствующими простому импульсному процессу в розе R.

На практике преобразовать произвольный орграф в розу можно, пользуясь следующим алгоритмом:

1. Выделить вершину A в заданном орграфе.

2. Найти все пути из A в A.

3. Найденные пути могут пересекаться. Выделить подмножество вершин пересечения и для каждой вершины из этого подмножества ввести фиктивные (но различные) вершины. Причем каждой из вершин пересечения соответствует такое число фиктивных вершин, которое на 1 меньше числа появлений данной вершины в найденных путях из A в A.

4. Выделенная вершина A по определению не включается в подмножество вершин пересечения.

5. Заменить на всех путях избыточные вершины фиктивными. Объединив все пути получить розу с центром в вершине A.

Преобразование орграфа, осуществленное по этому правилу, называют R– преобразованием.

Утверждение 4: Для того чтобы R – преобразование орграфа G(X,E), , с центром в выделенной вершине A имело конечное число лепестков, необходимо и достаточно, чтобы в орграфе G(X,E) не существовало ни одного локального цикла, не включающего A, достижимого из A и такого, что А достижима из него.

Утверждение 5: R – преобразование орграфа G с центром в точке A с конечным числом лепестков является аппроксимацией орграфа G.

Пример: B

A’’

G E

E

A F

I C F

F’ A

B C D A’

 

Рис.1

 

На рисунке показано R–преобразование графа произвольной структуры в трехлепестковую розу с центральной вершиной C.