«Анализ и синтез химико­ технологических систем Допущено Государственным комитетом по народному образованию в качестве учебника для студентов химико-техно.югических специальностей высших учебных заведений М О СКВА Х И М ...»

для абсорбера для холодильника Чтобы выполнить операции эквивалентного преобразования М БС с целью определения [/?*] ХТС в целом, исходную М БС можно представить в упорядоченной форме, которая позволяет легко выделять типовые связи между матричны ми блоками (последовательные, параллельные и обратные). Для рассмотрен­ ной абсорбционно-десорбционной ХТС (см. рис. 3.11, а) упоря­ доченная М БС представлена на рис. 3.12.

3.6. ОСНОВНЫЕ ЭТАПЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

И АНАЛИЗА ДЕЙСТВУЮЩИХ ХТС

Решение разнообразных задач математического моделирования и анализа действующих ХТС методологически осуществляют по следующим шести основным этапам:

Рис. 3.12. У п оряд очен н ая м атри ч н ая блок-схем а аб сорб цион но-десорб ционн ой Х Т С м о н о эта н о л ам и н о в о й очистки синтез-газа 1) постановка задачи-сф орм улировать инженерно-технологическую постановку задач анализа ХТС, которые необходимо решать с использованием вычислительного эксперимента на ММ; определить, с какой точностью требуется получить решение задач математического моделирования и анализа ХТС;

2) изучение физико-химической сущности ХТП, входящих в структуру Х Т С -в ы я в и ть конструкционные и технологические параметры ХТП, оказывающие существенное влияние на себе­ стоимость продукции; собрать данные по материальном у и тепловому балансам, режимам эксплуатации и о функционирова­ нии АСУ ТП. На основе технологической схемы ХТС составить логико-информационную схему, составить приближенные м ате­ матические модели ХТП, если такие модели еще не входят в библиотеку модулей расчета ХТП; эти приближенные модели должны соответствовать реальным технологическим режимам эксплуатации ХТС;

3) разработка математической модели основного варианта технологического режима ХТС и анализ чувствительности Х Т С -с о зд а т ь ММ действующего основного варианта ХТС с единым набором технологических параметров; выявить такие ХТП и параметры, которые оказы ваю т наименьшее влияние на основной вариант режима эксплуатации, а также найти пара­ метры Х ТП, оказывающие наибольшее влияние на переменные, которые представляют интерес с точки зрения целей анализа ХТС;

4) анализ затрат ресурсов на математическое моделирование Х Т С -необходим о сопоставить цели математического м оделиро­ вания и анализа ХТС с наличием имеющегося персонала иссле­ дователей, средств вычислительной техники и времени; проана­ лизировать требуемую точность расчета ХТС, которая может быть достигнута с использованием модулей расчета Х ТП, обла­ дающих наибольшей чувствительностью; в случае необходимос­ ти составить план сбора экспериментальных данных, проводя лабораторные и производственные измерения; решить, насколько общими (в противоположность частным) должны бы ть М М, и установить способ обработки физико-химических параметров, основываясь на этих решениях; разработать более общие модули расчета ХТП и новую логико-информационную схему ХТС с целью более точного описания режимов реальных ХТП и ап­ паратов; разработать алгоритм стратегии анализа ХТС и алго­ ритмы ускорения сходимости численных расчетов СУ м атем ати ­ ческих моделей, с тем чтобы удовлетворялась вся система задан­ ных ограничений и соблю дались материальный и энергетический балансы для всех возможных технологических режимов ХТС;

5) разработка модулей расчета параметров и состояний ХТП;

разработка математической модели ХТС в целом.

6) проведение вычислительного эксперимента на ЭВМ с мате­ матической моделью Х Т С для получения результатов анализа функционирования отдельных технологических блоков, агрега­ тов и узлов с последующим анализом производства (установки) в целом.

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

Необходимо дать предварительную оценку требований, кото­ рые предъявляются к математической модели ХТС: 1) четкое формулирование целей исследования; 2) применение на началь­ ном этапе простых М Р аппаратов, позволяющих установить необходимый уровень точности вычислительного эксперимента;

