Лекция 4-5. Методы представления систем.

Классификации методов формализованного представления систем. В большинстве первоначально применявшихся при исследовании систем классификаций выделяли детерминированные и вероятностные (статистические) методы или классы моделей, которые сформировались в конце прошлого столетия. Затем появились классификации, в которых в самостоятельные классы выделились теоретико-множественные представленыя, графы, математическая логика и некоторые новые разделы математики.

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

Рассмотрим классификацию, в которой выделяются следующие обобщенные группы (классы) методов (табл. 1):

• аналитические, к которым в рассматриваемой классификации отнесены методы классической математики, включая интегро-дифференциальное исчисление, методы поиска экстремумов функций, вариационное исчисление и т. п; методы математического программирования; первые работы по теории игр и т. п.;

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

• теоретико-множественные, логические, лингвистические, семиотические представления (методы дискретной математики), составляющие теоретическую основу разработки языков моделирования, автоматизации проектирования, информационно-поисковых языков;

• графические , включающие теорию графов и разного рода графические представления информации типа диаграмм, гистограмм и других графиков.

Разумеется, в табл. 1 приведены лишь укрупненные группы-направления, конкретные методы которых только в начальный период развития характеризуются рассмотренными особенностями. Эти направления непрерывно развиваются, и в их рамках появляются методы с расширенными возможностями по сравнению с исходными.

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

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

