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

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

Некоторые основные понятия. Граф-совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединенных линиями (рис. 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. Графы реакций: а-двудольный; б-сигнальный ур-ний кинетики; r₁, г₂-р-ции; а₁ -а₆-реагенты; k-константы скорости р-цнй; s-комплексния переменная преобразования Лапласа.

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

Рис. 4. Одноконтурная химико-технологическая система и соответствующие графы: а-структурная схема; б, в-материальные потоковые графы соотв. по общим массовым расходам и расходу компонента А; г- тепловой потоковый граф; д-фрагмент системы ур-ний (f₁ - 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. В. В. Кафаров, В. П. Мешалкин.