Математическое представление структурных схем с помощью графов

Все структурные схемы имеют нечто общее, и это побудило рассматривать их как особый объект математических исследований.

Для этого пришлось абстрагироваться от содержательной стороны структурных схем. В результате получилась схема, в которой обозначается только наличие элементов и связей между ними, а также (в случае необходимости) разница между элементами и между связями.

Такая схема называется графом (рис. 9).

Следовательно, граф состоит из:

§ обозначений элементов произвольной природы, называемых вершинами;

§ обозначений связей между ними, называемых ребрами.

Часто бывает необходимо отразить несимметричность некоторых связей; в таких случаях линию, изображающую ребро, снабжают стрелкой.

Если направления не обозначаются, то граф называется неориентированным, при наличии стрелок – ориентированным (полностью или частично).

Данная пара вершин может быть соединена любым количеством ребер; вершина может быть соединена сама с собой (тогда ребро называется петлей).

Если в графе требуется отразить другие различия между элементами или связями, то либо приписывают разным ребрам различные веса (взвешенные графы), либо раскрашивают вершины или ребра (раскрашенные графы).

Для графов построена теория, имеющая многочисленные приложения.

Разнообразные задачи этой теории связаны с различными преобразованиями графов, а также с возможностью рассмотрения различных отношений на графах: весов, рангов, цветов, вероятностных характеристик (стохастические графы) и т.п.

В связи с тем, что множества вершин и ребер формально можно поменять местами, получается два представления системы в виде:

§ вершинного графа;

§ реберного графа.

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

Так, в организационных системах часто встречаются линейные, древовидные (иерархические) и матричные структуры; в технических системах чаще встречаются сетевые структуры; особое место в теории систем занимают структуры с обратными связями.

Одной из структурной информации, которая содержится в графах, для ряда исследований недостаточно.