Название	Символический образ	Основная терминология и примеры теорий, возникших и развивающихся на базе соответствующего класса методов	Сферы и возможности применения
Аналитический		Аналитическими здесь названы методы, которые ряд свойств многомерной, многосвязной системы отображают в n-мерном пространстве в виде одной единственной точки (безразмерной в строгих математических доказательствах), совершающей какие-либо перемещения в пространстве (или обладающую каким-то поведением). Это отображение осуществляется посредством оператора (функции, функционала) Ф[Sx]. Можно также две (или более) системы или их части отобразить точками и рассматривать взаимодействие этих точек. Поведение точек, их взаимодействие описываются строгими соотношениями, имеющими силу закона. Основу понятийного (терминологического) аппарата этих представлений составляют понятия классической математики (величина, формула, функция, уравнение, система уравнений, логарифм, дифференциал, интеграл и т. д.). На базе аналитических представлений возникли и развиваются математические теории различной сложности от аппарата классического математического анализа (методов исследования функций, их вида, способов представления, поиска экстремумов функций и т.п.) до таких новых разделов современной математики, как математическое программирование (линейное, нелинейное, динамическое ч т. п.), теория игр (матричные игры с чистыми стратегиями, дифференциальные игры и т, п.)	Применяются в тех случаях, когда свойства системы можно отобразить с помощью детерминированных величин или зависимостей, т. е. когда знания о процессах и событиях в некотором интервале времени позволяют полностью определить поведение их вне этого интервала. Эти методы используются при решении задач движения и устойчивости, оптимального размещения, распределения работ и ресурсов, выбора наилучшего пути, оптимальной стратегии поведения, в том числе в конфликтных ситуациях ит.п. Математические теории, развивающиеся на базе аналитических представлений, направления стали основой многих прикладных теорий, в том числе теории автоматического управления, теории оптимальных решений и т. д. При практическом применении аналогических представлений для отображения сложных систем следует иметь в виду, что они требуют установления всех детерминированных связей между учитываемыми компонентами и целями системы в виде аналитических зависимостей. Для сложных многокомпонентных, многокритериальных систем получить требуемые аналитические зависимости крайне трудно. Более того, даже если это и удается, то практически невозможно доказать правомерность применения таких выражений, т. е. адекватность модели рассматриваемой задаче
Статический		Статистическим называют отображение системы с помощью случайных (стохастических событий, процессов, которые описываются вероятностными характеристиками и статистическими закономерностями. Статистические отображения системы можно представить как бы в виде «размытой» точки (размытой области) в n-мерном пространстве, в которую переводит систему (ее учитываемые в модели свойства) оператор Ф[Sx], «Размытую» точку следует понимать как некоторую область, характеризующую движение системы (ее поведение); при этом границы области заданы с некоторой вероятностью р (под вероятностью события понимается р(А)=^:т/п, где т - число появлений события A, n - общее число опытов), т. е, как бы размыты, и движение точки описывается некоторой случайной функцией Закрепляя все параметры этой области, кроме одного, можно получить срез по линии а- b смысл которого - воздействие данного параметра на поведение системы, что можно описать статистическим распределением по этому параметру, Аналогично можно получить двумерную, трехмерную и т.д. картины статистического распределения.	На базе статистических представлений возникли и развиваются прикладные направления: статистическая радиотехника, статистическая теория распознавания образов, экономическая статистика, теория массового обслуживания а также развившиеся из направлений, возникших на базе аналитических представлений, стохастическое программирование новые разделы теории игр и т. п. Расширение возможностей отображения сложных систем и процессов по сравнению с аналитическими методами можно объяснить тем, что при применении статистических представлений процесс постановки задачи как бы частично заменяется статистическими исследованиями, позволяющими, не выявляя все детерминированные связи между изучаемыми объектами (событиями) или учитываемыми компонентами сложной системы, на основе выборочного исследования (исследования репрезентативной выборки получать статистические закономерности и распространять их на поведение системы в целом с какой-то вероятностью). Однако не всегда можно получить статистические закономерности, не всегда может быть определена репрезентативная выборка; доказана правомерность применения статистических закономерностей. Если же не удается доказать репрезентативность выборки или для этого требуется недопустимо большое время, то применение статистических методов может привести к неверным результатам. В таких случаях целесообразно обратиться к методам, объединяемым под общим названием методы дискретной математики, которые помогают разрабатывать языки моделирования, модели и методики постепенной формализации процесса принятия решения. Статистические и теоретико-множественные методы инициировали возникновение теории нечетких или размытых множеств Л. Заде, которая явилась началом развития нового направления - нечетких формализации
		На базе статистических представлений развивается ряд математических теорий: математическая статистика; теория статистических испытаний, а развитием - теория статистического имитационного моделирования, теория выдвижения и проверки статистических гипотез, базирующаяся на общей теории статистических решающих функций (частным случаем этой теории, важным для теории систем, является байесовский подход к исследованию передачи информации в процессах общения , обучения и др. ситуациях); теория потенциальной помехоустойчивости и теории решающих функций', обобщение последних двух направлений -теория статистических решений
Теоретико-множественные		Теоретико-множественное представления базируются на понятиях множество, элементы множества, отношения на множествах, континуум. Множества могут задаваться следующими способами: 1) перечислением (интенсионально): {a} , где j = 1...и или <a1, a2,... , ai, ... ,аn>, где аi€A 2) путем указания некоторого характеристического свойства А (экстенсионально). В основе теоретико-множественных преобразований лежит переход от одного способа задания множества к другому: В множестве могут быть выделены подмножества. Из двух или нескольких множеств можно сформировать путем установления отношений между элементами этих множеств новое множество, обладающее принципиально новыми свойствами и, как прави­ло, новое качество приобретают и элементы. Теоретико-множественные представления допускают введение любых произвольных отношений. При конкретизации отношений и правил их использования можно получить одну из алгебр логики, один из формальных языков математической лингвистики, создать язык моделирования сложной системы, который затем, получив соответствующее название может развиваться как самостоятельное научное направление. Между теоретико-множественными описаниями разных систем или их частей можно устанавливать соответствия: гомоморфизма, изоморфизма, автоморфизма отношения рефлексивности, симметричности, транзитивности, заимствованные теорией множеств из других разделов математики	Благодаря возможности введения любых отношений теоретико-множественные представления используются как обобшаюший язык при сопоставлении различных направлений математики и других дисциплин, явились основой для возникновения новых научных направлений или развития существующих, Система может быть представлена совокупностью множеств или подмножеств разнородных компонентов с произвольно вводи­мыми элементами и отношениями. Однако свобода введения произвольных отношений приводит к тому, что в формализованном с их помощью описании проблемной ситуации довольно быстро могут обнаружиться неразрешимые противоречия - парадоксы, апории или антиномии, что не позволяет оперировать с получаемыми теоретико-множественными моделями таким же образом, как с классическими математическими (аналитическими, статистическими) соотношениями, гарантируя достоверность получаемых результатов
Логический		Логические представления переводят реальную систему и отношения в ней на язык одной из алгебр логики (двузначной, многозначной), основанной на применении алгебраических методов для выражений законов алгебры логики. Наибольшее распространение получила бинарная алгебра логики Буля (булева алгебра). Базовыми понятиями алгебры логики являются: высказывание, предикат, логические функции (операции) кванторы, логический базис, логические законы или теоремы (законы алгебры логики), применяя которые можно преобразовать систему из одного описания в другие с целью ее совершенствования. Например, получить более простую структуру (схему), содержащую меньшее число состояний, элементов, но осуществляющую требуемые функции. Теоремы доказываются и используются в рамках формального логического базиса, определяемого совокупностью специальных правил. Логические методы представления систем относятся к детерминистским, хотя возможно их расширение в сторону вероятностных оценок. На базе математической логики созданы и развиваются теории логического анализа и логического синтеза, теория автоматов. На основе логических представлений первоначально начинали развиваться некоторые разделы теории формальных языков. В силу ограниченности смысловыражающих возможностей бинарной алгебры в последнее время имеются попытки создания многозначных алгебр логики с соответствующими логическими базисами и теоремами	Применяются при исследовании новых структур и систем разнообразной природы (технических объекта, текстов и др.), в которых характер взаимоотношений между элементами еще не настолько ясен, чтобы было возможно их представление аналитическими методами, а статистические исследования либо затруднены, либо не привели к выявлению устойчивых статистических закономерностей, В то же время следует иметь в виду, что с помощью логических алгоритмов можно описывать не любые отношения, а только те, которые предусмотрены законами алгебры логики и удовлетворяют требованиям логического базиса. Логические представления широко применяются при исследовании и разработке автоматов разного рода, автоматических систем контроля, при решении задач распознавания образов. На их основе развивается самостоятельный раздел теории формальных языков - языки моделирования проблемных ситуаций и текстов. В то же время смысловыражающие возможности логических методов ограничены базисом и не всегда позволяют адекватно отобразить реальную проблемную ситуацию.
Лингвистические		Основными понятиями, на которых базируются лингвистические представления, являются понятия: тезаурус Т, грамматика G, семантика, прагматика. Термин тезаурус (от греч. сокровищница, богатство, клад, запас и т. п.) в общем случае «совокупность научных знаний о явлениях и законах внешнего мира и духовной деятельности людей, накопленную всем человеческим обществом». В математической лингвистике и семиотике термин тезаурус используется в более узком смысле для характеристики конкретного языка, его многоуровневой структуры. Для этих целей удобно пользоваться одним из принятых в лингвистике определений тезауруса как «множества смысловыражающих элементов языка с заданными смысловыми отношениями, которое дал Ю.А. Шрейдер. Для системных приложений интересно сочетание математической лингвистики и семиотики, которая возникла как наука о знаках. Однако некоторые школы, развивающие семиотические представления, равноправно пользуются в семиотике понятиями математической лингвистики, такими как тезаурус, грамматика, семантика и т. п. Такие представления иногда называют лингвистической семиотикой или лингвосемиотикой.	Для практических приложении модели лингвистических и семиотических представлений можно рассматривать как один класс методов формализованного представления систем Лингвистические и семиотические представления возникли и развиваются в связи с потребностями анализа текстов и языков. Однако во второй половине XX в. эти представления стали широко применяться для отображения и анализа процессов в сложных системах в тех случаях, когда не удается применить сразу аналитические, статистические представления или методы формальной логики, В частности, лингвистические и семиотические представления являются удобным аппаратом (особенно в сочетании с графическими) для первого этапа постановки и формализации задач принятия решений в ситуациях с большой начальной неопределенностью, чем и был вызван интерес к этим методам со стороны инженеров и специалистов, занимающихся исследованием и разработкой сложных систем. На их основе разрабатывают языки моделирования и автоматизации проектирования.
		С теоретической точки зрения границу между лингвистическими и семиотическими представлениями при разработке языков моделирования можно определить характером правил грамматики: если правила не охватывается классификаций формальных грамматик Н. Хомсного, то модель относят к семиотической и применяют произвольные правила взаимоотношений между знаками, отображающими компоненты модели, допустимые семиотикой	При применении этих методов следует иметь в виду, что при усложнении языка моделирования, при применении правил произвольной грамматики или семиотики трудно гарантировать достоверность получаемых результатов, возникают проблемы алгоритмической разрешимости, парадоксов, которые частично могут быть преодолены с помощью содержательного контроля и корректировки языка на каждом шаге его расширения в диалоговом режиме моделирования