3) наличие достоверных и (или) необходимых производственных данных; 4) наличие данных о физических и химических свойствах веществ и смесей, перерабатываемых в ХТС.

На этапе изучения ХТП, входящих в структуру ХТС, необхо­ димо при составлении списка параметров ТП выполнить сле­ дующие условия:

1) информация должна соответствовать целям, поставлен­ ным перед моделированием. Иногда полезно предвидеть тре­ бования, которые могут быть предъявлены к ММ в дальнейшем, но список не должен быть излишне подробным. Во многих случаях химические компоненты можно распределять на группы, а этим группам следует приписывать такие средние молекуляр­ ные веса, чтобы сходился М Б. Как правило, компоненты обрат­ ных ТП являю тся наиболее важными, так как они существенно влияю т на эффективность ХТС;

2) список должен включать также химические компоненты, которые непосредственно не влияю т на цели моделирования, но тесно связаны с основными компонентами, перерабатываемыми в ХТС;

3) видоизменение информации о входных ТП может описываться с одинаковой точностью во всех М Р. Состояние знаний об основных явлениях, происходящих в рассматриваемом аппарате, может оказаться недостаточным для описания работы аппарата с требуемой точностью;

4) вы брать рациональные единицы измерения параметров ТП, а в качестве информационных переменных на М Р выбрать те, которые отвечают на поставленные вопросы, являю тся ос­ новными компонентами в обратных ТП и наиболее точно рас­ считываются в МР.

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

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

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

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

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

Исходная Л И Н С должна включать простые и приближенные М Р отдельных элементов ХТС.

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

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

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

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

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

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

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

Разработка М Р для отдельных ХТП подразделяется на сле­ дующие операции: 1) выбор типа модели и формулировка огра­ ничений; 2) запись уравнений с учетом допущений; 3) получение данных, необходимых для решения уравнений; 4) выбор метода численного решения уравнений. Составление программы провер­ ки адекватности созданного М Р реальному ХТП.

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

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

Необходимо выполнить технико-экономическое обоснование реализации указанных рекомендаций на действующем произ­ водстве.

3.7. К О Н Т Р О Л Ь Н Ы Е В О П Р О С Ы И ЗА Д А Н И Я

ДЛЯ С А М О СТО ЯТЕЛ ЬН О Й РА БО ТЫ

В.3-1,. В чем различие пон ятий и н ф орм ац и он н ой перем енной и и н ф о р м ац и о н ­ ного п отока Х ТС?

ческие м одели элем ен тов, п а р ам е тр ы эл ем ен тов и п а р ам е тр ы технологических п оток ов ХТС?

эл ем ен тов Х Т С и степень сво б о д ы Х Т С в целом ?

В.3-4. С ф орм улируй те п он яти я б азисной и вы ходной и н ф о р м ац и о н н о й пере­ м енной С У м атем ати ческой м одел и Х Т С.

онны х перем енны х СУ?

В. 3-6. Ч ем р азл и чаю тся совм естн о р а зо м к н у ты е и совм естн о зам кн у ты е СУ?

В.3-7. К акие м етоды и спользую тся д л я р а зр а б о т к и стратеги и реш ения и н ­ ф орм ац и он н о разреж енны х С У м атем ати чески х м о д ел ей ХТС?

В.3-9. К акие трудн ости в о зн и к аю т при и спользовани и м ет о д а Г аусса д л я реш ения м ногом ерн ы х С Л У с разреж ен н ы м и м атр и ц ам и ?

В.3-11. Н азов и те основны е при знаки классиф икации м одулей р асч ета Т О или ХТП.

В.3-13. Н азо в и те классы м одул ей расчета состояний Т О по признаку о бщ ности назначения, или специализации.

В.3-14. Н азов и те классы м одул ей расч ета Т О по признаку и н ф о р м ац и о н ­ ности.

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

ко и расш иренно ин ф орм ац и он н ы х м одул ей расчета состояний Т О ди ф ф узи он ­ ного разделени я, соответствую щ и х п р о сты м ректиф и каци онны м кол он н ам ?

