Теория графов как инструмент системного анализа

Автор: Петухов Виктор, гр. 3512

Теория графов и её применение в системном анализе

Граф — объекст, состоящий из двух множеств (множество вершин и множество ребер). Конечный граф — такой граф, в которой количество его вершин конечно. Нуль-граф — состояит только из изолированных вершин (нет ребер). Пустой граф — не содержит ни вершин, ни ребер.

В зависимосоти от того, учитывается ли порядок вершин при описании графов, графы разделяются на:

— Ориентированные (ребро — дуга, петля — такое ребро, у которого оба конца сходятся в одной вершине)

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

Скелет мультиграфа : выкинули все кратные ребра, кроме одного и выкинули все петли.

Псевдограф : есть кратные ребра и петли. Мультиграф : есть кратные ребра, но нет петель.

Гиперграф — обобщение графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества вершин.

Полный граф — граф, у которого любые две вершины соеденены ребром. Плотный граф — полный граф, у которого при каждой вершине имеется петля.

Изомарфизм : два графа изоморфные, если существует перестановка вершин, при которой они совпадают.

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

Планарный граф — изоморфен плоскому.

Степень вершины — кол-во ребер инцидентных данной вершине.

Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некоторое подмножество инцидентных им ребер.

Частичный граф исходного графа : остатся все вершины и некоторые ребра.

Гамак — подграф графа, для которого существуют две принадлежащие ему вершины (вход и выход), такие что:

— Все дуги из входа ведут в гамак

— Любой путь, ведущий в гамак извне проходит через вход.

— Все дуги из выхода идут из гамака.

— Любой путь, идущий из гамака извне проходит через выход.

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

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

Маршрут — любая последовталеьность смежных ребер. Цепь — маршрут, все ребра которого различны (в ориентированном графе цепь называется путь).

Замкнутая цепь — цикл (в ориентированном графе цикл называется контр).

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

Эйлеров цикл — цикл, в котором содержатся все ребра графа. Задача простая, имеет однозначное решение: граф содержит Эйлеров цикл, если он связен и все локальные степени его вершин являются четными.

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

Связный неориентированный граф для любых двух вершин существует соединяющий их маршрут.

Свзный орграф — любые две вершины достижимы.

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

Бикомпонент (компонент сильной связности) — это максималньый по включению сильно связанный подграф графа.

В отличие от Гамильтоного цикла для выделения бикомпоненты существуют простые алгоритмы.

Граф можно рассматривать как набор бикомпонент, соединенных ребрами, не входящие ни в одну бикомпоненту.

Если входное воздействие попадает в одну из вершин бикомпоненты, то оно беспрепятственно распространяется по всем другим её вершинам. С точки зрения прохождения информации бикомпоненту можно рассматривать как одну вершину — такая конструкция — граф Конденсации (граф Герца).

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

1) Выявление контуров сильной связности и нейтрализация (преобразование структуры системы в безконтурный граф).

2) Смена направлений каких-либо дуг, входящих в контур

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

§5. Характеристиеские числа графа

Раскраска вершин графа — разбиение множества его вершин на не пересекающиеся подмножества, причем каждое подмножество не содержит смежных вершин.

Тогда хроматическое число графа — наименьшее число подмножеств, на которые можно разбить гарф при раскраске. Определение хроматического числа требует сложных алгоритмов переборного типа (методы целочисленного прогарммирования).

1) Составление расписания — это NP-полная задача (диспечеры используют типовые эвристики)

2) Распределение ресурсов (есть ресурсы, есть определенное кол-во работы)

3) Экономия памяти (распределение регистров в процессоре)

Цикломатическое число — наименьшее кол-во ребер, после удаления которого в графе не содержится ниодного цикла (оно указывает наименьшее число ребер, которые нужно удалить из графа для перевода его в дерево).

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

§6. Метрические свойтсва графа

Растояние между вершинами графа — длина кротчайшей цепи, соединяющей эти вершины. Длина цепи измеряется кол-вом входящих в неё ребер.

Диаметр графа — максимальное расстояние между двумя его вершинами.

