Лабораторная работа №1. www. nlr. ru – Российская национальная библиотека (РНБ)

Интернет-ресурсы

www. nlr. ru – Российская национальная библиотека (РНБ)

www. rsl. ru – Российская государственная библиотека (РГБ)

www. inion/ ru – Институт научной информации по общественным наукам РАН (ИНИОН)

www.auditorium. ru – Образовательный портал «Социально-гуманитарное и политическое образование»

www. economics. edu.ru – Образовательный портал «Экономика, социология, менеджмент»

www. economics.ru – Экономический портал

www.biblus.ru- - Каталог книг «Библус» по всем отраслям науки

www.forexpf.ru- Библиотека по техническому и фундаментальному экономическому анализу

www.libertarium.ru- Библиотека «Либертариум»

www.gks.ru – Госкомстат России (в разделе «Банк готовых документов» электронные версии официальных публикаций в свободном доступе)

www.minfin.ru – Министерство финансов России

http//stat.hse.ru- Статистический портал Высшей школы экономики

www.economy.gov.ru – Министерство экономического развития и торговли

www.cefir.ru – «Центр экономических и финансовых исследований и разработок» (результаты исследований, аналитические отчеты, статьи)

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

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

Определение графа. Пусть задано множество элементов 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 при наличии связи между вершинами i,j

- при отсутствии связи.

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

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

-

если из i можно перейти в j

- в противном случае

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

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

n - число вершин, m - число ребер

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

- если i-я вершина инцидентна j-му ребру

- если нет связи

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

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

-

если i-я вершина есть начало j-го ребра,

- если i- я вершина есть конец j-го ребра,

- если связи нет.

Для графа рис.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)

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

Цепью называется последовательность ребер E1,E2…En, когда каждое из ребер Еi соприкасается одним из концов с ребром Ei+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. Структурная схема системы.

а) 1 2 3 4 5

б) 1 2

5 4

в) 2

4 1 3

г) 1

2 3

4 5

д) 1

2 5

3 4

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

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

1 4

Рис.5.

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

1 3

Рис.6.

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

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

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

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

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

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

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

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

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

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

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

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

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

m=5 - число ребер

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

p1=3; p2=2; p3=3; р4=2;

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

m=5

n=4

p1=p2=p3=p4=2

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

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

Для графа рис.5:d12=d13=d14=1;

d21=d23=1; d24=2

d31=d32=d34=1;

d41=d43=1; d42=2

Тогда:

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

d12=d14=1; d13=2

d21=d23=1; d24=2

d32=d34=1; d31=2

d41=d43=1; d42=2

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

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

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

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

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

1 2 4

Рис.7.

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

1 3

Рис.8.

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

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

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

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

1 2 3и4

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

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

Дата добавления: 2014-11-29