В.3-17. Д айте определения коэф ф ициента р аздел ен и я входны х п о то к о в и кпд д л я элем ен тов Х Т С.

В.3-20. К акую структурн о-топ ологи ч ескую м о д е л ь Х Т С н еоб х о д и м о и сп ол ь­ зо в а ть дл я определения эквивалентной м ат р и ц ы п реоб разов ан и я Х Т С в целом?

В.3-21. С ф орм ул и руй те основны е п р ав и л а построени я м атр и ч н ы х блок-схем ХТС.

ческого м о д ел и рован и я и ан ал и за действую щ их Х Т С.

В.3-23. К акие основны е операции н еобходи м о вы п ол н и ть при изучении ф изико-хим ической сущ ности Х Т П и технологической схемы Х Т С ?

В.3-24. С ф орм ул и руй те сущ ность основны х операций р а зр аб о тк и м а т е м а т и ­ ческой м одели основн ого вар и ан та технологического реж им а Х Т С и ан ал и за чувствительности Х Т С.

В.3-25. К аким о б р а зо м п оказател и точн ости м одулей расч ета отд ел ьн ы х Т О в л и яю т на оценку точн ости м атем ати ческого м од ел и р о в ан и я Х Т С ?

р ая изображ ен а н а рис. 3.19, а, с учетом п рави л построения М Б С зап и сать м атри ч н ы е уравнения д л я м атри ч н ы х б л ок ов, отоб р аж аю щ и х д есорб ер 2 и т еп л о ­ обм енни к 3.

раздел ен и я и Т О хим ического превращ ен ия, если векторы п а р ам е тр о в их входны х и вы ходны х Т П будут представлены м атр и ц ам и -стр о к ам и. С р авн и те, чем о т л и ­ чаю тся полученны е новы е вы раж ения о т вы раж ен ий (3.42) и (3.45) соответствен н о.

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

3.3-4. Н арисуйте обоб щ енную блок-схем у м етодол оги и реш ения зад ач м а т е ­ м ати ч еского м од ел и р о в ан и я и ан ал и за действую щ их Х Т С, к о т о р а я и злож ена в раздел е 3.6.

колонн ректиф икации, ко то р ая в кл ю чает уравнение А нтуана д л я расч ета д а в л е ­ ния п ар о в чисты х к ом понентов, уравн ен ия Ф енске - А н д е р в у д а -Д ж и л л и л е н д а д л я расч ета м и н и м ал ь н о го и дей стви тельн ого ф л егм ового чисел, а такж е м и н и ­ м ал ь н о го и дей стви тельн ого чисел теоретических тар ел о к РК ; с о с т а в ь т е уравн е­ онн ого М Р С колонн ректиф икации М К С.

3.3-7. Н арисуйте Л И Н С дл я действую щ его узл а ректиф икации, вкл ю чаю щ его п р о сту ю колонну ректиф и каци и, деф л егм ато р -к о н д ен сато р и куб-и сп ари тел ь. Д л я к аж дого эл ем ен та узла ректиф икации используйте м и н и м ал ьн о ин ф орм ац ионны е М РС.

3.3-8. И спользуя м атри ц ы п реобразован ия эл ем ен тов абсорб цион нод есорб цион ной Х Т С (см. рис. 3.11, а): а бсорб ера, теп л ооб м ен н и ка, десорб ера и хол оди л ьн и ка, определите л окальную степень св о б о д ы Х Т С ; составьте р а зв ер ­ нутую л оги ко-и н ф орм ац и он н ую схему данной ХТС.

Глава

П РИ Н Ц И П Ы ПО СТРОЕНИЯ ТО ПОЛО ГИ ЧЕСКИХ

М О Д Е Л Е Й ХТС

4.1. К Л А С С И Ф И К А Ц И Я И Н А З Н А Ч Е Н И Е Т О П О Л О Г И Ч Е С К И Х

М О Д Е Л Е Й Х ТС

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

Эти трудности можно в значительной мере преодолеть, применяя топологические модели (графы) ХТС.

