1.1.3. Топологический анализ структур

В рассмотренных графовых моделях и вершины (элементы струк­туры), и ребра (связи между элементами) задавались исключительно самим фактом своего существования; присущие им свойства никак не раскрывались. Поэтому граф — модель структуры, требующая для своего построения минимум информации. Однако при этом следует иметь в виду, что анализ структурных свойств системы на графе неизбежно приобретает топологический характер. Рассмотрим основные этапы топологического анализа структур.

1.1.4. Анализ элементов

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

Наличие в графе изолированных вершин обычно свидетельствует об ошибках, допущенных при формировании или описании структуры. Ведь система — всегда целостный объект, все элементы которого взаимосвя­заны.

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

Изолированные – неинциденты ни одному из ребер графа. (вершина 12 рис.1)

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

Тупиковые – вершины, из которых нельзя попасть в другие вершины (на рисунке их нет).

Рис. 1. Граф

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

где – сумма элементов k-ой строки матрицы

– сумма элементов k-го столбца матрицы

– число ребер выходящих из вершины k

– число ребер входящих в вершину k

Если вершина , то вершина k – изолирована.

Если вершина , то вершина k – висячая.

Если вершина , то вершина k – тупиковая.

Наличие изолированных – это свидетельство об ошибках при нормировании или описание структур.

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

1.1.5. Анализ связей

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

Определим основные характеристики графа.

1) Мера избыточности структуры:

Для неориентированного графа:

m – количество ребер;

n – количество вершин;

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

,

где каждому ребру (i, j) соответствуют два единичных элемента матрицы .

2) Диаметр структуры

Пусть — длина минимального пути между висячей вершиной i и тупиковой вершиной j, равная числу ребер, состав­ляющих этот путь. Тогда, если I и J — множества висячих и тупиковых вершин графа соответственно, то диаметр структуры , где i ϵ I множество висячих вершин, j ϵ J множество тупиковых вершин. Характеризует максимальное число связей, разделяющих входные и выход­ные элементы структуры. По значению d можно косвенно судить о ряде предельных параметров системы, в частности, о ее надежности, длительности задержек сообщений, идущих от висячих вершин к тупиковым, инерцион­ности. Определение значений d, сводится к стандартной задаче поиска кратчай­шего пути на графе для каждой пары (i, j) .

3) Среднеквадратическое отклонение

,

где и входные и выходные ребра i-ой вершины.

4) Общая и относительная структурная близость соответственно (вычисления по матрице минимальных цепей между элементами):

; ,

где ; .

5) Индекс центральности:

γ = ,

где ; ;

γ =1 для структур с максимальной степенью централизации (радиальная)

γ =0 для структур с равномерным распределением связей (кольцевая полный граф).