Элементы теории графов

Математической основой СПУ является теория графов. Граф — это множество элементов двух видов — вершин и ребер две вершины соединяются ребром, и каждое ребро, имеющее направление от одной вершины к другой, называется путем. Таким образом, при сетевом планировании математическая зависимость явления (событий) от определяющих параметров (работ) выражается не в виде математического соотношения, а в виде геометрической фигуры — графа. [c.18]

Расчет элементов / -формы и передаточных функций аппаратов производится методами теории графов (формула. Мезона) или теории матриц, которые в данной работе подробно не рассматриваются. [c.77]

Элементы теории графов [c.285]

Графо-логическое описание процедур отыскания оптимального решения в виде блок-схем осуществления всех возможных исходов в поведении управляемой системы широко применяется в современной практике проектирования автоматизированного управления технологическими процессами и предприятиями. Разработка блок-схем решения логических задач дает возможность наиболее полного соблюдения всех условий оптимальности и варьирования элементов формальной и диалектической логики. В основе графо-логического обоснования блок-схем решения задач лежат положения теории графов и ее важнейшего раздела — сетевого планирования и управления. Механизм построения блок-схем достаточно отработан и основан на принятых в международном масштабе условных обозначениях, характеризующих отдельные процедуры логико-вычислительных операций по технологии обработки информации, например ввод и вывод данных, пропуск их через ЭВМ на печать и т. д. Кроме того, блок-схемы отражают последовательность и направленность информационных потоков, а также их взаимосвязи между собой. [c.153]

Топологический принцип формализации процедур системного анализа, положенный в основу развиваемого в книге подхода, существенно базируется на математическом аппарате теории графов, который, как показала практика системных исследований, оказался весьма эффективным как на уровне больших ХТС [6, 7], так и на уровне электрических, электромеханических и отдельных видов термодинамических систем [15, 45, 46]. В последнем случае особенно удобным является язык диаграмм связи, в основе которого лежит понятие диссипации энергии [3, 4, 45, 46]. Из дальнейшего изложения будет видно, что специфика объектов химической технологии как ФХС оказывает существенное влияние на рабочий математический аппарат диаграмм связи вводятся новые элементы, процедуры и понятия обосновываются специфические диаграммные фрагменты типичных подсистем ФХС определяются новые типы структур слияния, отражающие характер совмещения потоков субстанций в локальной точке пространства вводятся новые понятия локальных и глобальных диаграмм связи и т. п. Поэтому предлагаемую монографию следует рассматривать как новую методологию анализа специфических объектов — ФХС на основе их структурного (топологического) представления. [c.15]

Топологические матрицы графов несут в себе полную информацию о глобальной и локальной структурах графа так же, как и его изображение на рисунке. Наиболее часто в теории графов используются матрицы смежности А и инциденции В и несколько реже — матрица Кирхгофа, которая получается из матрицы — А заменой -го элемента главной диагонали на степень -й вершины. Ее также можно получить, если расставить произвольным образом ориентацию ребер графа и перемножить матрицу инциденций В получившегося орграфа на транспонированную к ней матрицу В . [c.176]

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

Топологию ХТС будем рассматривать в терминах теории графов (см. главу II). Тогда технологическая схема будет представлять собой потоковый граф С, вершинами которого будут элементы ХТС, а дугами — связи между элементами. [c.76]

II этап. Систематизированный или упорядоченный поиск неисправной цепи можно вести по специально разработанным логическим схемам, составляемым на основании теории графов, или древообразным схемам, раскрывающим наглядную связь между отдельными цепями, или специальным картам поиска неисправностей (рис. 124). Хорошо прослеживаемая взаимосвязь между элементами электрического оборудования с хорошей наглядностью позволяет установить границы неисправной цепи. Например, при пуске дизеля не включаются контакторы Д1, Д2 я ДЗ, а контактор КМН получает питание (включается). Точкой разветвления указанных цепей питания и, следовательно, началом неисправной цепи является место включения провода 283 к замыкающей блокировке замедленного действия РВ1. Наличие параллельных цепей в схеме питания электрических аппаратов дает возможность сократить длину отказавшей цепи. Если при выключенной кнопке Топливный насос и включенной Пуск дизеля контакторы Д1—ДЗ включаются — неисправная цепь где-то от блокировки РВ1 до провода 326. Искусственным включением замыкающей блокировки Д1 в цепи катушки контактора ДЗ в этой же проверяемой цепи можно дополнительно локализовать [c.250]

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

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

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

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

