Структурно-топологические характеристики систем

Структурные характеристики системы позволяют уже на ранней стадии создания системы оценить качество ее структуры и элементов с позиции общего системного подхода. Рассмотрим основные характеристики и приведем реализацию описанных алгоритмов анализа систем на языке программирования C#.

1 Связность структуры

1.1 Теоретические сведения

Эта характеристика позволяет выявить наличие обрывов в структуре, висячие вершины и т.п.

Связность элементов графа определяется матрицей связности С = ||cij||, элементы которой определяются на основе суммарной матрицы смежности:

Формула матрицы связности - vscode.ru

где n – число вершин графа, Ak = Ak-1A (в частности A2 = A•A), где A – матрица смежности графа.

Элемент матрицы Ak = ||akij|| определяет число путей длиной k от вершины i к вершине j.

Элемент матрицы связности:

Элемент матрицы связности - vscode.ru

1.2 Программная реализация

Аргументы метода connectionStructure( ): n – число вершин в графе, A – матрица смежности, C – ссылка на экземпляр класса Array, в который будет занесена матрица связности.

2 Структурная избыточность

2.1 Теоретические сведения

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

Структурная избыточность - vscode.ru

Для систем с избыточностью, имеющих кольцевую структуру или структуру типа «полный граф», R > 0, для систем без избыточности R = 0, для систем несвязных R < 0.

Обычно системы с большим R потенциально более надежны.

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

Недоиспользование возможностей структуры в достижении максимальной связности - vscode.ru

где n – количество вершин, gi – степень i-ой вершины, m – количество ребер у графа.

Этот показатель характеризует недоиспользование возможностей структуры в достижении максимальной связности.

2.2 Программная реализация

Аргументы метода structuralRedundancy( ): n – число вершин в графе, countE – количество ребер в графе, A – матрица смежности, R – структурная избыточность, e2 – неравномерность распределения связей. R и e2 – выходные параметры.

3 Структурная компактность

3.1 Теоретические сведения

Близость элементов i, j между собой определяется через минимальную длину цепи (пути) dij. Структурная компактность определяется несколькими параметрами.

Абсолютная компактность:

Абсолютная компактность, формула - vscode.ru

Относительная компактность:

Относительная компактность, формула - vscode.ru

где Qmin = n(n-1) – это минимальное значение компактности для структуры системы типа «полный граф»;

Диаметр структуры:

Диаметр структуры, формула - vscode.ru

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

3.2 Программная реализация

Аргументы метода structuralCompactness( ): n – число вершин в графе, E – список ребер графа, Q – абсолютная компактность, Qotn – относительная компактность, d – диаметр структуры. Q, Qotn и d – выходные параметры.

Ребро графа графа определяется экземпляром класс Edge:

где v1 и v2 – номера вершин, которые соединяет данное ребро.

Для поиска длин цепей (заносятся в List<int> chainsLenght) в графе используется модификация рекурсивного алгоритма «Поиск в глубину» (Depth-first search). Опишем принцип ее работы:

Пусть дан граф G = (V, E), где V – множество вершин графа, E – множество его ребер. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

  1. Перебираем все пары вершин, возможно, они являются началом и концом цепи. На каждой итерации перекрашиваем все вершины в белый цвет (обозначим его 1, а черный цвет будем обозначать 2). Вызываем для каждой пары вершин процедуру DFSchain.

Процедура DFSchain(int u, int endV, List<Edge> E, int[] color, int len) (параметры: u – номер начальной вершины цепи, endV – номер конечной вершины цепи, E – список ребер графа, color – массив, в котором хранятся цвета вершин, len – текущая длина цепи):

  1. Если номер вершины u не равен endV, значит мы не достигли конца цепи, поэтому перекрашиваем вершину u в черный цвет. Иначе – конец цепи достигнут: добавляем длину цепи (len) в список и выполняем возврат из функции.
  2. Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, рекурсивно выполняем процедуру DFSchain(w, endV, E, color, len + 1). Возвращаем вершине w белый цвет (возможно через нее проходят другие цепи, поэтому не будем исключать ее из рассмотрения).

Приведем реализацию метода DFSchain( ):

4 Степень централизации в структуре

4.1 Теоретические сведения

Для оценки централизации используют индекс центральности:

Индекс центральности - vscode.ru

где Zmax – максимальное значение величины:

strTopCharS9

Для структур систем, имеющих максимальную степень централизации σ = 1 (радиальная), для структур с равномерным распределением связей (полный граф, кольцевая) σ = 0.

4.2 Программная реализация

Аргументы метода degreeOfCentralization( ): n – число вершин в графе, Q – значение абсолютной компактности, E – список ребер графа. Метод возвращает значение индекса централизации (sigma). Для поиска значений длины цепей между вершинами используется метод DFSchain( ), описанный выше.

5 Основные виды структур

Введенные количественные характеристики могут быть использованы при сравнительной оценки топологических свойств структур систем. С точки зрения топологии внутренних связей выделяют следующие основные виды структур:

а) последовательная

б) кольцевая

в) радиальная

г) древовидная

д) типа “полный граф”

е) несвязная

Структурно-топологические характеристики систем - vscode.ru

Количественные значения структурно-топологических характеристик этих структур приведены в таблице ниже.

Структурно-топологические характеристики систем - vscode.ru

Видно, что структуры с нулевой избыточностью R = 0 всё же различаются по параметру ε2. Наибольшую неравномерность связей имеет радиальная структура. Наибольшую компактность имеет структура типа «полный граф». Наименьшую близость элементов – последовательная структура. Структуры неразличимые по показателю d: кольцевая и радиальная – имеют различные значения параметра Q, т.е. кольцевая структура всё же более компактна, чем радиальная. Отметим также, что чем больше централизация, тем выше неравномерность связей (параметр ε2).

Скачать листинги

 

 

Структурно-топологические характеристики систем
5 (100%) 1 vote

Поделиться в соц. сетях:

Один комментарий к статье “Структурно-топологические характеристики систем

  1. Programmer_blog

    Никогда не видел понятие матрицы связности, но насколько я понимаю [latex]A^k[/latex] – это матрица достижимости. Если в клетке такой матрицы содержится единица, значит между элементами графа, соответствующими строке и столбцу существует путь длины не более k (в невзвешенном графе, по крайней мере).

    Вы определяете матрицу связности как сумму матриц достижимости для всех k от 1 до n. Я не совсем понимаю что даст такая сумма. [latex]A^k[/latex] содержит информацию обо всех возможных путях в матрице – такая матрица позволит выявить компоненты связности и, в частности, изолированные вершины. А что в этом случае дает сумма?

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">