Графические		К графическим представлениям здесь отнесены любые графики (диаграммы, гистограммы, графики Гонта, т.е. «время-операция» в прямоугольных координатах и т д.) и возникшие на основе графических отображений теории: теорию графов, теорию сетевого планирования и управления и т, п., т. е. все, что позволяет наглядно представить процессы, происходящие в системах, и облегчить таким образом их анализ для человека (лица, принимающего решения). Есть и возникшие на основе графических представлений методы, которые позволяют ставить и решать вопросы оптимизации процессов организации, управления, проектирования и являются математическими методами в традиционном смысле. Таковы геометрия, теория графов. Понятие графа в математическом смысле первоначально было введено Л.Эйлером	Графические представления являются удобным средством исследования структур и процессов в сложных системах, средством организации взаимодействие человека и технических устройств (в том числе ЭВМ),

Для дискретных событий соотношение между возможными значениями случайной величины х, и их вероятностями р, называют законом распределения и либо записывают в виде ряда (таблице), либо представляют в виде зависимостей F(x)

При этом

Рис. 2. Представление законов распределения

Для непрерывных случайных величин (процессов) закон распределения представляют (соответственно дискретным законам) либо в виде функции распределения (интегральный закон распределения - рис. 2, б), либо в виде плотности вероятностей (дифференциальный закон распределения - рис. 2, г). В этом случае где р(х) -вероятность попадания случайных событий в интервал от x до .