Эксцентриситет — максимальное расстояние от неё до других вершин (диаметр — максимальный экцентрисистет вершины).

Центр графа — такая вершина, эксцентриситет которой равен радиусу графа. x 0 : x X[max d(x,y) ≥ max d(x 0 ,x)]

§7. Топологическая сортирвока графа

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

1) При составлении учебных планов

2) При планировании действий (разбиение целей на подцели и т. п.)

(все, что касается графов (определения — их около 80-ти) войдет в рубежку — нужно будет раскрыть всю специфику определния)

источник

• СООТВЕТСТВИЕ ГАЛУА
• ИНФОРМАЦИОННЫЕ СИСТЕМЫ
• ГРАФОВАЯ МОДЕЛЬ
• ТЕОРИЯ ГРАФОВ
• ИНВАРИАНТНЫЕ МЕТОДЫ

Информационные системы на сегодняшний день являются неотъемлемой частью различных проектов в самых разнообразных сферах как теоретической, так и практической деятельности человека [1, 2, 3]. В силу требований, предъявляемых к современным информационным системам, они должны быть ориентированы на пользовательские запросы. Последние же научные достижения и ресурсные возможности компьютерной техники при их разработке также предопределяют их клиент-серверную направленность [4, 5]. Таким образом, информационные системы должны функционировать в многопользовательском режиме, поддерживать кроссплатформенность и оперативно обновлять системные данные.

Все эти возможности закладываются в информационную систему при ее проектировании и последующей разработке [6]. Этап проектирования системы играет при этом определяющую роль. На этом этапе выбор математического инструментария при реализации функционала информационной системы устанавливает границы дальнейшей ее применимости [7, 8, 9].

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

На этапе проектирования информационной системы строится ее графовая модель, которая позволяет определить степень влияния одних структурных элементов на другие. Для этого при анализе взаимосвязей в системе применяют инварианты теории графов. Как показывает ряд исследований [11, 12, 13], такой гибкий инструментарий открывает широкие перспективы при дальнейшем исследовании информационной системы. Он позволяет изучить не только ее структурную организацию на этапе разработки системы, но и анализировать ее содержание на этапах заполнения, работы и сопровождения.

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

• полустепени исхода и захода вершины графа, параметры базовости и выводимости вершины, векторы полустепеней исхода и захода вершин графа;
• число слабых компонент графа, число «независимости» графа и коэффициенты «независимости» его подмножеств, число «неплотности», число t-взаимозависимости и число t-взаимонезависимости;
• вектор разделения, параметры внешнего и внутреннего разделения вершины графа, внешние и внутренние центры и радиусы вершины графа;
• число полукомпонент диаметра p, диаметр, полуплотность, p-полуплотность подмножеств графа;
• вектор и матрица надежности, прочность связи, слабая перемычка, прочность слабой перемычки, вектор прочности графа.

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

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

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

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

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

На этапе проектирования информационной системы следует предусмотреть целостный комплекс инструментов для работы с ней пользователя. Графовые модели информационной системы позволяют исследовать системные взаимосвязи между ее структурными элементами [14, 15]. Для всестороннего содержательного анализа требуются иные инструменты, которых достаточное множество среди различных приложений математики. В тоже время выбор инструмента следует проводить так, чтобы он отвечал принципу комплексности – позволял исследовать и внутреннюю организацию информационной системы, и ее содержательную основу. Однако далеко не все инструменты подходят для этого, а наличие слишком большого количества функционала для изучения системных процессов во многих случаях избыточно.

Соответствия Галуа выступают как раз тем инструментом, который, несмотря на простоту своего математического определения, позволяет изучать как структурные взаимосвязи элементов системы, так и собственно ее контент. При этом соответствие Галуа применимо на любом виде представления модели информационной системы [16, 17]. Возможно применение соответствия Галуа в информационных системах с табличной, иерархической, графовой, сетевой и других формах структурной организации. Это делает методологию инвариантной по отношению к виду модели.

