Ранжирование элементов систем Варианты заданий

Определить ранги элементов системы, заданной графом G = (V,U)

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

12)

13)

14)

15)

16)

17)

18)

19)

20)

Структурный анализ систем

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

Структурный анализ позволяет:

1) представить удобное символическое изображение системы в виде струк­турной схемы;

2) определить значимость элементов системы и связей между ними;

3) оценить качество структуры системы и сформулировать рекоменда­ции по ее улучшению.

Важной частью исследования является определение значимости эле­мен­тов системы на основании наличия между ними определенной со­во­­куп­ности от­но­шений. Для этого вводится количественный показатель зна­чимости - ранг элемента, который является относительной характе­рис­тикой, так как зависит от выбора критерия ранжировки. Определе­ние ранга эле­мен­тов позволяет облечь качественное субъективное пони­ма­ние значимости в коли­чест­венную форму.

Ранги элементов и другие структурные параметры позволяют оце­нить вклад, вносимый в общий функциональный показатель системы от­дель­ными элементами и связями, степень функциональной загрузки элемен­тов и связей, наличие "узких" мест в связях между объек­тами. Это, в свою оче­редь, позво­ляет разработать рациональную программу тех­ни­чес­кой реа­ли­зации системы с учетом значимости ее элементов, что дает оп­ре­деленную эко­номию сил и средств, поскольку выявленные проб­ле­мы решаются до начала не только про­из­водственного процесса, но и де­таль­но­го исследо­ва­ния системы.

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

Элементы теории графов

Def. Множество и набор U пар элементов из V называется графом G = (V,U).

Элементы множества Vназываютсявершинамиграфа. Элементы на­бораUназываютсяребрамиграфа. Про реброговорят, что оно соединяет вершины. Ребра виданазываютсяпетлями.

Вершины, соединенные ребром, назы­ваютсясмежными.Ребра, име­ю­щие общую вершину, называютсясмежными.

В наборе Uмогут встречаться одинаковые пары, ко­торые назы­вают­сякратными(илипараллельными) ребрами. Коли­чест­во одина­ко­вых парвUназы­ваетсякратностью ребра.

В литературе граф с кратными ребрами и петлями обычно назы­вают псев­до­графом. Псевдограф без петель (но с кратными ребрами) называютмульти­графом. Собственногра­фом, как правило,называютпсевдограф без петель и кратных ребер. Такого определения мы и бу­дем придерживаться.

Если пары в наборе Uявляются упорядоченными, то граф назы­ва­ет­сяориентирован­нымили краткоорграфом. Ребра орграфа часто на­зы­ваютдугами. В дальней­шем мы огра­ничимся рассмотрением только орграфов, со­хра­нив при этом терминологию, используемую для графов. Так часто делают в специальной литературе, если это не вызывает пу­таницы.

Если - ребро графа, то вершинаназывается нача­лом ребраx , а вершина- концом ребраx. В этом случае говорят, что реброx соеди­няет вершины. Если вершинаaявляется началом или концом ребраx, то говорят, чтоaиx инцидентны.

Два ребра называются смежными, если имеют общую вершину. Две вершиныназываютсясмежными, если.

Степенью вершиныaназывается числоребер, инцидент­ных вершинеa. Вершина графа, имеющая степень 0, называетсяизолиро­ван­ной, а степень 1 –висячей.

Если множество Vи наборUсостоят из конечного числа элементов и пар, то графGназываетсяконечным. Граф, у которого любые две вершины соединены ребром, назы­вает­сяполным.

Система ребер называетсяпу­тем, соединяющим вершины, если конец каждого ребра (за ис­ключением последнего) совпадает с началом следующего. Для любого ребра, принадлежа­ще­го пути, го­ворят, что путьпро­хо­дит через это ребро. Аналогично, если вершинапринад­ле­жит неко­то­рому ребру пути, то говорят, что этот путь проходит через вер­шину.

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

Граф Gназываетсясвязным, если для его любых двух различных вер­шинсуществует путь, соединяющий эти вершины.

Весьма наглядной является геометрическая реализация графаGв виде фигурыГ, вершины которой соответствуют вершинам графаG, а ребрам графаG- отрезки прямых или дуги, соединяющие со­от­ветст­вую­щие вершины.

Справедлива следующая теорема.

Теорема.Каждый конечный граф G можно реализовать в трех­мер­ном евклидовом пространстве.

Для характеристики графа Gиспользуются следующие числовые ха­ракте­ристики:

1) число вершин графа (элементов) n;

2) число ребер графа (связей) m;

3) число его связных частей (компонент) p;

4) цикломатическое число v(G) = m - n + p;

5) хроматическое число графа v(G).

Смысл первых трех характеристик ясен без комментариев.

Цикло­ма­тическое числоv(G)равно максимальному числу неза­ви­си­мых циклов.

Подробнее поясним смысл хроматического числа. Если все вер­ши­ны графа окрашены k цветами так, что никакие две смежные вершины не окрашены одним цветом, то граф называется хромати­чес­ким по­ряд­ка k. Минимальное числоk, при котором граф является хрома­ти­чес­ким по­рядкаk, называетсяхроматическим числом графаG и обозначаетсяv(G), т.е.v(G) = min k.

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

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

Граф - это топологическая модель, отображающая некоторую сово­куп­ность связей между элементами системы.

Связь - это некоторое отношение между двумя элементами, т.е., исполь­зуя графы, мы имеем дело с бинарными отношениями.