химический каталог




ГРАФОВ ТЕОРИЯ

Автор Химическая энциклопедия г.р. И.Л.Кнунянц

ГРАФОВ ТЕОРИЯ в химии, область конечной математики, изучающая дискретные структуры, называют графами; применяется для решения различных теоретич. и прикладных задач.

Некоторые основные понятия. Граф-совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединенных линиями (рис. 1,л). Если на графе линии ориентированы (т.е. стрелками показано направление связи вершин), они называют дугами, или ветвями; если неориентированы,-ребрами. Соотв. граф, содержащий только дуги, называют ориентированным, или орграфом; только ребра-неориентированным; дуги и ребра-смешанным. Граф, имеющий кратные ребра, называют мультиграфом; граф, содержащий только ребра, принадлежащие двум его непересекающимся подмножествам (частям),-двудольным; дуги (ребра) и (или) вершины, к-рым отвечают определенные веса или числовые значения к.-л. параметров,-взвешенным. Путь в графе-чередующаяся последовательность вершин и дуг, в которой ни одна из вершин не повторяется (например, a, b на рис. 1,a); контур-замкнутый путь, в котором первая и последняя вершины совпадают (например,f, h); петля-дуга (ребро), которая начинается и кончается в одной и той же вершине. Цепь графа-последовательность ребер, в которой ни одна из вершин не повторяется (например, с, d, e); цикл-замкнутая цепь, в которой ее начальная и конечная вершины совпадают. Граф называют связным, если любая пара его вершин соединена цепью или путем; в противоположном случае граф называют несвязным.

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

Для решения задач ГРАФОВ ТЕОРИЯ т. и ее приложений графы представляют с помощью матриц (смежности, инцидентности, двустрочных и др.), а также спец. числовых характеристик. Например, в матрице смежности (рис. 1,в) строки и столбцы отвечают номерам вершин графа, а ее элементы принимают значения 0 и 1 (соответственно отсутствие и наличие дуги между данной парой вершин); в матрице инцидентности (рис. 1,г)строки отвечают номерам вершин, столбцы-номерам дуг, а элементы принимают значения 0, + 1 и - 1 (соответственно отсутствие, наличие дуги, входящей в вершину и выходящей из нее). наиболее употребительные числовые характеристики: число вершин (т), число дуг или ребер (n), цикломатич. число, или ранг графа (п — т + k, где k-число связных подграфов в несвязном графе; например, для графа на рис. 1,б ранг будет: 10-6+ 1 =5).

Применение ГРАФОВ ТЕОРИЯ т. базируется на построении и анализе различные классов химических и химико-технологических графов, которые называют также топология, моделями, т.е. моделями, учитывающими только характер связи вершин. Дуги (ребра) и вершины этих графов отображают химический и химический-технол. понятия, явления, процессы или объекты и соответственно качеств. и количественное взаимосвязи либо определенные отношения между ними.

Рис. 1. Иллюстрация некоторых основных понятий: а-смешанный граф; б-осговное дерево (сплошные дуги a, h, d, f, h) и некоторый подграф (пунктирные дуги с, с, д, k, I) орграфа; в, г-матрицы соответственно смежности и инцидентности орграфа.

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

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

Рис. 2. Молекулярные графы и деревья: а, б - мультиграфы соответственно этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).

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

Мол. графы дают возможность сводить задачи, связанные с кодированием, номенклатурой и структурными особенностями (разветвлепность, цикличность и т.п.) молекул различные соединение, к анализу и сопоставлению чисто мат. признаков и свойств мол. графов и их деревьев, а также соответствующих им матриц. Для выявления количественное корреляций между строением молекул и физических-химический (в т.ч. фармакологическими) свойствами соединение разработано более 20 так называемой топологич. индексов молекул (Винера, Балабана, Хосойи, Плата, Рандича и др.), которые определяют с помощью матриц и числовых характеристик мол. деревьев. Например, индекс Винера W = (m3 + m)/6, где т-число вершин, отвечающих атомам С, коррелирует с мол. объемами и рефракциями, энтальпиями образования, вязкостью, поверхностным натяжением, хроматографич. константами соединение, октановыми числами углеводородов и даже физиол. активностью лек. препаратов.

Важными параметрами мол. графов, используемыми для определения таутомерных форм данного вещества и их реакционной способности, а также при классификации аминокислот, нуклеиновых кислот, углеводов и др. сложных природные соединений, являются спедняя и полная (Н)информац. емкости. Параметр вычисляется по формуле энтропии информации Шеннона: , где pt-вероятность принадлежности вершин m графа i-тому виду, или классу эквивалентности, k; i =, Параметр (см. также Энтропия). Изучение мол. структур типа неорганическое кластеров или лент Мёбиуса сводится к установлению изоморфизма соответствующих мол. графов путем их укладки (вложения) в сложные многогранники (например, полиэдры в случае кластеров) или спец. многомерные поверхности (например, римановые). Анализ мол. графов полимеров, вершины которых отвечают мономерным звеньям, а ребра-химический связям между ними, позволяет объяснить, например, эффекты исключенного объема, приводящие к качеств. изменениям прогнозируемых свойств полимеров.

