Лекция №2 Модели систем

Любое описание системы - это модель действительности, отобра­жаю­щая те или иные ее свойства. Поэтому будем употреблять тер­ми­ны "модель" и "описание" как эквивалентные.

Выделяют три вида моделей или описаний:

1) морфологические;

2) функциональные;

3) информационные.

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

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

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

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

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.

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

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

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

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