Меньков А.В., Острейковский В.А. Теоретические основы автоматизированного управления

Подождите немного. Документ загружается.

110

Отметим их. Одним из таих методов является эспертный ме-

тод. Он применяется в тех слчаях, о да при исследовании

сложных систем возниают проблемы, оторые не дается пред-

ставить в виде формальных математичесих задач. В таих слча-

ях прибе ают  сл ам эспертов, лиц, чья интиция и опыт мо-

т меньшить сложность проблемы. И, наонец, для решения

задач выбора и принятия решений в сложных проблемных сит-

ациях создаются специальные человео-машинные, проблемно-

ориентированные системы. Системы поддержи решений ориен-

тированы не на автоматизацию фнций лица, принимающе о

решение, а на предоставление ем помощи в поисе хороше о ре-

шения.

Подводя ито , отметим, что проблема выбора и принятия ре-

шений — центральная проблема системно о анализа. Налицо

сложности, оторые возниают перед системным аналитиом.

Но, с др ой стороны, имеется развитый математичесий и эв-

ристичесий аппарат, оторый является мощным оржием, по-

мо ающим обоснованно подходить  проблеме выбора.

3.4.12. Внедрение резльтатов анализа

Системный анализ является приладной наой, е о онеч-

ная цель — изменение сществющей ситации в соответствии с

поставленными целями. Оончательное сждение о правильнос-

ти и полезности системно о анализа можно сделать лишь на ос-

новании резльтатов е о пратичесо о применения. Конечный

резльтат бдет зависеть не тольо от то о, насольо совершен-

ны и теоретичеси обоснованы методы, применяемые при прове-

дении анализа, но и от то о, насольо рамотно и ачественно

реализованы полченные реомендации.

В настоящее время вопросам внедрения резльтатов систем-

но о анализа в прати деляется повышенное внимание.

В этом направлении можно отметить работы Р. Аоффа и П. Че-

лэнда. Следет заметить, что пратиа системных исследований

и пратиа внедрения их резльтатов сщественно различаются

для систем разных типов. Со ласно лассифиации, введенной

П. Челэндом, системы делятся на три типа: естественные, ис-

сственные и социотехничесие системы. В системах перво о

типа связи образованы и действют природным образом. Приме-

рами таих систем мо т слжить эоло ичесие, физичесие,

химичесие, биоло ичесие и т. п. системы. В системах второ о

типа связи образованы в резльтате человечесой деятельности.

Примерами мо т слжить всевозможные техничесие системы.

111

В системах третье о типа, помимо природных связей, важню

роль и рают межличностные связи. Таие связи обсловлены не

природными свойствами объетов, а льтрными традициями,

воспитанием частвющих в системе сбъетов, их харатером и

др. особенностями.

Системный анализ применяется для исследования систем

всех трех типов. В аждой из систем есть свои особенности, тре-

бющие чета при ор анизации работ по внедрению резльтатов.

Наиболее велиа доля слабостртрированных проблем в систе-

мах третье о типа. Следовательно, наиболее сложна пратиа

внедрения резльтатов системных исследований в этих системах.

При внедрении резльтатов системно о анализа необходимо

иметь ввид следющее обстоятельство. Работа осществляется

на лиента (заазчиа), обладающе о властью, достаточной для

изменения системы теми способами, оторые бдт определены

в резльтате системно о анализа. В работе должны непосредс-

твенно частвовать все заинтересованные стороны. Заинтересо-

ванные стороны — это те, то отвечает за решение проблемы, и

те, о о эта проблема непосредственно асается. В резльтате

внедрения системных исследований необходимо обеспечить

лчшение работы ор анизации заазчиа с точи зрения хотя бы

одной из заинтересованных сторон, при этом не допсаются

хдшения этой работы с точи зрения всех остальных частни-

ов проблемной ситации.

Говоря о внедрении резльтатов системно о анализа, важно

отметить, что в реальной жизни ситация, о да сначала прово-

дят исследования, а затем их резльтаты внедряют в прати

встречается райне редо, лишь в тех слчаях, о да речь идет о

простых системах. Социотехничесие системы изменяются с те-

чением времени а сами по себе, та и под влиянием исследо-

ваний. В процессе проведения системно о анализа изменяется

состояние проблемной ситации, цели системы, персональный и

оличественный состав частниов, соотношения межд заинте-

ресованными сторонами. Кроме то о, следет заметить, что реа-