Применение приведенных теорем можно проиллюстрировать на примере графов, изображенных на рис. 1У-4, а, б. Так, легко убедиться, что определитель третьего порядка, записанный для элементов 1, 2, 6 (см. рис. 1У-4, а), равен нулю [c.125]

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

При подходе, основанном на теории информации, соответствующее множество А из п элементов, полученное из молекулярного графа, разбивается на h непересекающихся подмножеств А мощности (/ = 1, 2,. .., Л п- — п) с помощью соотнощения эквивалентно- [c.211]

В заключение можно отметить, что, так как матрицы четности смежности (в отличие от таких матриц для хюккелевских графов) содержат отрицательные элементы, их собственные значения и собственные векторы, вообще говоря, не обнаруживают известных характеристик, предсказываемых теорией Перрона — Фробениуса для неотрицательных матриц [16], хотя, конечно, поскольку матрица M(G) [= А (G )] вещественна и симметрична, все значения х, при которых Pq(x) обращается в нуль, вещественны. Одно из следствий неприменимости теоремы Перрона — Фробениуса состо- [c.319]

СИЛЬНОЙ компоненте. Можно показать, что направленный граф — сильно связный, если и только если существует замкнутая направленная цепь ребер, содержащая все имеющиеся в графе ребра [2]. Поскольку объединение (как это понимается в теории множеств) направленной цепи из верщины К- в Уу и направленной цепи из верщины VJ в К, является направленным циклом, каждый сильно связный граф содержит по крайней мере один направленный цикл, и соответствующая матрица циклов содержит по меньшей мере одну строку, в которой все отличные от нуля элементы имеют одинаковый знак. [c.329]

При расчете используют специальный формализованный метод составления расчетных уравнений, пригодный для схем любой конфигурации. Он основан на аналитическом представлении схемы сети с помощью элементов теории графов и алгебры матриц. Нелинейность нагрузок приводят к необходимости пересчетов (итераций), направленных на получение роиения требуемой степени точности. [c.142]

В книге рассмотрены основные принципы моделирования, анализа и синтеза сложных химико-технологических систем (ХТС). Приведены методы расчета материальноэнергетических балансов и степеней свободы ХТС описаны математические модели технологических операторов (элементов систем), изложены основы матричного, детерминант-ного и топологического методов анализа ХТС. На основе использования топологических моделей (теории графов) ХТС рассмотрены методы разработки оптимальной стратегии (алгоритмов) исследования и декомпозиционные принципы оптимизации ХТС. Даны методы построения специальных программ математического моделпровапия ХТС на ЦВМ. [c.4]

В различных областях науки и техники для описания поведения физических и инженерных систем находят широкое применение прикладные методы комбинаторной топологии и теории структурных графов. Сюда относятся анализ и синтез ХТС, развиваемые на основе общей теории графов [1, 2], решение задач линейного программирования [3], графические методы синтеза логических автоматов [4], построение коммуникационных сетей [5], диаграммные методы в квантовой теории поля [6], метод графов в химической кинетике [7], диакоптика [8], метод конечных элементов [9, 10], математические методы исследования сложных физических систем [11] и т. п. [c.18]