Соответствие Галуа дополняет анализ системных элементов модели информационной системы, полученный с использованием инвариантов теории графов [18]. Методология исследования основана на выявлении ключевых системных компонентов для различных подмножеств модели. В качестве таковых могут выступать как отдельные элементы, так и их совокупности. Характеристики этих компонентов будут являться определяющими для взаимосвязанных – ассоциированных с ними подмножеств, исследуемых с помощью соответствия Галуа. По значениям и «поведению» данных компонентов можно судить об ассоциированных с ними других элементах информационной системы.

Так соответствие Галуа позволяет выявить те системные компоненты, которые определяют ее фундаментальную основу. «Выпадение» одного из них будет оказывать существенное влияние на функционирование информационной системы в целом, вплоть до прекращения ее работы [19]. Такой анализ важно провести на этапе проектирования программной среды системы, чтобы выделить ее функциональное ядро и обеспечить защиту работы от сбоев.

Данную задачу можно решить и другими методами [20, 21]. Однако комплексное исследование информационной системы с использованием соответствия Галуа на этапе работы с ее контентом дает пользователю неоспоримые перед другими методами преимущества [22]. Главное преимущество предопределено тем, что при необходимости структурных изменений информационной системы, связанных с ее содержательным наполнением, будет использоваться тот же инструментарий, только в других целях. Это обеспечит наиболее высокую степень надежности информационной системы, уменьшит временные затраты на внесение изменений и доработок, избавит разработчика программной среды от поиска необходимого инструментария для решения очередной задачи функционирования системной оболочки.

Кроме того, как показывает практика применения методологии соответствия Галуа [23, 24, 25], сведения, полученные об информационной системе, носят достоверный характер. Данные анализа поведения системы подтверждают интуитивные выводы, совпадают с показателями других методов изучения структуры и содержания информационной системы. При этом отличительной особенностью методологии соответствия Галуа является ее оперативность.

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

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

1. Андреева А. В., Максимова Н. А. ИСУ ВУЗ как инструмент управления качеством образования // В мире научных открытий. – 2013. – № 11.8 (47). – С. 22-28.
2. Мазилов А. О., Ступников А. В., Баженов Р. И. Разработка информационной системы учета заявок лаборатории компьютерных систем // Постулат. – 2015. – № 1 (1). – С. 5.
3. Козлов С. В. Особенности применения системы индивидуального тестирования «Комплекс измерения обученности» в школьном курсе информатики // Системы компьютерной математики и их приложения. – Смоленск: СмолГУ, 2008. С. 247-251.
4. Козлов С. В. Система индивидуального тестирования «Комплекс измерения обученности» // Системы компьютерной математики и их приложения. – Смоленск: СмолГУ, 2007. С. 223-225.
5. Киселева О. М. Реализация принципа индивидуализации образовательного процесса с использованием программы «Траектория обучения» // Современные научные исследования и инновации. – 2014. – № 5-2 (37). – С. 41.
6. Козлов С. В. Актуальные вопросы использования адаптивных информационно-образовательных систем в профильной школе // Наука и образование в XXI веке: сборник научных трудов по материалам международной научно-практической конференции 30 сентября 2013 г.: в 34 частях. – Ч. 21. – Тамбов: Бизнес-Наука-Общество, 2013. – С. 48-51.
7. Лагунова А. А., Пронина О. Ю., Баженов Р. И. Проект разработки и внедрения информационной системы по учету прохождения курсов повышения квалификации сотрудников // Современные научные исследования и инновации. – 2015. – № 12 (56). – С. 677-685.
8. Козлов С. В. Математические аспекты выбора оптимального набора тестовых заданий индивидуального теста // Психология, социология и педагогика. – 2014. – № 9 (36) [Электронный ресурс]. URL: http://psychology.snauka.ru/2014/09/3603 (дата обращения: 07.10.2014).
9. Киселева О. М. Особенности использования математических методов для решения педагогических проблем // Гуманитарные научные исследования. – 2014. – № 6 (34). – С. 15.
10. Козлов С. В. Интерпретация инвариантов теории графов в контексте применения соответствия Галуа при создании и сопровождении информационных систем // International Journal of Open Information Technologies. – 2016. – Т. 4. – № 7. С. 38-44.
11. Киселева О. М. Пример применения методов математического моделирования // NovaInfo.Ru. – 2016. – Т. 1. – № 42. – С. 67-70.
12. Козлов С. В. Вопросы формирования индивидуального теста // Гуманитарные научные исследования. – 2014. – № 10 (38). – С. 64-70.
13. Смикун А. Л., Баженов Р. И. Разработка информационной системы отдела связи // Современные научные исследования и инновации. – 2015. – № 6-2 (50). – С. 92-103.
14. Козлов С. В. Программный комплекс «Advanced Tester»: проектирование индивидуальных тестов в автоматизированной информационной системе // Современная педагогика. – 2014. – № 9 [Электронный ресурс]. URL: http://pedagogika.snauka.ru/2014/09/2696 (дата обращения: 29.10.2014).
15. Емельченков Е. П., Киселева О. М. О представлении предметных областей с помощью семантических сетей // NovaInfo.Ru. – 2016. – Т. 2. № 42. – С. 17-23.
16. Козлов С. В. Применение соответствия Галуа для анализа данных в информационных системах // Траектория науки. – 2016. – Т. 2. № 3 (8). –С. 18.
17. Козлов С. В. Использование соответствия Галуа как инварианта отбора контента при проектировании информационных систем // Современные информационные технологии и ИТ-образование. 2015. Т. 2. № 11. С. 220-225.
18. Козлов С. В. Применение методов функционального анализа при формировании оптимальных стратегий обучения школьников // Международный журнал экспериментального образования. – 2016. – № 3-2. – С. 182-185; URL: http://www.expeducation.ru/ru/article/view? >