лизация принятых решений влияет на все фаторы фнциони-

рования системы. Этапы исследования и внедрения в тао о типа

системах фатичеси сливаются. То есть идет итеративный про-

цесс. Проводимые исследования оазывают влияние на жизнеде-

ятельность системы и это видоизменяет проблемню ситацию,

ставит новю задач исследований. Новая проблемная ситация

стимлирет дальнейшее проведение системно о анализа и т. д.

Таим образом, проблема постепенно решается в ходе ативно о

исследования.

112

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Объясните, почем системность является общим свойством материи.

2. Что таое системные представления?

3. Рассажите о системном подходе и системных исследованиях.

4. Расройте термин «системный анализ».

5. Каие Вы знаете определения системно(о анализа?

6. Из аих этапов состоит системный анализ?

7. Ка Вы представляете себе методи системно(о анализа?

8. Перечислите процедры системно(о анализа.

9. В чем состоит формлирование проблемы при системном анализе?

10. Дайте определение цели системно(о анализа.

11. Каов порядо анализа стртры системы?

12. С аой целью осществляется сбор данных о фнционировании

системы?

13. Каие Вы знаете методы анализа информационных потоов?

14. Зачем необходимо построение модели системы?

15. Ка осществляется провера адеватности модели системы?

16. В чем состоит анализ неопределенности и чвствительности модели

системы?

17. Рассажите о видах ресрсов, использемых при реализации задач

системно(о анализа.

18. С аой целью выполняется формирование ритериев для систем-

но(о анализа?

19. Каим образом производится (енерирование альтернатив при сис-

темном анализе?

20. Перечислите методы, использемые в системном анализе для прове-

дения работы по формированию множества альтернатив.

21. Каие сложности возниают при решении задач выбора и принятия

решений?

22. Каим образом осществляется внедрение резльтатов системно(о

анализа?

Глава 4

МОДЕЛИ АНАЛИЗА СТРУКТУРЫ АСУ

В этой лаве изложены цели и задачи стртрно о анализа

АСУ с позиций ор анизации, фнций правления, использе-

мых ал оритмов, с позиций использемых техничесих средств.

Рассмотрены три обычно использемых ровня описания

стртры АСУ. Приводится аппарат формализации описания

стртры, для че о изла аются минимально необходимые сведе-

113

ния из теории рафов. Рассмотрен ал оритм порядочивания,

позволяющий формально разместить элементы стртры по

ровням стртры. Изложена последовательность введения чис-

ловой фнции, что позволяет определять масимальные и ми-

нимальные пти на стртре. Приведенный ал оритм деомпо-

зиции стртры АСУ позволяет минимизировать число элемен-

тов, составляющих систем, исходя тольо из стртрных

свойств этой системы. Методиа анализа потоов информации

является мощным средством решения множества пратичесих

задач. Рассмотренные математичесие модели стртрно-топо-

ло ичесих харатеристи систем позволяют оличественно оце-

нить ачество стртры и ее элементов с позиций общесистем-

но о подхода. Предложена методиа построения моделей фн-

ционирования ор анизационных систем.

В резльтате изчения материала данной лавы стденты

должны знать принципы, методы и средства системно о анали-

за, основные лассы моделей ор анизационных стртр, мето-

ды их формализации и ал оритмизации. Они должны меть вы-

полнять общесистемный анализ и необходимые общесистемные

расчеты.

4.1. Цели и задачи стртрноо анализа АСУ

Одной из лавных задач стртрно о анализа АСУ является

построение на лядной формальной модели, отображающей

процесс взаимодействия межд элементами или подсистемами,

составляющими систем, а таже их взаимодействие с внешней

средой.

При создании АСУ их стртрные модели мо т рассматри-

ваться с различных позиций: с позиции ор анизации, фнций

правления, использемых ал оритмов, использемых техничес-

их средств и т.п. В соответствии с этим мо т быть выделены

следющие аспеты стртры одной и той же системы и, а

следствие, следющие модели:

— ор анизационная стртра и ее модель;

— фнциональная стртра и ее модель;

— ал оритмичесая стртра и ее модель;

— техничесая стртра и ее модель и т.п.

Оранизационная стртра. Ка правило, она отображает со-

бой стртр правления, оторая сложилась на объете автома-

тизации (например, на предприятии) и оторая совершенствется

при внедрении АСУ. Эта стртра является основной и именно с

нее следет начинать анализ и последющий синтез АСУ.

112

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Объясните, почем системность является общим свойством материи.

2. Что таое системные представления?

3. Рассажите о системном подходе и системных исследованиях.

4. Расройте термин «системный анализ».

5. Каие Вы знаете определения системно(о анализа?

6. Из аих этапов состоит системный анализ?

7. Ка Вы представляете себе методи системно(о анализа?

8. Перечислите процедры системно(о анализа.

9. В чем состоит формлирование проблемы при системном анализе?

10. Дайте определение цели системно(о анализа.

11. Каов порядо анализа стртры системы?

12. С аой целью осществляется сбор данных о фнционировании

системы?

13. Каие Вы знаете методы анализа информационных потоов?

14. Зачем необходимо построение модели системы?

15. Ка осществляется провера адеватности модели системы?

16. В чем состоит анализ неопределенности и чвствительности модели

системы?

17. Рассажите о видах ресрсов, использемых при реализации задач

системно(о анализа.

18. С аой целью выполняется формирование ритериев для систем-

но(о анализа?

19. Каим образом производится (енерирование альтернатив при сис-

темном анализе?

20. Перечислите методы, использемые в системном анализе для прове-

дения работы по формированию множества альтернатив.

21. Каие сложности возниают при решении задач выбора и принятия

решений?

22. Каим образом осществляется внедрение резльтатов системно(о

анализа?

Глава 4

МОДЕЛИ АНАЛИЗА СТРУКТУРЫ АСУ

В этой лаве изложены цели и задачи стртрно о анализа

АСУ с позиций ор анизации, фнций правления, использе-

мых ал оритмов, с позиций использемых техничесих средств.

Рассмотрены три обычно использемых ровня описания

стртры АСУ. Приводится аппарат формализации описания

стртры, для че о изла аются минимально необходимые сведе-

113

ния из теории рафов. Рассмотрен ал оритм порядочивания,

позволяющий формально разместить элементы стртры по

ровням стртры. Изложена последовательность введения чис-

ловой фнции, что позволяет определять масимальные и ми-

нимальные пти на стртре. Приведенный ал оритм деомпо-

зиции стртры АСУ позволяет минимизировать число элемен-

тов, составляющих систем, исходя тольо из стртрных

свойств этой системы. Методиа анализа потоов информации

является мощным средством решения множества пратичесих

задач. Рассмотренные математичесие модели стртрно-топо-

ло ичесих харатеристи систем позволяют оличественно оце-

нить ачество стртры и ее элементов с позиций общесистем-

но о подхода. Предложена методиа построения моделей фн-

ционирования ор анизационных систем.

В резльтате изчения материала данной лавы стденты

должны знать принципы, методы и средства системно о анали-

за, основные лассы моделей ор анизационных стртр, мето-

ды их формализации и ал оритмизации. Они должны меть вы-

полнять общесистемный анализ и необходимые общесистемные

расчеты.

4.1. Цели и задачи стртрноо анализа АСУ

Одной из лавных задач стртрно о анализа АСУ является

построение на лядной формальной модели, отображающей

процесс взаимодействия межд элементами или подсистемами,

составляющими систем, а таже их взаимодействие с внешней

средой.

При создании АСУ их стртрные модели мо т рассматри-

ваться с различных позиций: с позиции ор анизации, фнций

правления, использемых ал оритмов, использемых техничес-

их средств и т.п. В соответствии с этим мо т быть выделены

следющие аспеты стртры одной и той же системы и, а

следствие, следющие модели:

— ор анизационная стртра и ее модель;

— фнциональная стртра и ее модель;

— ал оритмичесая стртра и ее модель;

— техничесая стртра и ее модель и т.п.

Оранизационная стртра. Ка правило, она отображает со-

бой стртр правления, оторая сложилась на объете автома-

тизации (например, на предприятии) и оторая совершенствется

при внедрении АСУ. Эта стртра является основной и именно с

нее следет начинать анализ и последющий синтез АСУ.

114

Основными элементами ор анизационной стртры являют-

ся подразделения аппарата правления и отдельные лица-опера-

торы, оторые связаны с анализом доментооборота и процед-

рой принятия правленчесих решений.

Основные направления совершенствования ор анизацион-

ной стртры:

— соращение излишних подразделений или операторов;

— минимизация связей межд этими элементами системы

(подразделения и операторы);

— повышение пропсной способности этих связей;

— порядочение доментооборота;

— ливидация цилов в движении доментов и т.п.

При анализе ор анизационной стртры решаются следю-

щие задачи:

— описание состава ор анизации и построение ее стртр-

ной схемы;

— определение фнций отдельных подразделений и опера-

торов;

— описание материальных и информационных связей;

— построение обобщенной стртрной информационной

модели ор анизации.

Фнциональная стртра.Она отображает фнции, выпол-

няемые отдельными элементами системы (подразделениями и

операторами) в составе ор анизационной стртры. В принципе

одной и той же ор анизационной стртре может соответство-

вать несольо различных фнциональных стртр.

Основные направления совершенствования фнциональной

стртры:

— странение параллелизма в выполнении фнций правления;

— освобождение элементов системы от выполнения фн-

ций, не предсмотренных соответствющими должност-

ными обязанностями;

— перераспределение фнций правления с целью оптими-

зации;

— создание масимально четих онтров ответственности.

При анализе фнциональной стртры решаются следю-

щие основные задачи:

— изчаются фнции правления в стртрных подразде-

лениях системы;

— выбирается состав фнций, подлежащих автоматизации;

— определяется взаимосвязь этих фнций;

— составляется обобщенная фнциональная стртра за-

дач правления.

115

Алоритмичесая стртра. Она отображает совопность ис-

польземых ал оритмов и последовательность их деомпозиции,

что позволяет в дальнейшем перейти  созданию про раммно о

обеспечения.

Основные направления совершенствования ал оритмичесой

стртры:

— использование стандартных (типовых) ал оритмов обра-

боти информации;

— повышение точности, сорости и надежности вычислений;

— соращение требемых объемов памяти;

— совершенствование отдельных ал оритмов.

При анализе ал оритмичесой стртры решаются следю-

щие задачи:

— выделение омплесов задач, отдельных задач, ал орит-

мов, модлей ал оритмов и т. п.;

— определение их информационно-ло ичесой взаимосвязи;

— определение последовательности их реализации.

Техничесая стртра. Техничесая стртра отображает

перечень и взаимосвязь техничесих стройств, использемых

для построения системы. При анализе техничесой стртры ре-

шаются следющие задачи:

— определяются элементы, частвющие в основных инфор-

мационных процессах: ре истрация и под отова инфор-

мации, сбор и передача, хранение и обработа, воспроиз-

ведение и выдача;

— составляется формальная стртрная модель системы тех-

ничесих средств с четом тополо ии расположения эле-

ментов, информационной и энер етичесой их взаимосвя-

зи, а таже связи с внешней средой.

4.2. Уровни описания стртры АСУ

Независимо от перечисленных аспетов рассмотрения систе-

мы, общая задача стртрно о анализа состоит в том, чтобы, ис-

ходя из заданно о описания элементов и непосредственных свя-

зей межд ними, полчить залючение о стртрных свойствах

системы и ее основных подсистем. Применительно  автомати-

зированным системам использется три ровня их описания:

— наличие связей;

— наличие и направление связей;

— наличие и направление связей и вид и направление движе-

ния си налов, оторые определяются взаимодействием эле-

ментов.

114

Основными элементами ор анизационной стртры являют-

ся подразделения аппарата правления и отдельные лица-опера-

торы, оторые связаны с анализом доментооборота и процед-

рой принятия правленчесих решений.

Основные направления совершенствования ор анизацион-

ной стртры:

— соращение излишних подразделений или операторов;

— минимизация связей межд этими элементами системы

(подразделения и операторы);

— повышение пропсной способности этих связей;

— порядочение доментооборота;

— ливидация цилов в движении доментов и т.п.

При анализе ор анизационной стртры решаются следю-

щие задачи:

— описание состава ор анизации и построение ее стртр-

ной схемы;

— определение фнций отдельных подразделений и опера-

торов;

— описание материальных и информационных связей;

— построение обобщенной стртрной информационной

модели ор анизации.

Фнциональная стртра.Она отображает фнции, выпол-

няемые отдельными элементами системы (подразделениями и

операторами) в составе ор анизационной стртры. В принципе

одной и той же ор анизационной стртре может соответство-

вать несольо различных фнциональных стртр.

Основные направления совершенствования фнциональной

стртры:

— странение параллелизма в выполнении фнций правления;

— освобождение элементов системы от выполнения фн-

ций, не предсмотренных соответствющими должност-

ными обязанностями;

— перераспределение фнций правления с целью оптими-

зации;

— создание масимально четих онтров ответственности.

При анализе фнциональной стртры решаются следю-

щие основные задачи:

— изчаются фнции правления в стртрных подразде-

лениях системы;

— выбирается состав фнций, подлежащих автоматизации;

— определяется взаимосвязь этих фнций;

— составляется обобщенная фнциональная стртра за-

дач правления.

115

Алоритмичесая стртра. Она отображает совопность ис-

польземых ал оритмов и последовательность их деомпозиции,

что позволяет в дальнейшем перейти  созданию про раммно о

обеспечения.

Основные направления совершенствования ал оритмичесой

стртры:

— использование стандартных (типовых) ал оритмов обра-

боти информации;

— повышение точности, сорости и надежности вычислений;

— соращение требемых объемов памяти;

— совершенствование отдельных ал оритмов.

При анализе ал оритмичесой стртры решаются следю-

щие задачи:

— выделение омплесов задач, отдельных задач, ал орит-

мов, модлей ал оритмов и т. п.;

— определение их информационно-ло ичесой взаимосвязи;

— определение последовательности их реализации.

Техничесая стртра. Техничесая стртра отображает

перечень и взаимосвязь техничесих стройств, использемых

для построения системы. При анализе техничесой стртры ре-

шаются следющие задачи:

— определяются элементы, частвющие в основных инфор-

мационных процессах: ре истрация и под отова инфор-

мации, сбор и передача, хранение и обработа, воспроиз-

ведение и выдача;

— составляется формальная стртрная модель системы тех-

ничесих средств с четом тополо ии расположения эле-

ментов, информационной и энер етичесой их взаимосвя-

зи, а таже связи с внешней средой.

4.2. Уровни описания стртры АСУ

Независимо от перечисленных аспетов рассмотрения систе-

мы, общая задача стртрно о анализа состоит в том, чтобы, ис-

ходя из заданно о описания элементов и непосредственных свя-

зей межд ними, полчить залючение о стртрных свойствах

системы и ее основных подсистем. Применительно  автомати-

зированным системам использется три ровня их описания:

— наличие связей;

— наличие и направление связей;

— наличие и направление связей и вид и направление движе-

ния си налов, оторые определяются взаимодействием эле-

ментов.

116

На первом ровне, о да исходят лишь из наличия или от-

стствия связей, изчаемой системе может быть поставлен в со-

ответствие неориентированный раф, вершины оторо о отобра-

жают элементы системы, а ребра — сществющие межд эле-

ментами связи.

Основные задачи, решаемые на этом ровне:

— определение связности (целостности) системы. Если сис-

тема оазывается несвязной, то ставят задач выделения

изолированных связных подсистем со списами входящих

в них элементов;

— выделение цилов;

— определение минимальных и масимальных последова-

тельностей элементов (цепей), разделяющих элементы

др от др а.

На втором ровне, о да задано направление связей, изчае-

мой системе соответствет ориентированный раф, направление

д оторо о совпадает с направлением связей.

Резльтаты стртрно о анализа на этом ровне оазывают-

ся более содержательными. К задачам анализа на этом ровне

относят:

— определение связности (целостности) системы;

— тополо ичесая деомпозиция системы с выделением

сильно связанных подсистем;

— нахождение входных и выходных полюсов системы и в со-

ответствии с этим выделение пнтов приема и выдачи ин-

формации;

— выделение ровней в системе и определение их взаимо-

связей;

— определение масимальных и минимальных птей;

— определение харатеристи тополо ичесой значимости

элементов;

— полчение информации о слабых местах в стртре.

На третьем ровне описания связей не тольо читывается

наличие и направление связей, но и расрывается состав и ха-

ратер си налов взаимодействия элементов. Система отобража-

ется с помощью специально вводимых схем или моделей сопря-

жения.

Основные задачи на этом ровне:

— определение харатера си налов (входные, выходные, п-

равляющие и т.п.);

— построение моделей фнционирования элементов систе-

мы и самой системы.

117

4.3. Формализация описания стртры

методами теории рафов

Принцип представления стртры в виде рафа чрезвычайно

прост. Чаще все о элементам системы ставят в соответствие вер-

шины рафа, а связям — ребра.

Рассмотрим неоторые основные определения, непосредс-

твенно связанные с задачами стртрно о анализа АСУ.

4.3.1. Способы формализованноо задания рафа

А. Графичесое представление.

Это наиболее на лядный способ представления отношений

межд элементами, е о недостато — относительная сложность

использования ЭВМ для анализа.

Б. Матричное представление.

Матрица смежности вершин для неориентированно о рафа

имеет вид:

A = ||a

||, i, j = ,

де n — число вершин рафа,

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

A = ||a

||, i, j = ,

задается следющим образом:

Матрица инциденций

B = ||b

||, i = , j = ,

де n — число вершин, m — число ребер, определяется следю-

щим образом:

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

1 n,

1, если сществет связь межд i и j вершинами;

0, в противном слчае.

1 n,

1, если из вершины i можно перейти в вершин j;

0, в противном слчае.

1 n,

1 m,

1, если i-тая вершина инцидентна j-том ребр

0, в противном слчае.

116

На первом ровне, о да исходят лишь из наличия или от-

стствия связей, изчаемой системе может быть поставлен в со-

ответствие неориентированный раф, вершины оторо о отобра-

жают элементы системы, а ребра — сществющие межд эле-

ментами связи.

Основные задачи, решаемые на этом ровне:

— определение связности (целостности) системы. Если сис-

тема оазывается несвязной, то ставят задач выделения

изолированных связных подсистем со списами входящих

в них элементов;

— выделение цилов;

— определение минимальных и масимальных последова-

тельностей элементов (цепей), разделяющих элементы

др от др а.

На втором ровне, о да задано направление связей, изчае-

мой системе соответствет ориентированный раф, направление

д оторо о совпадает с направлением связей.

Резльтаты стртрно о анализа на этом ровне оазывают-

ся более содержательными. К задачам анализа на этом ровне

относят:

— определение связности (целостности) системы;

— тополо ичесая деомпозиция системы с выделением

сильно связанных подсистем;

— нахождение входных и выходных полюсов системы и в со-

ответствии с этим выделение пнтов приема и выдачи ин-

формации;

— выделение ровней в системе и определение их взаимо-

связей;

— определение масимальных и минимальных птей;

— определение харатеристи тополо ичесой значимости

элементов;

— полчение информации о слабых местах в стртре.

На третьем ровне описания связей не тольо читывается

наличие и направление связей, но и расрывается состав и ха-

ратер си налов взаимодействия элементов. Система отобража-

ется с помощью специально вводимых схем или моделей сопря-

жения.

Основные задачи на этом ровне:

— определение харатера си налов (входные, выходные, п-

равляющие и т.п.);

— построение моделей фнционирования элементов систе-

мы и самой системы.

117

4.3. Формализация описания стртры

методами теории рафов

Принцип представления стртры в виде рафа чрезвычайно

прост. Чаще все о элементам системы ставят в соответствие вер-

шины рафа, а связям — ребра.

Рассмотрим неоторые основные определения, непосредс-

твенно связанные с задачами стртрно о анализа АСУ.

4.3.1. Способы формализованноо задания рафа

А. Графичесое представление.

Это наиболее на лядный способ представления отношений

межд элементами, е о недостато — относительная сложность

использования ЭВМ для анализа.

Б. Матричное представление.

Матрица смежности вершин для неориентированно о рафа

имеет вид:

A = ||a

||, i, j = ,

де n — число вершин рафа,

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

A = ||a

||, i, j = ,

задается следющим образом:

Матрица инциденций

B = ||b

||, i = , j = ,

де n — число вершин, m — число ребер, определяется следю-

щим образом:

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

1 n,

1, если сществет связь межд i и j вершинами;

0, в противном слчае.

1 n,

1, если из вершины i можно перейти в вершин j;

0, в противном слчае.

1 n,

1 m,

1, если i-тая вершина инцидентна j-том ребр

0, в противном слчае.

118

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

Рис. 4.1. иллюстрирет это положение.

В. Множественное представление.

В этом слчае для ориентированно о рафа G(V ) задается мно-

жество вершин V и соответствие G, оторое поазывает, а свя-

заны межд собой вершины. Для аждой вершины i соответствие

G определяет множество вершин G(i), в оторые можно непос-

редственно попасть из вершины i. Это множество называется

множеством правых инциденций.

Множество G

-1

(i) определяет все вершины, из оторых можно

непосредственно попасть в вершин i. Это множество называется

множеством левых инциденций.

Таим образом, ориентированный раф задается перечисле-

нием (списом) множеств вида G(i), либо множеств вида G

-1

(i)для

всех вершин рафа. Таой способ оазывается наиболее омпа-

тным и эффетивным при задании исходной информации о

стртре для решения задач синтеза, особенно для иерархичес-

их стртр.

Пример. Псть стртра системы имеет вид, поазанный

на рис. 4.2. Необходимо представить ее рассмотренными спо-

собами.

Строим раф системы (рис. 4.3), матрицы смежности

(табл. 4.1) и инциденций (табл. 4.2).

Множественное задание стртры: G(1) = (2,3), G(2) = 0,

G(3) = (5,4), G(4) = (2), G(5) = (1,2). Или G

-1

(1) = (5), G

-1

(2) =

= (1, 5, 4), G

-1

(3) = (1), G

-1

(4) = (3), G

-1

(5) = (3).

Таблица 4.1 Таблица 4.2

12345 1234567

101100 111-10000

200000 2-100-1-100

300011 30-100011

401000 4000010-1

511000 500110-10

1, если i-тая вершина — начало j-тоо ребра;

–1, если i-тая вершина — онец j-тоо ребра;

0, если i-тая вершина не инцидентна j-том ребр.

119

Определение цепи, пти, цила, онтра. Цепью называется та-

ая последовательность ребер E

, E

, …, E

k-1

, E

, о да аждое

ребро E

k-1

соприасается одним из онцов с ребром E

. Цепь

можно обозначить последовательностью вершин, оторые она

содержит. Например, для рафа, представленно о на рис. 4.4, це-

пью бдет (1, 4, 3, 5) или (1, 3, 4) (рис. 4.5).

Понятие цепи обычно использется для

неориентированных рафов.

Птем называется таая последователь-

ность д , о да онец аждой предыдщей

д и совпадает с началом последющей.

Например, для рафа (рис. 4.3) последова-

тельность д (1, 3), (3, 4), (4, 2) является

птем (рис. 4.6). Понятие пти обычно ис-

пользется для ориентированных рафов.

Цилом называется таая онечная цепь, оторая начинается

и заанчивается в одной вершине. Например, на рис. 4.5 цепь

(1, 4, 3) является цилом. Понятие цила имеет смысл тольо для

неориентированных рафов.

+1–1

Ý2

Ý4

Ý1

Ý5

Ý3

Рис. 4.1. Правило

построения b

Рис. 4.2. Стртра

системы

Рис. 4.3. Граф системы

èëè

Рис. 4.4. Вид ,рафа Рис. 4.5. Вид цепи

1 3

Рис. 4.6. Вид пти

118

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

Рис. 4.1. иллюстрирет это положение.

В. Множественное представление.

В этом слчае для ориентированно о рафа G(V ) задается мно-

жество вершин V и соответствие G, оторое поазывает, а свя-

заны межд собой вершины. Для аждой вершины i соответствие

G определяет множество вершин G(i), в оторые можно непос-

редственно попасть из вершины i. Это множество называется

множеством правых инциденций.

Множество G

-1

(i) определяет все вершины, из оторых можно

непосредственно попасть в вершин i. Это множество называется

множеством левых инциденций.

Таим образом, ориентированный раф задается перечисле-

нием (списом) множеств вида G(i), либо множеств вида G

-1

(i)для

всех вершин рафа. Таой способ оазывается наиболее омпа-

тным и эффетивным при задании исходной информации о

стртре для решения задач синтеза, особенно для иерархичес-

их стртр.

Пример. Псть стртра системы имеет вид, поазанный

на рис. 4.2. Необходимо представить ее рассмотренными спо-

собами.

Строим раф системы (рис. 4.3), матрицы смежности

(табл. 4.1) и инциденций (табл. 4.2).

Множественное задание стртры: G(1) = (2,3), G(2) = 0,

G(3) = (5,4), G(4) = (2), G(5) = (1,2). Или G

-1

(1) = (5), G

-1

(2) =

= (1, 5, 4), G

-1

(3) = (1), G

-1

(4) = (3), G

-1

(5) = (3).

Таблица 4.1 Таблица 4.2

12345 1234567

101100 111-10000

200000 2-100-1-100

300011 30-100011

401000 4000010-1

511000 500110-10

1, если i-тая вершина — начало j-тоо ребра;

–1, если i-тая вершина — онец j-тоо ребра;

0, если i-тая вершина не инцидентна j-том ребр.

119

Определение цепи, пти, цила, онтра. Цепью называется та-

ая последовательность ребер E

, E

, …, E

k-1

, E

, о да аждое

ребро E

k-1

соприасается одним из онцов с ребром E

. Цепь

можно обозначить последовательностью вершин, оторые она

содержит. Например, для рафа, представленно о на рис. 4.4, це-

пью бдет (1, 4, 3, 5) или (1, 3, 4) (рис. 4.5).

Понятие цепи обычно использется для

неориентированных рафов.

Птем называется таая последователь-

ность д , о да онец аждой предыдщей

д и совпадает с началом последющей.

Например, для рафа (рис. 4.3) последова-

тельность д (1, 3), (3, 4), (4, 2) является

птем (рис. 4.6). Понятие пти обычно ис-

пользется для ориентированных рафов.

Цилом называется таая онечная цепь, оторая начинается

и заанчивается в одной вершине. Например, на рис. 4.5 цепь

(1, 4, 3) является цилом. Понятие цила имеет смысл тольо для

неориентированных рафов.

+1–1

Ý2

Ý4

Ý1

Ý5

Ý3

Рис. 4.1. Правило

построения b

Рис. 4.2. Стртра

системы

Рис. 4.3. Граф системы

èëè

Рис. 4.4. Вид ,рафа Рис. 4.5. Вид цепи

1 3

Рис. 4.6. Вид пти

120

Контром называется таой онечный

пть,  оторо о начальная вершина первой д-

и совпадает с онечной вершиной последней

д и. Например, для рафа (рис. 4.3) последо-

вательность д (1, 3), (3, 5), (5, 1) есть онтр

(рис. 4.7).

Длиной цепи (пти) называют число ребер (д ),

входящих в цепь (пть) рафа.

Матрица смежности вершин рафа А является матрицей не-

посредственных птей рафа, имеющих длин, равню единице.

Общее число транзитных птей длиной λ может быть полчено в

резльтате возведения в λ-тю степень матрицы А:

= A

λ–1

Элемент матрицы A

(λ) определяет число птей длиной λ

от вершины i  вершине j.

На рис. 4.8 приведен пример определения элементов матрицы.

Степень вершины. Число ребер, инцидентных вершине i не-

ориентированно о рафа, называют степенью вершины i и обозна-

чают ρ(i).

Для рафа, представленно о на рис. 4.4:

ρ(1) = 4; ρ(2) = 1; ρ(3) = 3; ρ(4) = 2; ρ(5) = 2. ρ(i) = 12.

Или в общем виде 0,5 = m, де n — число вершин, m —

число ребер рафа.

1 3

Рис. 4.7.

Вид онтра

i j

λ = 1, a

= 1

λ = 2, a

= 1

λ = 2, a

= 2

λ = 3, a

= 2

Рис. 4.8. Пример элементов матрицы А

i 1=

∑

i 1=

∑

121

Число д ориентированно о рафа, оторые имеют началь-

ной вершиной вершин i, называют полстепенью исхода верши-

ны i и обозначают через ρ

(i). Анало ично, число д , оторые

имеют своей онечной вершиной вершин j, называют полсте-

пенью захода вершины j и обозначают через ρ

–

(j). Для рафа,

представленно о на рис. 4.3:

(1) = 2; ρ

(2) = 0; ρ

(3) = 2; ρ

(4) = 1; ρ

(5) = 2; ρ

(i) = 7.

–

(1) = 1; ρ

–

(2) = 3; ρ

–

(3) = 1; ρ

–

(4) = 1; ρ

–

(5) = 1; ρ

–

(j) = 7.

Или в общем виде ρ

(i) = ρ

–

(j), де m — число д ра-

фа, n — число вершин рафа.

К понятию связности рафа. Для неориентированных ра-

фов вводится понятие слабой связности или просто связности.

Граф G (V) называется слабо связным (связным), если для

любых вершин рафа i и j сществет цепь из вершины i в вер-

шин j.

Для ориентированных рафов вводится дополнительное по-

нятие сильной связности. Граф G(V) называется сильно связным,

если для любых вершин рафа i, j сществет пть из вершины i

ввершин j.

Граф на рис. 4.4 является слабо связным. На рис. 4.9 представ-

лен сильно связный раф, на рис. 4.10 — несвязный, распадаю-

щийся на два сильно связных под рафа.

i 1=

∑

j 1=

∑

i 1=

∑

j 1=

∑

1 3

Рис. 4.10. Вид несвязно,о

,рафа, распадающе,ося на

два сильно связных под,рафа

Рис. 4.9. Вид сильно

связно,о ,рафа