Скачать:  mod3_osnovnoe.zip [59,89 Kb] (cкачиваний: 115)

Кафедра АИТ

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

по дисциплине: «Моделирование систем»

на тему: «Структурно-топологические характеристики вычислительных систем»

Теоретическая часть

К основным структурно-топологическим характеристикам относится:

-связность структуры;

-структурная избыточность;

-компактность;

-степень централизации.

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

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

Элементы матрицы С можно вычислить на основе матрицы:

,

где A^k матрица смежности K-го порядка. Элемент C_ij=1, если ; C_ij=0, если . Для неориентированных графов связность всех элементов в структуре соответствует выполнению следующего условия:

(1)

Правая часть неравенства (1) определяет необходимое минимальное число связей в структуре неориентированного графа содержащего n вершин.

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

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

В условии (1) левую и правую часть разделим на (n-1), найдем разность и обозначим ее через R – структурная избыточность.

(2)

Найдем структурную избыточность для каждой из структур:

1.Последовательная структура:
m = n -1, Þ R = 0 – система с минимальной избыточностью.

2.Кольцевая структура:
m = n, Þ .

3.Радиальная структура:
m=n-1; Þ R = 0.

4.Структура полный граф:
Þ .

Данная характеристика используется для косвенной оценки экономичности и надежности исследуемых ВС. Для систем с максимальной избыточностью, имеющих структуру типа "полный граф" ; для систем с минимальной избыточностью ; для несвязных систем . Таким образом, система с большим R потенциально более надежна. Ее целесообразно дополнить другим параметром, учитывающим неравномерность связей .

, (3)

где - степень вершины (число ребер инцидентных вершине i).

С учетом (3) получаем:

(4)

Определим среднеквадратичное отклонение :

(5)

Определим для различных структур:

1.Последовательная структура:
m = n -1, Þ .

2.Кольцевая структура:
m = n, Þ .

3.Радиальная структура:
m=n-1; Þ .

4.Структура полный граф:
Þ.

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

- минимальная длина пути для ориентированного графа или минимальная длина цепи для неориентированного графа.

Сумма всех минимальных путей (цепей) составляет структурную компактность системы.

;

Определим для различных структур:

1.Последовательная структура:
m = n -1, Þ .

2.Кольцевая структура:
m = n, Þ .

3.Радиальная структура:
m=n-1;
Если n– четное число, тогда
Если n– нечетное число, тогда .

4.Структура полный граф:
Þ.

Для оценки структурной компактности иногда используется относительный показатель:

Степень централизации

;

; ; ;

В качестве примера рассмотрим следующую таблицу для n = 5.

Расчет структурно-топологических характеристик заданного графа

Пусть дан граф:

Для расчета примем:

n = 8;

m = 10

1) Определяем связность структуры.

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

Построим матрицу смежностей:

0,5×20 ³ 7;

10 ³7; (верно) – граф является связным;

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

R> 0, следовательно в данной системе присутствует структурная избыточность.

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

Структура имеет неравномерность связей, т.к. эта величина имеет большое значение.

4) Структурная компактность:

Находим относительный показатель:

5) Степень централизации:

Вывод

После анализа данного графа выяснили, что данная структура ближе к древовидной.