Электронное периодическое издание зарегистрировано в Федеральной службе по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор), свидетельство о регистрации СМИ — ЭЛ № ФС77-41429 от 23.07.2010 г.

Соучредители СМИ: Долганов А.А., Майоров Е.В.

источник

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

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

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

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

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

О Шаи в своей книге «THE MULTIDISCIPLINARY COMBINATORIAL APPROACH AND ITS APPLICATIONS IN ENGINEERING» выделяет следующие типы графических моделей систем:

4. Модель устойчивости (сопротивления). (43)

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

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

Для математического описания состава и структуры физической системы используются два типа соотношений:

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

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

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

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

Рассмотрим одну из таких моделей на примере электрической цепи.

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

Сопротивление – компонент, в котором происходит необратимое преобразование электрической энергии в тепло. Зависимость между током (поперечная переменная) и напряжением (продольная переменная) может быть представлена в одной из двух форм: i * R (t)=G*U*R (t) или U*R (t)=Ri *R (t), где параметры G – проводимость,

R – сопротивление (G=R -1 и R=G -1).

Емкость – компонент, накапливающий электрическую энергию. Заряд q(t) связан с напряжением U С (t) на линейной емкости соотношением q(t)=CU C (t), где С – параметр, называемый емкостью.

Индуктивность – компонент, накапливающий магнитную энергию.

Магнитный поток ψ (t) линейной индуктивности пропорционален, протекающему в ней току i L (t), т.е. ψ (t)=Li L (t), где L – параметр, называемый индуктивностью.

Идеальные электрические двухполюсники: а – резистор; б – конденсатор; в – катушка индуктивности; г – источник напряжения; д – источник тока.

Источники энергии в электрических цепях представляются идеальными двухполюсниками двух типов. Источник напряжения – двухполюсник (рис. 4.г), напряжение в котором определяется некоторой функцией времени е(t) и не зависит от протекающего по нему тока, т.е. U E (t)=e(t). Источник тока – двухполюсник (рис. 4.д), ток в котором также определяется некоторой функцией времени j(t) и не зависит от приложенного напряжения, т.е. i J (t)=j(t).

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

Направления дуг пассивных двухполюсников можно выбирать произвольно. Дуги активных двухполюсников ориентируются по направлению источника тока и противоположно направлению источника напряжения (направление дуги указывает на положительное направление тока и противоположно положительному направлению напряжения). (44)