Для полной группы несовместных событий имеют место условия нормирования:

функции распределения

и плотности вероятности

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

Наибольшее применение получили:

1-й начальный момент - математическое ожидание или среднее значение случайной величины:

д ля дискретных величин,

д ля непрерывных величин;

2-й центральный момент - дисперсия случайной величины:для дискретных величин,

На практике иногда используется не дисперсия , а среднее квадратическое отклонение .

Связь между системами в общем случае характеризуется ковариацией — моментом связи; для двумерного распределения обозначаемых

Можно использовать ковариацию нормированных отклонений - коэффициент кор­реляции

где , - нормированные отклонения; среднеквадратические отклонения.

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

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

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

Теоретико-множественный подход в описании систем позволяет предложить следующую обобщенную модель (рис. 4.1, а)

Y = F : X

где:

Y={y₁,…,y_j,…,y_m} – выходная реакция системы;

X={x₁,…,x_j,…,x_n} – множество выходных воздействий;

F={F₁,…,F_j,…,F_m} – множество операторов, реализуемых системой.

Причем F_j F_R – множество физически реализуемых операторов с учетом необходимости соблюдения причинно-следственной связи

F_j(t,A) : X(t,A) → y_j(t-t₀,A),

где: t₀ – задержка реакции системы Y на воздействие Х по времени t; А={α₁,…,α_k,…,α_s} – множество дестабилизирующих факторов, генерируемых множеством угроз Т, которому противостоит множество механизмов М защиты системы (рис. 3.1).

Иллюстрацией вполне может быть граф (рис. 4.1, а), где:

y_j=F_j(t,X)

и соответствующий ему (n+2)-местный предикат

Г(y_j,F_j,x₁,…,x_n)

или инцидентор на множествах

Г(Y,F,X).

Для информационных пространств СТС X,Y олицетворяют информационные ресурсы (концентраторы и хранители информации), а F - информационно-телекоммуникационные подсистемы (операторы обработки и передачи информации).

С учетом имеющей место задачи обеспечения безопасности системы имеем

Y = F : X (T M).

Тогда постановка этой задачи примет вид

,

где Y_э – множество эталонных значений выходной реакции Y системы;

Е₀ – множество порогов безопасности системы.

При этом могут быть сформулированы также определенные оптимизационные задачи:

- с точки зрения устойчивого функционирования системы;

подсистемы защиты.

Для линейных систем (рис. 4.1,б) последние выражения не претерпят существенного изменения. В этом случае оператор F трансформируется в линейную передаточную функцию Н, где

y_j= , j=1(1)m.

При рассмотрении иерархически организованных систем (рис.4.2) m=1 или

y₀= .

По формуле Мезона для типового звена иерархических систем имеем

y₀= ,

где: x_i – ресурс i-го компонента низшего уровня иерархии;

y₀ – ресурс высшего уровня иерархии;

k_i0 и k_0i – линейные операторы передачи между вышеупомянутыми ресурсами.

Глубина обратной связи для i-го компонента составит

1-L=1- k_i0k_0i,

а петлевая передача

L= k_i0k_0i.

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

Y(t,A) = F(t,A) : X(t,A).

Для этого уместно использовать функции чувствительности

S= - дифференциальной и

- относительной.

X

H

T

Y

Рис. 4.1 Обобщенная структура системы

