Программирование на C, C# и Java

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 Теоретические сведения

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

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

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

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

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

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

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

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

б) кольцевая

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

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

д) типа «полный граф»

е) несвязная

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

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

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