Для решения задач математического моделирования, анализа и оптимизации ХТС применяют четыре класса топологических моделей ХТС: 1) потоковые графы, 2) информационно-потоко­ вые графы, 3) сигнальные графы и 4) структурные графы.

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

П П Г применяют для разработки алгоритм ов оптимальной стратегии расчета ХТС при технологически направленном спо­ собе анализа сложных многоконтурных ХТС (см. разделы 2. и 6.1). М П Г используют для автоматизированного составления систем уравнений материальных балансов ХТС, ТП Г и ЭСП Г применяют для автоматизированного составления систем урав­ нений теплового и эксергетического балансов ХТС (см. разделы 2.6, 2.7 и 5.1).

Информационно-потоковые графы (И П Г) отображ аю т особен­ ности информационной структуры систем уравнений м атем а­ тических моделей ХТС. Выделяют две группы И П Г: двудоль­ ные информационные графы (ДИГ) и информационные графы (ИГ).

Информационно-потоковые графы применяют для разработ­ ки алгоритм ов оптимальной стратегии решения информационно разреженных совместно замкнутых систем уравнений м атем а­ тических моделей ХТС (см. разделы 3.2 и 6.2).

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

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

Тепловые СТГ используют для автоматизированного составле­ ния систем уравнений тепловых процессов функционирования сложных ХТС и для определения матриц преобразования тепло­ вых процессов (см. разделы 3.6 и 3.7).

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

Исходя из теоретико-множественных представлений, граф G(X, Г) задан, если задано непустое множество X = (л^, х 2,..., д:п) и многозначное отображение Г множества X во множество X (рис. 4.1, а). М ногозначное отображение Г - э т о закон, по которому каждому элементу x, е X ставится в соответствие не­ которое подмножество Гх, с X. Элементы множества X изобра­ жаются точками и называю т вершинами графа (F), а отображение Г -о т р е зк а м и (иногда направленными), соединяющими элемент х с элементами подмножества Гд: и называю т ребрами U или дугами U графа.

Нуль-граф - э т о граф, состоящий из изолированных вершин, не соединенных ребрами (дугами) (рис. 4.1,5). Граф G = {X, Г) называется конечным, если число его вершин | Л | конечно. Граф G называется Г-конечным, если для каждой вершины х е Х множество Гх конечно. Некоторый конечный граф, изображен­ ный на рис. 4.1,а, определяется множеством: X = |л:0, х 15 х 2, х ъ, х4, л'5}. Отображение Г характеризуется следующими соотно­ шениями:

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

Направленный граф называется симметрическим, если для любых двух вершин х ( и х} из того, что х, е Г х 7, следует, что х.е Г х,. Если эти условия удовлетворяю тся не для всех пар вершин графа, то граф называется асимметрическим. Д ве верши­ ны графа называю тся смежными, если они определяю т ребро или дугу графа. Каждой неизолированной вершине граф а приX, Рис. 4.1. Различны е граф ы :