Рис. 3. Графы реакций: а-двудольный; б-сигнальный уравений кинетики; r1, г2-реакции; а16-реагенты; k-константы скорости р-цнй; s-комплексния переменная преобразования Лапласа.

С применением ГРАФОВ ТЕОРИЯ т. и принципов искусственного интеллекта разработано программное обеспечение информационно-поисковых систем в химии, а также автоматизиров. систем идентификации мол. структур и рационального планирования органич. синтеза. Для практическое реализации на ЭВМ операций выбора рациональных путей химический превращений на основе ретросинтетич. (см. Ретросинтетический анализ)и синтонного принципов используют многоуровневые разветвленные графы поиска вариантов решений, вершины которых соответствуют мол. графам реагентов и продуктов, а дуги изображают превращения веществ.

Рис. 4. Одноконтурная химико-технологическая система и соответствующие графы: а-структурная схема; б, в-материальные потоковые графы соответственно по общим массовым расходам и расходу компонента А; г- тепловой потоковый граф; д-фрагмент системы уравений (f1 - f6) материального баланса, полученной из анализа графов на рис. 4, б и в; е-двудольный информационный орграф; ж-информационный граф, I-смеситель; II-реактор; III-ректификационная колонна; IV-холодильник; I1-I8-технол. потоки; q-массовый расход; H-энтальпия потока; i. s и i*, s*- соответственно реальные и фиктивные источники и стоки материальных и тепловых потоков; с-концентрация реагента; V-объем реактора.

Матричные представления мол. графов различные соединений эквивалентны (после преобразования соответствующих элементов матриц) матричным методам квантовой химии. Поэтому ГРАФОВ ТЕОРИЯ т. применяют при выполнении сложных квантово-химический расчетов: для определения числа, свойств и энергий мол. орбиталей, например в комплексных соединение, прогнозирования реакционной способности сопряженных альтернантньгх и неальтернантных полиенов, выявления ароматические и антиароматические свойств веществ и др.

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

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

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

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

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

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

Информационно-пстоковые графы отображают логико-информац. структуру систем уравений мат. моделей ХТС; применяются для составления оптим. алгоритмов расчета этих систем. Двудольный информац. граф (рис. 4, е)неориентированный или ориентированный граф, вершины которого отвечают соответственно уравениям fl -f6 и переменным q1 - V, а ветви отображают их взаимосвязь. Информац. граф (рис. 4, ж) - орграф, изображающий порядок решения уравений; вершины графа отвечают этим уравениям, источникам и приемникам информации ХТС, а ветви-информац. переменным.

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

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

Для создания комплексов программ автоматизир. синтеза оптим. высоконадежных производств (в том числе ресурсосберегающих) наряду с принципами искусств. интеллекта применяют ориентированные семантические, или смысловые, графы вариантов решений ХТС. Эти графы, которые в частном случае являются деревьями, изображают процедуры генерации множества рациональных альтернативных схем ХТС (например, 14 возможных при разделении ректификацией пятиком»понентной смеси целевых продуктов) и процедуры упорядоченного выбора среди них схемы, оптимальной по некоторому критерию эффективности системы (см. Оптимизация). ГРАФОВ ТЕОРИЯ т. используют также для разработки алгоритмов оптимизации временных графиков функционирования оборудования многоассортиментных гибких производств, алгоритмов оптим. размещения аппаратуры и трассировки трубопроводных систем, алгоритмов оптим. управления химико-технол. процессами и производствами, при сетевом планировании их работы и т.д.

Лит.. Зыков А. А., Теория конечных графов, [в. 1], Новосиб., 1969; Яцимирский К. Б., Применение теории графов в химии, Киев, 1973; Кафаров В. В., Перов В. Л., Мешалкин В. П., Принципы математического моделирования химико-технологических систем, М., 1974; Кристофидес Н., Теория графов. Алгоритмический подход, пер. с англ., М., 1978; Кафаров В. В., Перов В. Л., Мешал кин В. П., Математические основы автоматизированного проектирования химических производств, М., 1979; Химические приложения топологии и теории графов, под ред. Р. Кинга, пер. с англ., М., 1987; Chemical Applications of Graph Theory, Balaban A.T. (Ed.), N.Y.-L., 1976. В. В. Кафаров, В. П. Мешалкин.

Химическая энциклопедия. Том 1 >> К списку статей


[каталог]  [статьи]  [доска объявлений]    [обратная связь]

 

 

Реклама
курсы обучения кондицианеров ремонт
декор arco marina b
моноколесо с ручкой или с рулем купить
штендер уличный дешево

Рекомендуемые книги

Введение в химию окружающей среды.

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

Химия и технология редких и рассеянных элементов.

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

 

 



Рейтинг@Mail.ru Rambler's Top100

Copyright © 2001-2012
(07.12.2016)