графов теория

ГРАФОВ ТЕОРИЯ в химии

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

Некоторые основные понятия. Граф-совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединенных линиями (рис. 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 = (m³ + m)/6, где т — число вершин, отвечающих атомам С, коррелирует с мол. объемами и рефракциями, энтальпиями образования, вязкостью, поверхностным натяжением, хроматографич. константами соед., октановыми числами углеводородов и даже физиол. активностью лек. препаратов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_{В. В. Кафаров, В. П. Мешалкин}