а- граф определяем й м еством верш х = { 0, определяем й м еством верш X = {.г,,.х л3.т4} Рис. 4.2. Различны е виды граф ов:

а-ненаправленны или неориентированны б-направленный, или орграф e-смеш й;.’-симметричес­ кий: 0 асим етрический граф надлежит одно или несколько ребер (дуг), которые называю т инцидентными данной вершине. Так, вершине х 1 графа, изобра­ женного на рис. 4.1, в, инцидентны ребра a, d, е\ вершине х 3-р е б р а Ь, с, е.

Две различные дуги (два различных ребра) смежны, если они имею т общую вершину.

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

а путь (л,..т2..V,v, л5,.v,v х ): элем контур (л2, л3 хЛ л«. v v,v..т2); элем б- элементарны контуры ц, = (.v,, х,..v,)= (м,. к2 ц2= (л,. хЛл,) = (м i/J: и = (*V v,. xy) —. uj:

M— 'г л < v v = ((/2-l,y иУпараллельны п ти (i/2 н3 м). (u4 u5 никлы ц, = (.v.v..т3 д,) = (м. м.

м4); = (.V л. л,) = (ц » ц (i/,, м {и м (м м (м. »4) последовательность дуг между лю бой парой вершин графа, в которой конец одной дуги является началом другой дуги.

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

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

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

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

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

Введем понятие независимых циклов графа. Пусть граф G(X, Т) имеет m ребер. К аж дому циклу ц, графа сопоставим m-мерный вектор-цикл: Д = (ц,1, ц,-,..., ц'", придав каждому г-му через ребро ик в направлении его ориентации гк раз, а в противо­ положном направлении sk раз, то координата Ц; = rk — sk. Вектор Д, пространства 'Rn будем называть вектором-циклом, соответст­ вующим /-му циклу ц,. Независимые циклы - э т о такие циклы графа, для которых соответствующие им векторы-циклы линейно независимы.

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

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

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

Двудольный граф - это граф G = (X, Y, Г), множество вершин которого V = X U У состоит из двух непересекающихся подмно­ жеств X n Y = 0, а каждое ребро (дуга) инцидентно вершинам из этих подмножеств, т. е. ребрам (дугам) соответствует много­ значное отображение ГХ с У и ГУ с X (рис. 4.6, а). Двудольный граф также назы ваю т простым или двусторонним графом.

Мультиграф - э т о граф G(V, U), в котором некоторые пары вершин могут быть соединены более чем одним ребром (или кратны ми дугами) (рис. 4.6,6).

ребер (дуг), инцидентных этой i-й вершине.

Т ак, степени верш ин граф а, изображ ен н ого на рис. 4.6, б, соответственно равн ы : p fx j) = р (jcJ = 3; р (х 2) = 5; р(.г3) = 4; p(.v5) = 1.

Рис. 4.5. С вязны й (а) и несвязны й (6) граф ы, деревья Г,, Т 2 (в. г), полны е граф ы Д ля каждой вершины орграфа выделяю т входную степень вершины р'(»), равную числу входных дуг, инцидентных этой /-й вершине, и выходную степень вершины р"(/), которая равна числу выходных дуг, инцидентных этой г-й вершине орграфа.

Д л я орграф а, изображ ен н ого на рис. 4.6,в, степени его верш ин равн ы с о о т ­ ветственно: = р'(.тч) = 1;

Очевидно, что в лю бом орграфе: р ' (/) = р " (/); р (г) = = 1 р '(0 + 1 р "(0Общее число ребер (дуг) е = \Е\ некоторого графа G{V, Ё), Рис. 4.6. Д вудол ьн ы й граф (а)\ к определени ю.степеней верш ин н еори ен ти рован ­ ного (6) и ори ен ти рован н ого (в) граф ов имеющего v = \ V\ вершин, определяется следую щ им соотнош ением: е = 1/2 р (г).

Среди вершин орграфа можно выделить три множества вер­ шин: вершины-источники, для каждой из которых р' (i) = 0 и р" (I ф 0; вершины-стоки, для каждой из которых р" (/1 = 0 и р '(у 1 # 0 ; смешанные вершины, для каждой из которых р (к) ф и р ’(/с) ф 0. Висячая вершина г р а ф а -э т о вершина, которой инци­ дентно одно ребро (дуга), т. е. р (/) = 1.

Граф является топологической, а не геометрической фигурой.

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

Так как граф является топологической фигурой, один и тот же граф может быть геометрически изображен различными спосо­ бами: вершины могут быть расположены в произвольном поряд­ ке, соединяющие их ребра (дуги) могут быть проведены в виде кривых, прямых или ломаных линий. Два графа называю тся изоморфными, если они имеют одинаковое число вешин и одина­ ковое число ребер, если каждой паре вершин, соединенных ребром, в одном графе соответствует такая же пара вершин, соединенных ребром в другом графе. Примеры изоморфных неориентированных графов и G2) и изоморфных орграфов (G3 и G J изображены на рис. 4.7. О бязательным условием изоморфности орграфов является одинаковая ориентация всех их дуг.

Подграф {V ’, Е ) графа G(V, Е)~ это такой граф, множество вершин V которого является подмножеством V \V с V), а м но­