Рисунок 5 — Электрическая схема (а) и ее изоморфные графы (б и в).

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9447 — | 7325 — или читать все.

193.124.117.139 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

источник

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

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

Рассмотрим другие подходы к анализу систем с использованием теории графов.

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

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

2. Сигнальный граф тоже является ориентированным графом.

3. Величина, соответствующая вершине-началу ребра, называется входной величиной ребра. Если из вершины выходит несколько ребер, то входные величины всех этих ребер одинаковы и равны величине, соответствующей вершине.

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

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

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

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

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

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

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

Аналогично, нелинейному элементу в графе G соответствует нелинейный элемент в графе G´, осуществляющий умножение входных величин нелинейного элемента на переменные коэффициенты d(f)/dx_k и суммирование полученных произведений. Если, кроме того, нелинейная характеристика зависит от параметра, то к выходу нелинейного элемента добавляется связывающее воздействие, вырабатываемое также посредством нелинейного элемента.

источник

Автор работы: Пользователь скрыл имя, 22 Июня 2011 в 17:08, курсовая работа

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

ВВЕДЕНИЕ 3
РАЗДЕЛ 1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ И СТАНОВЛЕНИЯ СИСТЕМНОГО ПОДХОДА 4
1. 1. ВОЗНИКНОВЕНИЕ И СТАНОВЛЕНИЕ СИСТЕМНЫХ ИДЕЙ 4
1. 2. ВОЗНИКНОВЕНИЕ И РАЗВИТИЕ НАУКИ О СИСТЕМАХ 5
РАЗДЕЛ 2. ОСНОВЫ ТЕОРИИ СИСТЕМ 9
2. 1. ОСНОВНЫЕ СМЫСЛОВЫЕ ВАРИАЦИИ ПОНЯТИЯ “СИСТЕМА” 9
2. 2. ХАРАКТЕРИСТИКА ОСНОВНЫХ ОПРЕДЕЛЕНИЙ СИСТЕМЫ 10
2. 3. ОСНОВНЫЕ КАТЕГОРИИ СИСТЕМНОГО ПОДХОДА 11
2. 4. ВНЕШНИЕ И ВНУТРЕННИЕ СИСТЕМООБРАЗУЮЩИЕ ФАКТОРЫ 13
2. 5. СУЩНОСТЬ И НЕОБХОДИМОСТЬ КЛАССИФИКАЦИИ СИСТЕМ 15
2. 6. СУЩНОСТНАЯ КЛАССИФИКАЦИЯ СИСТЕМ 16
2. 7. СОСТАВ СИСТЕМЫ 21
2. 8. ПОНЯТИЕ СТРУКТУРЫ СИСТЕМЫ 24
РАЗДЕЛ 3. СИСТЕМНЫЙ АНАЛИЗ 26
3. 1. МЕТОДОЛОГИЯ СИСТЕМНОГО АНАЛИЗА 27
3. 2. ВИДЫ СИСТЕМНОГО АНАЛИЗА 30
3. 3. СТРУКТУРА СИСТЕМНОГО АНАЛИЗА 32
ВЫВОД 37
ЛИТЕРАТУРА 38

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

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

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

Классификация связей, предложенная И. В. Блаубергом, В. Н. Садовским, Э. Г. Юдиным, которые выделяют связи взаимодействия, порождения, преобразования, строения, функционирования, развития, управления, является слишком обобщенной. Это приводит к тому, что связь заслоняется более сложными явлениями (взаимодействие, строение, функционирование и т. п.). В. В. Дружинин и Д. С. Конторов делят связи на прямые и обратные. При этом прямые связи бывают усиливающие (ослабляющие) сигнал, ограничивающие, запаздывающие и селектирующие (осуществляющие отбор), а обратные делятся: на положительные (усиливающие исходный процесс) и отрицательные (ослабляющие исходный сигнал); на гладкие (действуют во всем диапазоне изменений выходного процесса) и пороговые (действуют, когда процесс превышает некоторое значение, называемое нижним порогом и не превышает некоторое значение, выступающее как верхний порог); на двусторонние, реагирующие на увеличение и на уменьшение; связи первого, второго и старшего порядка; на связи мгновенные, запаздывающие и опережающие.

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