k_0n

k_n0

Рис 4.2. Типовое звено иерархических систем

Отсюда в первом приближении (без учета производных высшего порядка, что частенько допустимо при монотонной эволюции систем) имеем для дестабилизирующего фактора α_s и m=1 (иерархическая структура) следующее

Осуществляя эквивалентные преобразования последнего выражения, при Y=∑F_i получаем

или

.

Из данного выражения относительное отклонение для параметра Y будет равно

,

где = 1 – сумма коэффициентов вклада для каждого входа иерархической системы.

Для линейной модели

для дестабилизирующего фактора α_s, воздействующего на Н_i и x_i, имеем

.

В результате эквивалентных преобразований с учетом x_i=y/H_i получаем

.

Таким образом,

или относительное отклонение по аналогии равно

.

В случае, если угрозы Т воздействуют только на ресурсы системы х_i, получаем

.

Наоборот при воздействии на инфраструктуру Н_i имеем

.

Если пороги безопасности заданы в относительном виде

,

получаем

.

Отсюда при прогнозируемом относительном отклонении дестабилизирующего фактора Δα_s/α_s = необходимым условием обеспечения безопасности системы является

.

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

В случае, когда вместо α_s используется целый ансамбль факторов А, соответствующее выражение примет вид

.

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

Применение графов для описания систем

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

(П.1)

задан, если даны непустое множество вершин , не пересекающееся с ним множество ребер и предикат (инцидентор) . Обычно является трехместным предикатом, т. е. определенным на всех упорядоченных тройках - и , для которых и . Аналитически предикат описывается логическим высказыванием следующего вида:

, (П.2)

которое означает, что ребро соединяет вершины и . Вершины и называются смежными, а ребро - инцидентным этим вершинам в графе.

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

Согласно определению графа (П.1), для всякого элемента справедливо одно и только одно из следующих высказыва­ний:

& & ; (П.3)

(П.4)

& & . (П.5)

Логические высказывания (П.3) - (П.5) позволяют классифицировать ребра на ориентированные (направленные) ребра - дуги (П.3), петли - (П.4) и неориентированные (ненаправленные) ребра - звенья (П.5). В ряде практических случаев звенья в соответствии с высказыванием (П.5) изображаются совокупностью двух (слитых в одну) двунаправленных дуг,

,

что бывает удобно для описания макромоделей систем.

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

Элементами графа могут быть цепи и циклы. Цепью называется последовательность

элементов графа, для которой справедливо высказывание

.

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

(П.6)

для которой истинно высказывание

.

В качестве количественных характеристик пути для описания систем уместно использовать такие понятия, как длина пути и вес пути . Число ребер, образующих путь, называется длиной пути. Для пути (2.6) длина . Вес пути - произведение весов образующих его ре­бер, для пути (2.6) вес

.

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

Замкнутый путь называется контуром . Согласно выражению (П.6) для контура . Определения длины и веса контура аналогич­ны соответствующим определениям, сделанным выше для пути. Контур называется простым, если все его рёбра различны, или составным (сложным) - в противном случае. Контур называет­ся элементарным, если все его вершины различны.

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

,

,

где - число дуг, исходящих из вершины ; - число дуг, входящих в вершину .

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

.

Весом прадерева называется произведение весов всех входящих в него дуг.

Частным случаем прадерева является звезда - совокупность простых путей с общей конечной или на­чальной вершиной; эту вершину назовем центром звезды. Если центром звезды является начальная вершина путей , т.е.

,

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

,

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

Любой вершине, не являющейся центром звезды, инцидентны только одна исходящая и одна входящая дуги. Именно такие звезды и прадеревья будут использованы далее для структурной оценки систем.

Далее рассмотрим части графов. Пусть имеем два графа

и ,

где и ; - предикат, индуцированный инцидентором на множествах и . Если

,

то является частью . К числу частей относится и сам граф ; прочие его части обычно называют собственными. Для практики наибольшее значение имеют следующие два типа частей графа. Подграфом графа называется часть графа , порожденная подмножеством вершин , если подмножество ребер удовлетворяет следующему условию:

.

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

Если является суграфом графа , то сам граф называется сверхграфом; если - подграф, то - надграф, и если - часть графа, то - объемлющий граф.

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

,

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

Униграфом называется граф , не содержащий кратных ре­бер, т. е. такой, что каждая пара его вершин соединена не более чем одним ребром:

,

где - число ребер, соединяющих вершины и .