Хилшя одной из первых смогла во(т1Щнйть содержательные идеи теории графов. ХимИки,- по-видимо у у,.. но. предложению Крум-Брауна, начали рисовать символы элеиедтов внутри кружка, а связи между элементами изображать отрезками прямых, соединяющих этп кружки. Молекула химического вещества стала представляться графом с вершинами — атомами и ребрами — связями. Так был создан классический язык структурной химии, столь привычный и естественный в настоящее время. Возможность формализации на его основе химических объектов (молекул) с помощью математических объектов (графов) позволяет использовать методы теории графов для определения числа различных изомеров. Это обстоятельство позволило блестящему английскому математику Кэли еще в 1874 г. решить классическую задачу структурной химии о иере-числении изомеров углеводородов, что является первым известным примером ирименения математических методов к исследованию изомерии. В химической кинетике также неявно использовался [c.3]

В серии статей, опубликованных ггримерно за 12 лет, Р. Кинг [19—24] для классификации многих комплексов элементов главных подгрупп и переходных металлов использовал теорию групп, теорию графов и топологию. Кроме того, им были составлены чрезвычайно полезные таблицы полиэдров высокой симметрии, имеющих 01 4 до 16 вершин эти таблицы содержат также перечень степеней вершин у., число и тип граней (треугольные или четырехугольные) и точечную группу. Таким образом, построить соответствующий полиэдр несложно. [c.154]

Полимеры распространены повсеместно, имеют многочисленные применения в промышленности и играют значительную роль в повседневной жизни. Полимерная молекула состоит из множества связанных вместе мономерных звеньев 10—10 звеньев в случае обычных линейных цепей и даже больше в случае разветвленных или сетчатых полимеров. В качестве первого шага при изучении физических свойств полимеров возможны простые модели, основанные на теории графов. Между элементами этих простейших теоретикографовых моделей и химической реальностью имеется следующее соответствие [c.481]

Книга Г. Кёнига и В. Блекуэлла Теория электромеханических систем [86] посвящена объединению в целях теоретического анализа и синтеза весьма различных по своим свойствам и назначению элементов (электрические машины, электронные, магнитные и другие усилители, гидропреобразователи, гироскопы) , которое авторы основьшают не на применении известного метода аналогий, а на использовании одной из ветвей топологии - теории графов . Речь идет о стремлении выявить глубокую общность в математическом описании элементов различной физической природы , чтобы обеспечить применение строгих методов и их обоснованное упрощение. [c.10]

У = / / = 1,. .., т), состоящего из подмножеств (потребителей Л, источников У2 и простых точек разветвления на схеме 7з) множества вег-вей I = I / = 1,. .., и), отображающих заданные попарные связи (соединения) между узлами множества условных знаков, характеризующих тип и специфические особенности элементов. С точки зрения теории графов схема г. ц. - конечный цриентированных граф (орграф), дополненный специальными поясняющими знаками, если это требуется. Числа т и п называются параметрами г. ц. [c.15]

С другой стороны, состав промежуточных веществ должен позволять сводить баланс элементов (включая и символ поверхности) в каждой стадии. Поэтому составы промежуточных соединений могут отличаться между собой на состав одного из участников реакции, либо на состав другого промежуточного вещества, либо на их комбинацию. Возможно, что выбор нромежуточных соединений и уравнений стадий удастся осуществить на машине путем целенаправленного перебора. В данном случае надо учитывать, что число участников для одного маршрута обычно составляет три, четыре, редко пять веществ, а число стадий и промежуточных соединений — два — четыре, но может, конечно, быть и больше. Поэтому перебор будет ограниченным. В результате получается несколько вариантов наборов стадий для каждого маршрута. Если такие наборы конструируются ЭВМ, исследователь должен отобрать химически оправданные варианты, Метод алгоритмического построения линейных механизмов на основе теории графов предложен в работе [30]. [c.50]

Другой подход заключается в том, чтобы считать математическую модель механизма реакции некоторой сложной системой, элементы нижнего уровня которой есть математические модели элементарных стадий (либо еще более простые вычислительные операции), а элементом верхнего уровня является сама математическая модель механизма [139]. Такой подход дает возможность использовать для обработки данных о структуре аппарат теории графов. При этом удается информацию о структуре механизма перерабатывать только один раз в ПП, что позволяет строить более экономные подпрограммы расчета скоростей реакций, чем в предыдущем случае. ПП получаются более сложными, а СПРФ — более простой, чем при матричном подходе. [c.194]

Физическая модель электронного отроения молекул, какие бы гипотетические элементы ока ни заключала в себе, получает в квантовой химии математическое описание и дальнейшее изучение модели уже проводится математическими методами. Здесь нет возможности п необходимости касаться истории привлечения для теоретической работы различных математических методов (вариационного исчисления Уангом в 1928 г., теории групп Ван Флеком и Малликеном в начале 30-х годов, теории графов в 60-х годах и т. д.), но по-настоящему революционизирующее влияние на развитие квантовой химии оказало появление новой вычислительной техники. [c.93]