• формального — фиксирует наличие и направленность связи;

• функционального — фиксирует наличие или отсутствие функциональности в связях;

• логического — дается объяснение природы связей;

• содержательного — анализируются содержание, природа связей.

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

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

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

В свою очередь функциональные можно представить как связи:

• порождения, или причинно-следственные связи;

• преобразования— реализуются путем непосредственного взаимодействия двух объектов с переходом их в новое состояние;

• строения, или структурные, — обеспечивают строение системы;

• функциональные (в узком смысле слова) — обеспечивают функционирование системы;

• развития — смена состояний отличается качественными изменениями;

• управления — обеспечивают процесс управления системой

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

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

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

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

Максимальное количество связей в системе определяется числом возможных сочетаний между элементами и может быть найдено по формуле

где n— количество элементов, входящих в систему;

С— количество связей между ними.

Если система состоит из пяти элементов, то максимальное количество связей для нее равно 20. Эта формула верна только для тех систем, у которых между двумя элементами допустима одна связь.

Структура системы (лат. structura — строение, порядок связи) — это совокупность устойчивых связей между элементами системы, которые обеспечивают целостность системы и тождественность самой себе. Структура оказывается намного богаче состава, ибо состав отвечает на вопрос “Из чего состоит система?”, а структура обеспечивает ответ на более сложный вопрос: “Как устроена система?”. Один из основоположников исследования структур В. И. Свидерский писал: “Под понятием структуры мы будем понимать принцип, способ, закон связи элементов целого, систему отношений элементов в рамках данного целого”, т.е. термин “структура” является более богатым по сравнению с термином “состав”. Он обладает способностью не только фиксировать свойства системы, но и объяснять их определенным строением системы. Система становится системой только тогда, когда ее элементы, имеющие определенную пространственную, временную и целевую организацию, определенным образом взаимосвязываются один с другим.

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

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

Структуры можно классифицировать по разным основаниям:

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

Любая структура описывается следующими основными характеристиками:

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

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

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

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

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

Рис. 4 Граф и матрица инциденций

В матрице наличие связи фиксируется единицей, а ее отсутствие — нулем.

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

Системный анализ представляет собой важный объект методологических исследований и одно из наиболее бурно развивающихся научных направлений. Ему посвящено множество монографий и статей. Наиболее известные его исследовател: В. Г. Афанасьев, Л. Берталанфи, И. В. Блауберг, А. А. Богданов, В. М. Глушков, Т. Гоббс, О. Конт, В. А. Карташов, С. А. Кузьмин, Ю. Г. Марков, Р. Мертон, М. Месарович, Т. Парсонс, Л. А. Петрушенко, В. Н. Садовский, М. И. Сетров, Г. Спенсер, В. Н. Спицнадель, Я. Такахара, В. С. Тюхтин, А. И. Уемов, У. Черчмен, Э. Г., Юдин и др.

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

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

Ситуация усугубляется не только тем, что не разработаны интеллектуальные технологии системного анализа, но и тем, что нет однозначности в понимании самого системного анализа. Это, несмотря на то, что уже 90 лет прошло со времени выхода в свет основополагающего труда в области теории систем — “Тектологии” А. А. Богданова, и почти полстолетия насчитывает история развития системных идей.

источник

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

Классификация применяемых графиков по признакам и видам приведена в табл. 2.8.

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

Таковы геометрия, теория графов.

Исторически понятие «графа» первоначально было введено Л. Эйлером.

Основные понятия теории графов приведены в табл. 2.9, которая поможет начать самостоятельное ее изучение.

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

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

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

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

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

Однако в последнем случае важно понимать основные недостатки СПУ.

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

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

Для снижения доли «ручного» труда полезно сочетать графические представления с лингвистическими и семиотическими, разрабатывая языки автоматизации формирования сетевой модели. На основе такого сочетания методов возникли новые направления моделирования — стрyкmурно-лингвистическое, графо-семиотическое и т.п.

источник