Граф, не являющийся униграфом, называется мультиграфом.

Когда никакая пара вершин не соединена более чем ребрами , т.е.

,

граф называется - графом. Отсюда следует, что - граф – это пустой граф, а - граф – это униграф.

Объединением графов называется граф , для которого

и предикат индуцирован предикатами .

Пересечением графов следует считать граф , в котором

и предикат индуцирован предикатами .

Известны также и другие операции над графами, которые под­робно изложены в.

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

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

Планарным называется граф, если он может быть графически изображен на плоскости так, что все пересечения его ребер являются лишь вершинами графа. В противном случае граф называется непланарным.

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

Используются также матрицы соседства, сечений и контуров. Однако недостаток вышеописанных матриц заключается в том, что они отражают только наличие или отсутствие инциденции между вершинами и ребрами и не учи­тывают веса ребер, которые зачастую присваиваются каждому из этих элементов при описании реальных объектов (в частности, ИО). В этом отношении более удобной следует считать мат­рицу , элементы которой определяются следующими соотноше­ниями:

;

,

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

.

.

.

.

.

.

.

.

.

…

…

…

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

Достоинством матрицы следует также считать ее соответствие системе однородных уравнений, широко применяемой для описания систем,

(П.7)

или в матричной форме

,

где - вектор переменных, соответствующих вершинам.

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

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

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

В этом случае системы уравнений могут быть записаны в виде сле­дующего матричного соотношения:

,

где , - квадратная матрица коэффициентов; , и , - -мерные векторы-столбцы независимых переменных и .

Коэффициенты (параметры информационных потоков) могут зависеть от и .

Часто встречается на практике при линейном моделировании, в т.ч. ИО, уравнение типа

, (П.8)

где - входная переменная; - выходная переменная.

Для аналоговых интегрирующих и дифференцирующих операций также справедливо (2.8) при и соответственно, где - оператор Лапласа; - постоянная времени звеньев.

Примером также может служить сумматор, описываемый уравнением

(П.9)

где - входные, а - выходные напряжения сигнала; - коэффициенты суммирования.

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

(П.10)

где - значение входного сигнала в момент времени ; - значение выходного сигнала в момент времени ; - выходной сигнал в момент времени ; - период квантования сигнала по времени.

Выражение (П.10) называется рекурсивным. Нерекурсивным (П.10) станет, если принять при .

Уравнение (П.10) аналогично по форме записи выражениям (П.8) и (П.9). Поэтому дискретные модели обычно рассматривают как системы, состоящие из унифицированных звеньев задержки, описы­ваемых уравнением , а также умножителей или и сумматоров (П.10), которые при анализе отображаются простейшими дугами с весами ребер , и .

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

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

Граф Мэзона строится на основании причинно-следственной формы исходных уравнений:

(П.11)

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

(П.12)

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

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

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

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

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

То­пологическая формула передачи может быть записана в следу­ющем обобщенном виде:

, (П.13)

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

Для различных типов графов все пути равен

,

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

При вычислении определителей может быть использована сле­дующая обобщенная формула:

, (П.14)

где - вес -го элементарного графа, образованного из исходного графа по специальным правилам, обусловленным типом графа; - число всевозможных элементарных графов, образован­ных на исходном графе. При этом вес элементарного графа из вы­ражения (П.14) равен

, (П.15)

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

Выражения (П.14) и (П.15) справедливы также и для опреде­лителя дополняющего подграфа . Как видно из формул (П.13) - (П.15), специфика используемого для расчета графа играет роль лишь при формировании (П.14) и расчете весов (П.15) элементар­ных графов. Рассмотрим эту процедуру для различных типов гра­фов.

Для графа Мэзона элементарный граф состоит из множества некасающихся контуров; фактор равен количеству некасающихся контуров, входящих в состав данного элементарно­го графа. Вес элементарного графа в этом случае

, (П.16)

где - вес -го контура, входящего в состав данного элементарного графа.

Из (П.15) следует

, (П.17)

где - вес -й дуги, входящей в состав -го контура; - длина -го контура. Следует заметить, что исходный граф может содержать несколько элементарных графов с одним и тем же фактором. Исключение составляет единственный элементарный граф с фактором , который следует считать множеством контуров, вырожденных в вершину, имеющую вес, равный 1. Поэтому с учетом (П.16), (П.17) формула для расчета определителя сигнального графа (Мэзона) часто записывается в следующем виде:

, (П.18)

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