В основе классификации полимерных систем может лежать состав, методы получения, структура, области применения [7]. Согласно [8] все известные полимеры могут быть разделены так, как это сделано на схеме 1. На представлениях о строении полимерных цепей построен еще один вариант классификации (схема 2) [9]. Сперлинг применил для этой цели топологический подход с использованием теории графов (схема 3) [10]. Известна также классификация многокомпонентных полимерных систем, построенная с использованием понятий теории групп. Высказано предположение, что можно получить новые морфологические и топологические типы смесей, проводя так называемые обратные реакции [10]. Например, деструкция привитого сополимера или сетчатых структур может дать новые полимерные системы. Не исключается и возможность создания новых классификаций. Так, недавно предложена классификация многокомпонентных полимерных систем, в основе которой лежат элементы, представляющие определенные типы полимерных систем (гомо-и сополимеры, полимерные сетки и смеси) [11]. Более сложные системы составляют из данных элементов путем их соединения посредством бинарных операций, таких, как сополимеризация, сшивание, смешение, образование взаимопроникающих сеток (ВИС) и т. д. Такая классификация позволяет описать не только состав и метод получения полимерной системы, но и ее простран [c.5]

Ставя перед собой задачу оптимизации схем хроматографического разделения многокомпонентных проб, в частности, содержащих смесь Со, Са и ТЬ, исследователи провели следующую процедуру с применением теории графов. Если изобразить всевозможные ситуации на пути разделения ионов как вершины графа, а способы достижения этих ситуаций как ребра графа, то результирующий граф будет иметь вид, представленный на рис. 9. Здесь символ обозначает произошедшее разделение. Например, АЦВС читается, как вымывание из адсорбента двух ионов ВС вместе ион А останется в колонке и вымывается отдельно А В С — элементы окончательно разделены и выделены. Для того чтобы [c.49]

Элементы сингулярной звезды выведены и описаны ранее при триангуляции диаграммы состава — четырехмерного девятивершинника — с применением теории графов (раздел П.4). [c.224]

Выше в связи с описанием математических подробностей хюккелевой теории сопряженных молекул мы уже отмечали, что ее наиболее обш,ие, сильные и красивые результаты получаются при П0М0Ш.И математической теории графов [5]. Здесь мы ознакомимся с некоторыми сторонами обш,ей теории альтернантных углеводородов, развитой в основном в работах Коулсона и Лонге-Хиггинса [9]. Суш,ественно то, что некоторые важные результаты этих работ сохраняют силу и вне рамок использованных авторами приближений (отбрасывание интегралов перекрытия и требование постоянства всех матричных элементов взаимодействия). Излагаемая ниже теория очень красива. Ознакомление с ней может доставить подлинное эстетическое наслаждение. [c.360]

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

В настоящее время одним из важных вопросов теории химических графов является разработка теоретико-информащтонных инвариантов графа [19]. Множество соответствующих элементов, полученных из молекулярного графа, разбивается на основе соотнощения эквивалентности на непересекающиеся подмножества, и для расчета информационного содержания структуры используется формула Шеннона [20] . Информационное содержание графа может рассматриваться как количественная мера его структурной неоднородности или же разнообразия. Например, из двух графов и [c.209]

Группа С транзитивна на П, если для всех а, 0 е и существует g е С, такое, что ag = 3. Если это так, то в этом случае теорема об орбитальном стабилизаторе утверждает, что 101 = I ОI /1 I, где — стабилизатор в С точки а е 12, такой, что состоит из всех g е С, фиксирующих положение а. В более общем случае С может быть нетранзитивным на О, и тогда П разбивается на орбиты Ц, т.е. подмножества, на каждое из которых С действует транзитивно, и мы можем применять теорему об орбитальном стабилизаторе для каждой орбиты 12-. Рассмотрим следующие примеры такой ситуации. Пусть N = (1, 2,. .., я). Определим граф со множеством вершин N как просто множество Е ребер на /V, т.е. подмножество Е множества N<2), состоящего из всех 2-подмножеств (подмножеств, содержащих два элемента) N. Например, гомотет-раэдрический граф, вершины которого обозначены, как показано на рис. 1, задается Е = (12, 13, 24, 25, 34, 35, 45), где мы используем у в качестве аббревиатуры для ребра (I, ] е [c.298]

Справочник химика 21

Химия и химическая технология