Понятие графа структуры системы управления

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

Существуют различные типы графов, которые отличаются своими основными элементами и, следовательно, свойствами. Например, граф, в котором есть петли, т.е. ребра, соединяющие вершины сами с собой, и кратные ребра, т.е. дополнительные ребра, соединяющие смежные вершины, называется псевдографом. Граф, в котором есть кратные ребра, называется мультиграфом. Граф, не содержащий петель и кратных ребер, называется обыкновенным графом. Граф , в котором множество U состоит из упорядоченных пар вершин , где и , называется ориентированным графом, или орграфом, а сами упорядоченные пары вершин называются ориентированными ребрами, или дугами графа. Если дуга орграфа направлена из вершины x в вершину y, то говорят, вершина x смежна к вершине y, а вершина y смежна от вершины x. Таким образом, в графе смежные вершины соединены ребрами, а в орграфе — дугами.

Граф имеет следующие основные формы представления: 1) графический (в виде диаграммы), 2) матричный, 3) теоретико-мно­жест­вен­ный, 4) в виде списка. Диаграмма графа представляет собой множество точек, расположенных на плоскости и интерпретирующих вершины графа, и множество жордановых дуг[1], соединяющих эти точки и интерпретирующих ребра графа. Матричный способ представляет граф в виде специальной таблицы (матрицы). Существуют различные матрицы графа: матрица смежностей, матрица инциденций, контурная матрица и др. Теоретико-множественный способ задает граф в виде множества вершин и множества ребер. Представление графа в виде списка используется в ЭВМ, например, это может быть список пар номеров смежных вершин графа. В большинстве случаев все рассмотренные способы дают адекватное представление, т.е. представляют тот же самый граф.

Графы удобно использовать для моделирования структур СУ. Графом системы управления (ГСУ) называется граф , в котором множество вершин X интерпретирует множество элементов СУ, а множество ребер U — множество связей между ними. Важным преимуществом модели в виде ГСУ является возможность эффективного применения компьютерных технологий для автоматизации обнаружения критических структурных свойств исследуемой СУ. Класс ГСУ значительно меньше, чем класс всех графов, в частности, к ГСУ обычно не относят мультиграфы и псевдографы, содержащие кратные ребра и петли. В большинстве случаев заданы направления связей между элементами СУ, поэтому ГСУ является орграфом, в котором направление дуг совпадает с направлением связей в СУ. Иногда, чтобы показать контур самоуправления в элементе СУ, у соответствующей вершины ГСУ ставят петлю.

Элементы ГСУ моделируют важные для структурного анализа элементы СУ. К таким элементам в орграфе относят маршрут, путь, контур, полуконтур и др. Маршрут — это упорядоченное множество смежных вершин, в котором каждая предшествующая вершина смежна к последующей. Путь — это маршрут, в котором все вершины различны. Каждый путь имеет начальную и конечную вершины. Если существует путь из вершины x в вершину y, то говорят, что вершина y достижима из вершины x. Длина пути на единицу меньше числа входящих в него вершин. Контур — это замкнутый путь, в котором начальная и конечная вершины совпадают.Орграф, не содержащий контуров, называется бесконтурным.

При выделении подграфов ориентируются на типовые графы, структурные свойства которых можно рассматривать как критические. К ним можно отнести следующие типы графов: полный, пустой, связный, несвязный, бесконтурный, дерево и др. В полном подграфе любая пара вершин смежна. Пустой подграф состоит из попарно несмежных вершин. Понятие бесконтурного графа часто встречается при анализе свойств ГСУ. Например, информационный граф всегда является бесконтурным, так как наличие контура в таком ГСУ означает существование логически невозможной замкнутой последовательности вхождения документов [9]. Из теории графов известно утверждение, что в бесконтурном орграфе любой маршрут есть путь.