Лабораторная работа №4

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

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

Определение графа. Пусть задано множество элементов V. Граф G(V) считается определённым, если задано семейство сочетаний элементов или пар вида E=(a,b), где a,b є V, указывающее какие элементы считаются связанными. Пара E = (a,b) называется ребром, а элементы a,b - вершинами. Если порядок расположения концов безразличен, то (a,b) - неориентированное ребро, если этот порядок важен, то (a,b) - ориентированное ребро или дуга. Соответственно графы, состоящие из ребер, называют неориентированными (рис.1), а из дуг (рис.2) - ориентированными.

Рис.1 Рис.2

Способы формализованного задания графа.

Существует три способа задания графа.

1.Графический. Наиболее наглядный способ, однако он не может быть использован при решении задачи на ЭВМ.

2.Матричный. Матрица смежности для неориентированного графа имеет вид:

, где

Для графа рис.1:

Для ориентированногографа элементы a_i,j определяются так:

Для графа рис.2:

Если пронумеровать ребра графа, то его можно задать матрицей инцидентности:

; ; ,

где n – число вершин графа, m – число ребер графа.

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

Например, матирца инцидентности для графа (рис.1) имеет вид:

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

Например, матирца инцидентности для графа (рис.1) имеет вид:

Для графа (рис.2)

.

3.Множественный. Для графа G(V) задается множество вершин V и соответствие G, которое показывает как они между собой связаны. Соответствие G(i) показывает множество вершин, в которые можно попасть из i. Для графа рис.2: G(1)=(2,4); G(2)=(5); G(3)=(1); G(4)=(3); G(5)=(4).

Можно задать соответствие G^-1(j) определяющее множество вершин, из которых можно попасть в i.

Для графа рис.2:

G^-1(1)=(3);G^-1(2)=(1);G^-1(3)=(4);G^-1(4)=(1,5);G^-1(5)=(2).

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

Цепью называется последовательность ребер E₁,E₂…E_n, когда каждое из ребер Е_i соприкасается одним из концов с ребром E_i+1. Цепь можно обозначить последовательностью вершин, которые она содержит.

Путем называется последовательность дуг, когда конец предыдущей дуги совпадает с началом последующей.

Длиной цепи (пути) называют число ребер (дуг), входящих в цепь (путь).

Матрица смежности вершин А является матрицей матрицы А: А^k = A^k-1 * A

Элемент матрицы A^k a^(k)_i,j определяет число путей длинной k от вершины i к j, непосредственных путей графа, имеющих длину, равную единице. Общее число транзитных путей от вершины i к вершине j длиной K получается возведением в K -ю степень.

Число ребер, инцидентных вершине неориентированного графа, называют степенью вершины P(i).

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

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

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

Для ориентированного графа связность элементов определяется матрицей связности С, где

если (1)

если

Для неориентированного графа связность всех элементов соответствует выполнению условия:

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

Для системы с минимальной избыточностью R=0; для несвязных систем R может быть отрицательным.

3. Равномерность распределения связей в структуре неориентированного графа, имеющего m ребер и n вершин характерезуется показателем:

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

4. Структурная компактность - это параметр, отражающий близость элементов между собой:

d_i,j - минимальная длина цепи между вершинами i и j.

Часто структурная компактность характеризуется относительным показателем:

5. Степень централизации в структуре характеризуется индексом центральности:

Индекс центральности меняется в диапазоне от 0 до 1.

6. Ранг элемента позволяет распределить элементы системы в порядке их значимости. Значимость элемента определяется числом его связей с другими элементами. Ранг элемента используется при представлении структуры системы в виде ориентированного графа и может быть вычислен по формуле:

Пример №1. Система задана следующей структурной схемой (рис.3). Рассчитать ее структурно - топологические характеристики и сравнить их с характеристиками типа “кольцевая” (рис.4).

Рис.3. Структурная схема системы

а)

б)

в)

г)

д)

Рис.4. Типовые виды структур для n=5: а)последовательная; б)кольцевая; в)радиальная; г)древовидная; д)полный граф.

Вначале исходную структурную схему рис.3 представим в виде неориентированного графа (рис.5)

Рис.5.Типовая кольцевая структура для n=4 соответствует графу рис.6

Рис.6.

Вычислим структурно-топологические характеристики графов Рис.5 и Рис.6 и сравним их между собой.

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

Для графа рис.5 составим матрицу смежности

Проверим условие (2):

‑ условие связности выполняется.

Аналогично для графа рис.6:

‑ условие связности выполняется.

Структурная избыточность (рассчитывается по (3)).

Для графа рис.5.

Для кольцевой структуры:

Вывод: структура рис.5 обладает в два раза большей избыточностью по сравнению с кольцевой.

Равномерность распределения связей. (рассчитывается по (4)).

Для графа рис.5

m=5 ‑ число ребер;

n=4 ‑ число вершин.

,

где p₁=3; p₂=2; p₃=3; р₄=2;

Для графа рис.6:

m=5;

n=4.

,

где p₁=p₂=p₃=p₄=2

Вывод: В графе рис.6 связи распределяются более равномерно.

Структурная компактность. Оценим ее оптимальным показателем по(6).

Для графа рис.5:

d₁₂=d₁₃=d₁₄=1;

d₂₁=d₂₃=1; d₂₄=2

d₃₁=d₃₂=d₃₄=1;

d₄₁=d₄₃=1; d₄₂=2

Тогда:

Аналогично, для графа рис.6:

d₁₂=d₁₄=1; d₁₃=2

d₂₁=d₂₃=1; d₂₄=2

d₃₂=d₃₄=1; d₃₁=2

d₄₁=d₄₃=1; d₄₂=2

Степень централизации в структуре оценим по индексу центральности δ (7).

Для графа рис.5:

Для графа рис.6:

Вывод: Структура рис.5 имеет малую степень централизации, структура рис.6 абсолютно децентрализована.

Пример 2. Дана структурная схема системы (рис.7.). Ранжировать ее элементы в порядке их с труктурной значимости.

Рис.7.

Представим систему рис.7 в виде ориентированного графа (рис.8).

Рис.8.

Матрица смежности графа рис.8 имеет вид:

Для расчета рангов элементов системы вычислим матрицу A^{4 :}

Вычислим ранги элементов системы рис.7 по формуле (8):

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

И 4

Задание 1. Рассчитать структурно-топологические характеристики данной преподавателем системы и сравнить их с характеристиками одной из таковых структур.

Задание 2. Ранжировать элементы данной преподавателем системы в порядке их структурной значимости.

Дата добавления: 2015-07-14