Представление состояний систем в виде графов

Теория графов получила распространение в связи с необходимостью анализа последовательности переходов вычислительных алгоритмах. В теории графов используется язык графического обозначения направления переходов из одного состояния в другое. Использование теории графов для описания моделей систем управле­ния со сложной структурой, стало распространенным в последнее время. Графовая форма описания модели позволяет эффективно использовать новые возможности языков программирования, такие как указатели, списки, классы, множест­венное наследие. Представление в форме ориентированного (сигнального) графа, в частности структурной схемы, расширяет ин­формацию о модели, позволяя вводить причинно-следственные отношения. Знание о направленности связей имеет большое значение для задач анализа и синтеза. В качестве иллюстрации на рис. 1.1-1.4 приведены примеры ориентированных моделей графов, последний из которых представляет диаграмму модели странного аттрактора Лоренца [9]. Эта форма представления позволяет эффективнее решать задачи выделения путей и ко­нтуров, связности, структурной управляемости и многие другие.

Модель системы представляется ориентированным графом H=<G,H> с множеством переменных Х=x₁,...., x_n , где n - общее множество вершин с множеством дуг G и упорядоченных пар номеров смежных вершин G=(i,j)1,... (i,j)n. Общее количество таких пар обозначено в приме­рах как Q.

Несмотря на всю компактность и удобство такой записи на практике чаще используют матрицу смежности R=r_ij, показывающую наличие дуги между i -ой и j -ой вершинами.

 

Рис. 1.4. Модель странного аттрактора в форме ориентированного графа

 

Рис. 1.5. Модель алгоритма переходных состояний системы в форме ориентированного графа

Рис. 1.6. Модель системы в форме гиперграфа

Рис. 1.7. Модель странного аттрактора в форме гиперграфа

 

Описание сложных процессов и систем графами переходов из различных состояний Р_i показано на рис. 1.8. При этом различают несвязанные, слабосвязанные и сильно связанные системы.

 

 

 

Рис. 1.8. Схемы соединения при решении задач в теории графов

 

 

Другим способом представления топологии связей в системе является матрица смежности (наличия связей) R и изоморфности D, в строках которой представлены номера входящих (с плюсом) и выходящих (с минусом) дуг.

Для приведенного примера матрицы смежности и изоморфности имеют вид:

Избыточность хранимой информации в матрице смежности (нулевые значения) компенсируют­ся простотой вычислительных алгоритмов и скоростью получения требуемой ин­формации из матрицы. Кроме того, наличие только двух значений 0 или 1, дает возможность использовать для ее представления битовые поля, что значительно экономит память и, при размерах системы порядка 100 элементов. Если использование матрицы R в обычной десятичной форме не уступает по затратам ресурсов на хранение, то значительно упрощает алгоритм обработки информации. Использование матриц смежности и изоморфности имеет большое значение для топологи­ческого анализа алгоритмов [10].

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

Гиперграфы

Гиперграфы являются теоретико-множественной формой представления дифференциальных уравнений, заданных в общем случае не причинно—следственным способом [13]. По сравнению с графом, представление модели в форме гиперграфа расширяет возможности представления многовходовых элементов, од­нако при этом теряется информация о направленности связей.

Гиперграф определяется как пара H=<X,E> образующая конечное множество X=x₁,...,xn вершин и некоторое семейством E=e1,...,eq ребер - непустых частей Х, удовлетворяющих условию UE=X [17]. Одним из способов задания топологии гиперграфа [22], является матрица , где

Гиперграф является вариантом симплециального комплекса или симплециальной схемы [23]. В ряде работ [25-27], вводится понятие ориентированного гиперграфа. При этом множество E - определяется как множество ориентированных ребер.

Примеры гиперграфов приведены на рис. 1.6 и рис. 1.7. Из диаграмм видно, что гиперг­раф является способом группирования зависимых переменных, без указания причинно-следственных отношений между ними.

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

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: