Причем последние 12 лет своей жизни Эйлер тяжело болел, ослеп и, несмотря на тяжелый недуг, продолжал работать и творить. Статистические подсчеты показывают, что Эйлер в среднем делал одно открытие в неделю. Трудно найти математическую проблему, которая не была бы затронута в произведениях Эйлера. Все математики последующих поколений так или иначе учились у Эйлера, и недаром известный французский ученый П.С. Лаплас сказал: "Читайте Эйлера, он – учитель всех нас". Лагранж говорит: "Если вы действительно любите математику, читайте Эйлера; изложение его сочинений отличается удивительною ясностью и точностью". Действительно, изящество вычислений доведено у него до высшей степени. Кондорсе заключил свою речь в академии в память Эйлера следующими словами: "Итак, Эйлер перестал жить и вычислять!" Жить, чтобы вычислять - каким это кажется скучным со стороны! Математика принято представлять себе сухим и глухим ко всему житейскому, к тому, что занимает обыкновенных людей. С именем Эйлера, является задача о трех домиках и трех колодцах.

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

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

Зарождение Теории Графов в 18 в. связано с математическими головоломками, но особенно сильный толчок ее развитию был дан в 19 в. и главным образом в 20 в., когда обнаружились возможности ее практических приложений: для расчета радиоэлектронных схем, решения т.н. транспортных задач и др. С 50-х гг. Теория графов все шире используется в социальной психологии и социологии.

В области Теории Графов следует назвать работы Ф. Харри, Дж. Кемени, К. Фламента, Дж. Снелла, Дж. Френча, Р. Норманна, О. Ойзера, А. Бейвеласа, Р. Вейса и др. В СССР по Т. г. работают Φ. Μ. Бородкин и др.

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

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

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

2) Анализ полученной модели, выделение в ней структурных единиц (подсистем) и изучение их связей. Таким способом могут быть выделены, напр., подсистемы в крупных организациях.

3) Изучение уровней структуры иерархических организаций: количество уровней, количество связей, идущих из одного уровня в другой и от одного лица к другому. На основании этого решаются задачи:

а) количеств. оценки веса (статуса) индивида в иерархической организации. Одним из возможных вариантов определения статуса является формула:

где r (р) - статус некоторого лица р, k - величина уровня субординации, определяемая как наименьшее количество шагов от данного лица к своему подчиненному, nk - количество лиц на данном уровне k. Напр., в организации, представленной след. графом:

вес а=1·2+2·7+3·4=28; 6=1·3+2·3=9 и т.д.

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

Наиболее простой способ дается формулой: r=Σdxy/Σdqx, т.е. частное от деления суммы всех дистанций каждого до всех других на сумму дистанций данного индивида до всех других.

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

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

Задача : Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу. Дорожки не могут проходить через колодцы и домики (рис.1).

Рис. 1. К задаче о домиках и колодцах.

Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году, которая является одной из основных в теории графов. Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

Теорема. Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство

В - Р + Г = 1, (*)

где В - общее число вершин, Р - общее число ребер, Г - число многоугольников (граней).

Доказательство. Докажем, что равенство не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ (рис. 2, а).

а) б)

Действительно, после проведения такой диагонали в новом разбиении будет В вершин, Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно, имеем

В - (Р + 1) + (Г+1) = В – Р + Г.

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

Для этого будем последовательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая:

для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC;

для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN.

В обоих случаях равенство не изменится. Например, в первом случае после удаления треугольника граф будет состоять из В-1 вершин, Р-2 ребер и Г-1 многоугольника:

(В - 1) - (Р + 2) + (Г -1) = В – Р + Г.

Таким образом, удаление одного треугольника не меняет равенства.

Продолжая этот процесс удаления треугольников, в конце концов, мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения В = 3, Р = 3, Г = 1 и, следовательно,

Значит, равенство имеет место и для исходного разбиения, откуда окончательно получаем, что для данного разбиения многоугольника справедливо соотношение.

Заметим, что соотношение Эйлера не зависит от формы многоугольников. Многоугольники можно деформировать, увеличивать, уменьшать или даже искривлять их стороны, лишь бы при этом не происходило разрывов сторон. Соотношение Эйлера при этом не изменится.

Приступим теперь к решению задачи о трех домиках и трех колодцах.

Решение. Предположим, что это можно сделать. Отметим домики точками Д1, Д2, Д3, а колодцы - точками К1, К2, К3 (рис. 1). Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.

Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г= 1.

Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9.

Следовательно, Г = 5. Каждая из пяти граней имеет, по крайней мере, четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше (5 4)/2 = 10, что противоречит условию, по которому их число равно 9.

Полученное противоречие показывает, что ответ в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому коло

Теория Графов в химии

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

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

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

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

Использованная литература :

1.Берж К., Т. г. и ее применение, перевод с французского, М., 1962;

2.Кемени Дж., Снелл Дж., Томпсон Дж., Введение в конечную математику, пер. с англ., 2 изд., М., 1963;

3.Ope О., Графы и их применение, пер. с англ., М., 1965;

4. Белых О. В., Беляев Э. В., Возможности применения Т. г. в социологии, в сб.: Человек и общество, вып. 1, [Л.], 1966;

5. Количественные методы в социологических исследованиях, М., 1966; Беляев Э. В., Проблемы социологических измерения, "ВФ", 1967, No 7; Bavelas. Communication patterns in task oriented groups, в кн. Lerner D., Lass well H., Policy sciences, Stanford, 1951;

6.Кemeny J. G., Snell J., Mathematical models in the social sciences, N. Y., 1962; Filament C., Applications of graph theory to group structure, N. Y., 1963; Оeser Ο. Α., Harаrу F., Role structures and description in terms of graph theory, в кн.: Вiddle В., Thomas E. J., Role theory: concepts and research, N. Y., 1966. Э. Беляев. Ленинград.

Молекулярные графы и типы молекулярных структур

из "Применение теории графов в химии"

Химия относится к тем областям науки, которые плохо поддаются формализации. Поэтому неформальное применение математических методов в химических исследованиях связано в основном с теми направлениями, в которых удается построить содержательные математические модели химических явлений.
Другой путь ироникновення графов в теоретическую химию связан с квантово-химическими методами расчета электронного строения молекул.
В нервом разделе обсуждаются способы анализа молекулярных структур в терминах графов, которые используются затем для по-строепня топологических индексов и иа пх основе корреляции типа структура - свойство, излагаются также элементы молекулярного дизайна.
Как известно, вещество может находиться в твердом, жидком или газообразном состоянии. Стабильность каждой из этих фаз определяется условием минимума свободной энергии и зависит от температуры и давления. Всякое вещество состоит из атомов или ионов, которые нри определенных условиях могут образовывать устойчивые подсистемы. Элементный состав и относительное расположение атомов (ближний порядок) в такой подсистеме сохраняются достаточно до.лго, хотя ее форма и размеры могут меняться. С уменьшением температуры или с увелпчегшем давления происходит уменьшение подвижности этих подсистем, однако движение ядер (нулевые колебания) не прекращаются п при абсолютном нуле температуры. Такие стабильные связные образования, состоящие пз) онечпого числа атолюв, могут существовать в жидкости, в нарах или в твердом веществе и называются молекулярными системами.
МГ в перспективной проекции отражает основные особенно-стп геометрии молекулы и дает наглядное представление об ее структуре. Обсудим в терминах МГ некоторые типы молекулярных структур. Рассмотрим молекулы, для описания структуры которых удобно использовать плоские реализации графов. Простейшим системам такого типа соответствуют древообразные МГ.
В случае молекул этиленового ряда МГ содержат только вершины степени три (углерод) и степени единица (водород). Обгцая формула таких соединений С Н,г+2. Молекулы С Н +2 в основном состоянии обычно являются плоскими. Каждый атом углерода характеризуется тригональным окружением. В данном случае возможно существование изомеров типа цис- и транс-. В случае тг 1 структура изомеров может быть достаточно сложной.
Рассмотрим теперь некоторые молекулярные системы, содержащие циклические фрагменты. Как и в случае углеводородов парафинового ряда, существуют молекулы, структуры которых можно описать в терминах графов, имеющих только вершипы степени четыре и единица. Простейшим примером такой системы является циклогексан (см. рис. 1.3,6), Обычно структуру циклогексапа описывают в виде МГ в перспективном изображении, опуская при этом вершины степени единица. Для циклогексапа возможно существование трех поворотных изомеров (рис, 1.7).

VARIABILITY МНОГООБРАЗИЕ СТРОЕНИЯ OF STRUCTURES AND FORMS И ФОРМ МОЛЕКУЛ OF ORGANIC COMPOUND ОРГАНИЧЕСКИХ СОЕДИНЕНИЙ MOLECULES L. P. OLEKHNOVICH г. и. йгЦпзйЗау кУТЪУ‚ТНЛИ „УТЫ‰‡ ТЪ‚ВММ˚И ЫМЛ‚В ТЛЪВЪ, кУТЪУ‚-М‡-СУМЫ The question of genesis and the variety of the types ЗЗЦСЦзаЦ of mirror configurational isomerism of organic com- Химия углерода – органическая химия – выде- ляется разнообразием строения и чрезвычайной pounds are discussed with многочисленностью индивидуальных соединений the application of some . Общее число известных органических соеди- elements of graph theory. нений (свыше десяти миллионов) ежегодно попол- няется десятками тысяч новых веществ, синтезиру- Briefly the principles of емых в лабораториях. Органическая химия удивляет analysis of molecular многообразием классов молекул, в строении кото- forms (“figures”) on the рых на первый взгляд не видно никакой логики. Ос- новной причиной появления не поддающегося basis of symmetry opera- простому перечислению (>107) множества органи- tions are enlightened. Dif- ческих соединений являются уникальные свойства ferences of achiral and центрального элемента – углерода. chiral compounds are Мир соединений углерода – это неисчерпаемая комбинаторика вариантов и способов построения classified. молекул из n атомов С, m атомов O, k–N, l–S, h–P и т.д. к‡ТТПУЪ ВМ˚ ‚УФ УТ˚ щгЦеЦзнх нЦйкаа ЙкДойЗ Ф УЛТıУК‰ВМЛfl ПМУ„У- З абйЕкДЬЦзаьп ейгЦдмг У· ‡БЛfl ‚Л‰У‚ БВ Н‡О¸- Подобно тому как физики пользуются эконом- МУИ НУМЩЛ„Ы ‡ˆЛУММУИ ным, но емким языком математических формул и ЛБУПВ ЛЛ У „‡МЛ˜ВТНЛı выкладок, химики используют особый язык запи- сей строения соединений. Этот язык тем более не- ТУВ‰ЛМВМЛИ Т Ф Л‚ОВ˜В- обходим в органической химии для упорядочива- МЛВП ˝ОВПВМЪУ‚ ЪВУ ЛЛ ния представлений о многочисленных подклассах „ ‡ЩУ‚. д ‡ЪНУ УТ‚В˘В- гигантского разнообразия молекул. Чтобы тратить меньше времени и места при изображении струк- М˚ Ф ЛМˆЛФ˚ ‡М‡ОЛБ‡ турных формул, химики-органики часто не за- ЩУ П (ЩЛ„Ы) ПУОВНЫО трудняют себя обозначениями атомов. Этот прием М‡ УТМУ‚В Ф В‰ТЪ‡‚ОВ- особенно удобен, когда рассматриваются не ка- кие-либо свойства конкретного соединения, а об- МЛИ У· УФВ ‡ˆЛflı ТЛППВ- щие закономерности строения и формы рядов мо- Ъ ЛЛ, НО‡ТТЛЩЛˆЛ У‚‡- лекул. Так, вместо того чтобы рисовать буквенные М˚ УТУ·ВММУТЪЛ ТЪ УВ- обозначения углеродных и водородных атомов во всех структурных изомерах, например предельно- © йОВıМУ‚Л˜ г.и., 1997 МЛfl ТЛППВЪ Л˜М˚ı Л го углеводорода гексана – С6Н14 , изображаются ‡ТЛППВЪ Л˜М˚ı ТУВ‰ЛМВ- графы (схема 1) МЛИ, ‰‡МУ УФ В‰ВОВМЛВ НЛ ‡О¸МУИ ТЛППВЪ ЛЛ. Схема 1 44 лйкйлйЗлдав йЕкДбйЗДнЦгъзхв ЬмкзДг, ‹2, 1997 Вершины графов (точки) – это атомы углерода, соединений, изображать также сложные превраще- а соединяющие их линии (ребра) – это связи С–С. ния молекул (реакции) и понимать друг друга. Поскольку углерод четырехвалентен, а водород од- Вообще химические графы имеют прямое отно- новалентен, то ясно, что при концевых (свободных) шение к специальной отрасли математики – теории вершинах графа должно быть по три атома Н, при графов . В этой теории граф G порядка n опреде- средних вершинах типа – по два, при третич- ляется как непустое множество вершин V1 , V2 , …, Vn ных вершинах – по одному и не должно быть с множеством (m) парных отношений – ребер, свя- водородных атомов при четвертичных вершинах зывающих различные вершины. Начало теории гра- фов положили знаменитые рассуждения Л. Эйлера. Приведенные выше графы, следовательно, не- (1736) о кёнигсберских мостах, где были сформули- полные, однако они достаточны для представления рованы критерии обхода всех ребер графа без пов- структурных изомеров углеводородов. Ниже приве- торений, а также другие его работы, связанные с ма- дены графы молекул непредельных углеводородов с тематическими головоломками и развлечениями. двойными (С=С) и тройными (С≡С) связями, а так- Важные вехи на пути развития этой теории состави- же графы некоторых циклических и каркасных уг- ли работы Г. Кирхгофа (1847) и В. Гамильтона леводородов (табл. 1). (1859). А. Кэли (1857, 1874–1875) был первым, кто Тригональный граф (схема 2) обобщает пред- использовал графовые представления (перечисле- ставления о фигурах весьма различных молекул. ния графовых “деревьев”) в связи с подсчетом числа изомеров первых членов ряда предельных углеводо- Таким образом, графическая (графовая) форму- родов – алканов. Действительно, только с помощью ла соединения – это экономное представление важ- аппарата теории графов (теорема Пойа, 1937) мож- ных частных и наиболее общих закономерностей его но решать задачи перебора (перечисления) всех строения и формы. Химикам достаточно подобных структурных изомеров молекул СnH2n +2 , CnH2n , графов, чтобы, не пользуясь длинными названиями CnH2n − 2 , CnH2n − 4 и т.д. (см. графы изомеров гексана), Таблица 1 Z,E-изомеры бутена-2 Z E H3C CH CH CH3 .R . R,L-изомеры 1,3-диметил-3-кумулена L . Z. . E. Z,E-изомеры 1,4-диметил-4-кумулена. . . . . . Диметилацетилен 1,4-диметил-биацетилен Ксилолы Бензол Толуол орто- мета- пара- Циклические предельные угледовороды Циклопропан Циклобутан Циклопентан Циклогексан и так далее Каркасные углеводороды Тетраэдран Призман Кубан йгЦпзйЗау г.и. езйЙййЕкДбаЦ лнкйЦзаь а ойке ейгЦдмг йкЙДзауЦлдап лйЦСазЦзав 45 O 2− O − CH2 + F B C N C = F F O O O O H2C CH2 Трифторид Анион кислотного остатка Катион триметиленметана бора угольной азотной кислоты кислоты Схема 2 а также изомеров производных (замещенных) угле- лаееЦнкаь а ДлаееЦнкаь ейгЦдмг, водородов, когда “вручную”, при больших n, это дакДгъзДь лаееЦнкаь требует много времени. В настоящее время теория Обратимся теперь к другой особенности нашего графов естественным образом входит во многие сознания – вниманию. Когда мы рассматриваем ка- разделы современной математики, такие, как топо- кой-либо из окружающих объектов (в том числе мо- логия и комбинаторика, линейная алгебра и теория лекулярные графы), то при этом зачастую реализу- групп, теория вероятностей и численный анализ. ются тоже сознательно неконтролируемые операции Она успешно применяется в физике, химии, гене- внимания, которые отмечают, в каком соответствии тике, антропологии, электротехнике, проектирова- друг другу находятся части объекта. Древние греки нии ЭВМ, архитектуре, социологии и лингвистике. термином “соизмеримый” (σιёёετροσ) обозначали Следует иметь в виду особенности “языка” хи- такие особенности взаиморасположения, отноше- мических графов: ний частей объекта, которые и обусловливают его симметричный вид, форму – строгую симметрию молекулярные графы формализуют соедине- зданий, кристаллов минералов, двустороннюю сим- ния, включающие, как правило, несколько (два и метрию листьев растений, поворотную симметрию более) сортов атомов-вершин; цветов и т.д. если общая теория графов допускает произ- Объекты симметричны, если соразмерность и вольное количество ребер, исходящих из одной вер- взаиморасположение их частей допускают такие шины (в том числе изолированные вершины при операции поворотов, внутренних отражений, ин- полном отсутствии ребер), то вершины химическо- версий (комбинирование поворотов и отражений), го графа обязаны иметь ровно столько ребер (свя- действие которых оставляет их (объекты) неизмен- зей), какова валентность (координационное число) ными, переводит их самих в себя. Строение симмет- данного атома в химическом соединении; ричных объектов таково, что оно характеризуется наличием хотя бы одного из следующих элементов вершины химического графа вместе с направ- симметрии: лениями ребер должны быть четко ориентированы, плоскости зеркального отражения σ (S1) – пло- ибо они представляют собой взаиморасположение скости симметрии, имеющие ее объекты, состоят из атомов в молекулах, а также углы между связями одинаковых, зеркально-тождественных половин атомов: для тетраэдрического атома углерода эти (см. графы на схемах 1, 2 и в табл. 1); углы обычно равны 109,5°, для тригонально-плос- кого – 120°, для дигонального, ацетиленового – оси симметрии Сn , n = 2, 3, 4, …, – части объек- 180°, но могут быть и исключения (см. графы кар- та совмещаются, как и объект в целом, при его по- касных углеводородов в табл. 1), а трехмерные (объ- воротах на углы 2π / n (см. табл. 1 и схему 2); емные) проекции графов необходимы для пред- зеркально-поворотной оси Sn , S2 = i – центр ставления конфигураций молекул. инверсии – является комбинацией С2 + S1 , S4 = ком- Химики-экспериментаторы проектируют, по- бинации C4 + S1 (см. E-изомеры бутена-2, четных добно инженерам, графы новых, неизвестных ранее кумуленов, тетраэдран и кубан в табл. 1). соединений, продумывают и реализуют способы их Объект асимметричен, если его внутреннее синтеза. Химики-теоретики подвергают сравни- строение и внешнюю форму нельзя охарактеризо- тельному анализу в квантовохимических расчетах вать ни одним из перечисленных элементов сим- подчас весьма разные структуры, чтобы выявить метрии (см. 2-й и 4-й изомеры гексана на схеме 1, пределы изменений межатомных расстояний и рас- аланин на схеме 3). Для таких объектов имеется един- пределения электронов в ионах и молекулах, пред- ственная тривиальная операция симметрии – С1 . ставляемых одним графом (см. схему 2). Графичес- Поворот С1 на 360° (2π) совмещает асимметричный кие формулы стали обиходными немногим более объект сам с собой. Разумеется, действием опера- 100 лет назад, и графовый язык общения химиков ции С1 совмещаются сами с собой и все симметрич- непрерывно совершенствуется. ные объекты, поскольку этот поворот тривиален. 46 лйкйлйЗлдав йЕкДбйЗДнЦгъзхв ЬмкзДг, ‹2, 1997 3 3 H H H H H COOH H3C COOH HOOC CH3 C 2 C C C 2 C 1 4 4 1 H H H2N H H2N H H2N H H NH2 Метан Метиламин Глицин l-аланин r-аланин Схема 3 Сферы, шары – примеры объектов, имеющих асимметричная молекула (аланин) имеет зеркаль- бесконечные множества всех элементов симметрии – ного двойника – дубль (см. схему 3). S1(σ), Cn , Sn . Шар совмещается сам с собой при лю- бых поворотах, любых ориентациях зеркальных В 60–70-е годы нашего столетия ученые-стерео- плоскостей и осей вращения, проходящих через его химики Р. Кан, К. Ингольд и В. Прелог выработали центр. Поэтому правильные выпуклые многогран- общие правила для отнесения компонентов-дубле- ники (тетраэдр, куб, октаэдр, додекаэдр, икосаэдр – тов подобного типа к левым (l) и правым (r) формам: идеальные Платоновы тела), в которые вписывают- заместители (атомы), связанные с асимметри- ся сферы, имеют хотя и конечные наборы элементов ческим углеродным или иным атомным центром, симметрии, но их число и разнообразие всегда наи- сортируются по их иерархии, и самым старшим (но- большие в сравнении с другими многогранниками. мером 1) является тот, который имеет бульшую Уже давно было отмечено, что если асимметрич- атомную массу: в аланине (схема 3) 14N старше 12С, а ную фигуру отразить в зеркальной плоскости, распо- среди атомов углерода метильной и карбоксильной групп старше последний: он связан с тяжелыми 16О, ложенной вне этого объекта, то получается фигура, в в то время как первый – с легкими 1Н; точности подобная исходной, но несовместимая с первой при любых сдвигах и поворотах. Следова- наблюдатель ориентируется (конечно, мыс- тельно, всем асимметричным объектам можно со- ленно) к молекуле, или молекула ориентируется к поставить зеркальноподобные двойники. Обыден- наблюдателю таким образом, чтобы углеродный ные примеры этого – наша обувь и перчатки, левые центр “заслонял” самый младший заместитель (Н), и правые пары фигур которых облегают соответст- и если при этом траектория последовательного пе- венно левые и правые зеркально-дублетные конеч- рехода от самого старшего к младшим (незаслонен- ности наших вообще-то планарно-симметричных ным) заместителям (то есть от первого номера к по- фигур. Кристаллографы еще несколько веков назад следующим) аналогична движению стрелок часов, отметили распространенность зеркальноподобных то конфигурация абсолютно правая (r), если наобо- энантиоморфных форм в неорганическом мире – рот, то абсолютно левая (l). левые и правые кристаллы кварца, турмалина, каль- цита (исландский шпат). Введя представления об абсолютно левых и пра- вых конфигурациях, мы должны предупредить об Зеркальная изомерия, энантиомерия, в органи- относительности этой абсолютности. Операции зер- ческой химии – весьма распространенное явление. кального отражения соответствует Р – инверсия ко- Приоритет ее открытия в середине прошлого столе- ординат всех атомных и субатомных частей объекта. тия принадлежит выдающемуся французу Луи Пас- Однако поскольку неизвестно внутреннее строение теру, обратившему внимание на зеркальное подобие атомных (электроны) и субатомных (кварки, глюо- форм кристаллов калий-аммонийных солей винной ны) частиц, то операцию Р физики дополняют фор- кислоты. С именем Пастера связано становление мальной операцией зарядового сопряжения С – стереохимии, основывающейся на проблемах сим- сменой на противоположные знаки зарядов и всех метрии и асимметрии молекул, их строения (формы) других антиподных квантовых характеристик атом- в трехмерном пространстве. Важной вехой разви- ных (протонов, нейтронов, электронов) и субатом- тия стереохимии явилась предложенная в 1874 году ных (кварков, глюонов) частиц, а также операцией Я. Вант Гоффом и Ж. Ле Белем тетраэдрическая инверсии направлений движения (импульсов и мо- модель атома углерода. Если в простейшем углево- ментов импульсов) всех составляющих объекта, ко- дороде, фигура которого аналогична высокосим- торая соответствует обращению времени Т. Поэто- метричному тетраэдру, – метане атомы водорода му действительно предельной инверсией является последовательно заменять (замещать) другими ато- комбинированная СРТ-операция. Отсюда следует, мами и атомными группировками, то симметрия что абсолютным антиподом исходной, например, получающихся молекул быстро понижается. После r-молекулы должен быть ее l-партнер, но состоя- трех таких процедур с тетраэдрическим углеродным щий из антивещества и движущийся во времени центром связаны уже четыре разных заместителя, и вспять. Идеи комбинирования Р-, С- и Т-операторов йгЦпзйЗау г.и. езйЙййЕкДбаЦ лнкйЦзаь а ойке ейгЦдмг йкЙДзауЦлдап лйЦСазЦзав 47 симметрии принадлежат Г. Людерсу и В. Паули единить к бесконечно симметричной сфере, то все (1954–1955). элементы симметрии исходного объекта деградиру- Вследствие гигантских возможностей варьирова- ют полностью, то есть асимметричная “добавка” ния атомов и атомных групп, способных связывать- переводит идеально симметричный (синглетный) ся с углеродом, в принципе реализуемы бесконеч- объект в класс энантиомерных дублетов. ные последовательности зеркальных r, l-дублетов Однако не следует считать, что энантиомерия молекул с асимметрическими углеродными центра- невозможна среди симметричных фигур (молекул). ми. Отметим их фундаментальную особенность: ес- Запомним простую закономерность: зеркальная ли асимметрический углеродный или иной атом- конфигурационная изомерия действительно невоз- ный центр поместить в качестве заместителя на можна в рядах объектов (молекул), имеющих в ка- одну из вершин высокосимметричного объекта (на- честве внутренних элементов симметрии плоско- пример, на тетраэдран, кубан; табл. 1) и даже присо- сти зеркального отражения σ (S1) и/или зеркально- Таблица 2 C2 C2 R L . . (CH 2) n (CH 2) n R, L-транс-циклооктены R, L-транс-циклоэтилены C2 C2 C2 C2 C2 C2 Твистан R L Z Z -бифенилы симметрии C2 Z Z R L -трифенилметаны симметрии C3 L R C2 R Гексагелицен L Спирали, пружины, шнеки, винты, гайки, болты 48 лйкйлйЗлдав йЕкДбйЗДнЦгъзхв ЬмкзДг, ‹2, 1997 поворотные оси i (S2, 3, 4, …). При отражении таких д – топологически-киральные молекулы (кате- фигур внешней зеркальной плоскостью получаются наны, узлы на схеме 4). тождественные исходным объекты-копии (см. гра- Все же условность разбиения очевидна в свете фы на схемах 1, 2 и в табл. 1). Наоборот, если строе- разработанных Р. Каном, К. Ингольдом и В. Прело- ние объектов (молекул) характеризуется отсутстви- гом , дополненных их последователями ем внутренних зеркальных элементов симметрии Sn правил отнесения конфигураций энантиомерных (σ, i), но они симметричны относительно поворотов молекул к R- или L-рядам – это циркулярные, спи- Cn (n = 2, 3, 4, …), то такие фигуры всегда R, L-дуб- ральные (киральные) движения по (R) или против летны. Простейший пример – 1,3-диметил-3-куму- (L) хода стрелок часов при последовательном рас- лен (табл. 1) и все его гомологи с нечетным числом смотрении “старшинства” (веса) заместителей, рас- атомов углерода в линейной цепи. В табл. 2 показа- полагающихся (схема 3) вокруг атомного центра – ны некоторые R, L-дублеты из большого множества а, выделенной плоскости – б (транс-циклоэтилены, молекул, симметричных относительно поворотов. табл. 2), при обходе контуров пропеллеров – в, вин- Отметим, что они вообще не имеют асимметричес- тов – г, узлов – д в табл. 2, на схеме 4. ких углеродных центров. В технике молекулам бифе- нилов и трифенилметилов аналогичны фигуры ло- пастей вентиляторов, пропеллеров, роторы турбин; фигурам гелиценовых молекул аналогичны спирали, пружины, шнеки, левая и правая нарезка винтов. Для краткой характеристики обсуждаемого яв- -катенан ления на рубеже XIX и XX веков лорд Кельвин Трилистный узел (CH2)m , с ориентированными и не- минимальное m = 66 предложил термин “chirality” (от греч. χειρ – рука). тождественными кольцами В русском языке употребляются два варианта произ- ношения и написания этого термина: киральность и Схема 4 хиральность. Автор вместе с физиками отдает пред- почтение первому. Сопряженные операцией зер- кального отражения (координатной инверсии P) мо- Следовательно, строго говоря, не существуют лекулы – компоненты энантиомерных дублетов – качественно различные виды киральности молекул. отличаются лишь единственным свойством – про- Например, называемая топологической кираль- тивоположными знаками +(R) и −(L) угла враще- ность д на схеме 4 всего лишь отражение той струк- ния плоскости поляризации света. Аналогичные турной особенности изображенных молекул, что антиподные (+, −) отношения характерны также отдельные их части удерживаются вместе не хими- для полюсов магнитов, зарядов и других квантовых ческими связями, а топологией строения цепей (ка- характеристик атомных и субатомных частиц. Такие тенаны), замкнутых спиралей и узлов; их киральная отношения называются физиками киральной сим- (R, L) форма вполне аналогична форме пропелле- метрией. ров – в и спиралей – г. Поэтому все перечисленные выше виды киральности молекул количественно Благодаря усилиям химиков-синтетиков, увле- оцениваются единообразно: знаком (+, −) и вели- ченных проблемами стереостроения, за последние чиной угла вращения плоскости поляризации при десятилетия стали известны и доступны весьма мно- стандартной длине волны света. гочисленные, в том числе экзотические, виды ки- Тем не менее известно также и то, что при поли- ральных молекул (см. табл. 2 и схему 4). Принято конденсации центрально-киральных (r либо l) ами- считать , что разнообразие киральных химичес- нокислот, рибонуклеотидов общая киральность по- ких соединений разделяется на пять видов в соответ- лимера (белка, ДНК) не может быть оценена ствии с симметричными особенностями строения: тривиальным суммированием индивидуальных ки- а – молекулы с киральным центром не имеют ральностей звеньев: Σrn(ln) . Эта сумма “объем- никаких элементов симметрии, кроме элемента лется” спиральной (геликальной) киральностью идентичности C1 (примеры – аминокислоты (ала- макромолекулы, имеющей свой знак (+R h, −Lh) и нин на схеме 3), сахара-углеводы); абсолютную величину, б – планарно-киральные молекулы симметрии Nr (l) ∑ l (r) ⊂ R (L). h h C1 и/или C2 (выделенный элемент строения – плос- n n (1) кость, примеры – транс-циклоэтилены в табл. 2); Тот факт, что регулярная орто-конденсация аки- в – аксиально-киральные молекулы c симмет- ральных бензольных колец также приводит к спи- рией Cn (имеют форму пропеллеров или свастик, ральным гелиценам (табл. 2), лишь подтверж- примеры – твистан, бифенил, трифенилметан в дает общее правило: и циркулярное объединение табл. 2 и т.п.); акиральных мономеров подходящего строения, и г – геликально-киральные молекулы симметрии линейная поликонденсация киральных (только r C2 (характерная форма – спираль, примеры – гекса- или только l) звеньев автоматически ведут к спи- гелицен в табл. 2, белки, ДНК); ральной форме полимера. Можно полагать, что в йгЦпзйЗау г.и. езйЙййЕкДбаЦ лнкйЦзаь а ойке ейгЦдмг йкЙДзауЦлдап лйЦСазЦзав 49 рядах таких макромолекул реализуется некая пос- имеющие внутренние зеркальные элементы симмет- ледовательность киральностей, соответствующая рии Sn , конфигурационно однозначны (синглетны), иерархии уровней стереостроения. Например, пер- поскольку их внутреннее строение Р-четно. Объек- вичный, вторичный, третичный и четвертичный ты, не имеющие внутренней Р-четности строения уровни строения гемоглобина , очевидно, харак- (не имеющие элементов симметрии Sn), всегда кон- теризуются также последовательностями “вложе- фигурационно двузначны (дублетны, левый + пра- ний” типа (1) суммы индивидуальных киральностей вый). Чтобы из Р-четного объекта получить его ко- аминокислот в спиральную киральность полипеп- пию, достаточно одной Рσ(i)-операции, но чтобы тида, этих двух – в “глобулярную” киральность скопировать Р-нечетный объект, необходимы две третичного уровня, наконец, этих трех – в “надмо- последовательные Р-операции: лекулярную” киральность квартета (тетраэдра) объединенных глобул. Отсюда, между прочим, сле- P P R L R. дует, что стереохимия полимеров, их ассоциатов должна учитывать в дополнение к перечисленным Заметим, однако, что далеко не всем окружаю- выше также “глобулярную” – е и “надмолекуляр- щим нас в живой и неживой природе Р-нечетным ную” – ж виды киральности. Именно следующие за объектам можно легко найти левых либо правых первичным (структурным) верхние конфигураци- партнеров-близнецов, например выбранному дере- онные уровни организации макромолекул играют ву в лесу или камню из кучи щебня. Отметим далее, решающую роль при их функционировании в орга- что киральная симметрия абсолютно (на 100%) не низмах. Так, биохимические реакции с участием соблюдается для Р-нечетных молекул органических ферментов эффективно осуществляются лишь в соединений, входящих в состав всех живых орга- случаях, когда предварительно реализована ком- низмов на нашей планете. Если это аминокислоты, плементация, то есть “узнавание”, отбор тех моле- то только левые (l); если сахара-углеводы, то только кул реагентов и субстратов, особенности конфигу- правые (r); если это биополимеры, то они спираль- рации которых (“фигуры” которых) идеально но закручены только вправо (белки, ДНК). На эту согласуются с контурами, формами соответствую- закономерность, называемую киральной асиммет- щих полостей в глобулах ферментов. Бытовым ана- рией биосферы, также впервые обратил внимание логом такой комплементации Д. Кошланд предло- Л. Пастер. жил считать соответствие ключа и замка . ганЦкДнмкД дакДгъзДь ДлаееЦнкаь 1. Общая органическая химия: Пер. с англ. М.: Химия, Обобщим изложенное выше. Данная статья пре- 1981–1986. Т. 1–12. следует цель показать, что в необозримом на пер- 2. Жданов Ю.А. Углерод и жизнь. Ростов н/Д: Изд-во вый взгляд материале органической химии легче РГУ, 1968. 131 с. ориентироваться, если усвоить принципы графово- 3. Татт У. Теория графов. М.: Мир, 1988. го изображения наиболее общих характеристик строения молекул, а также принципы оценки их 4. Соколов В.И. Введение в теоретическую стерео- конфигурации – формы в трехмерном пространст- химию. М.: Наука, 1982; Успехи химии. 1973. Т. 42. ве – на основе идей симметрии и асимметрии. По- С. 1037–1051. следние включают представления об основных опе- 5. Ногради М. Стереохимия. М.: Мир, 1984. раторах симметрии: плоскости, осях и зеркально- 6. Харгиттаи И., Харгиттаи М. Симметрия глазами поворотных осях, используемых при выявлении тех химика. М.: Мир, 1989. внутренних особенностей строения молекул, кото- 7. Филиппович И.В., Сорокина Н.И. // Успехи соврем. рые определяют их внешний вид, форму и в конеч- биологии. 1983. Т. 95. С. 163–178. ном счете важнейшие их свойства. При “сортировке” молекул на симметричные и * * * асимметричные особая роль принадлежит операто- ру зеркального отражения – координатной инвер- Лев Петрович Олехнович, доктор химических на- сии Р. Оператор Рσ координатам всех частей (ато- ук, профессор, зав. кафедрой химии природных и мов) объекта, расположенного слева от выбранной высокомолекулярных соединений Ростовского го- плоскости, ставит в однозначное соответствие коор- сударственного университета, зав. лабораторией динаты инвертированного (отраженного) объекта внутренней динамики молекул химфака и НИИ фи- справа от этой плоскости. Оператор Pi осуществляет зической и органической химии РГУ, член-коррес- аналогичную координатную инверсию относитель- пондент Российской академии естественных наук. но точки, выбранной вне объекта (легко сообразить Область научных интересов: органический синтез, и проверить, что при действии Pi -оператора также кинетика и механизмы молекулярных перегруппи- получается зеркальный двойник объекта, но повер- ровок, стереохимия и стереодинамика. Соавтор нутый, опрокинутый на 180°). Объекты (молекулы), двух монографий и автор более 370 научных статей. 50 лйкйлйЗлдав йЕкДбйЗДнЦгъзхв ЬмкзДг, ‹2, 1997

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

Естественным расширением молекулярного графа является реакционный граф , рёбра которого соответствуют образованию, разрыву и изменению порядка связей между атомами.

«Подчеркнём, что именно в теории Р. Бейдера впервые нашла обоснование эмпирическая идея аддитивности, именно эта теория позволила придать строгий физический смысл целому ряду понятий классической теории химического строения , в частности, „валентному штриху“ (связевый путь) и структурной химической формуле (молекулярный граф).»

Напишите отзыв о статье "Молекулярный граф"

Примечания

См. также

Литература

• = Chemical Applications of Topology and Graph Theory, ed. by R. B. King. - М .: Мир, 1987. - 560 с.

Химическая связь Отображение структуры Электронные свойства Стереохимия

Отрывок, характеризующий Молекулярный граф

На другой день князь Андрей вспомнил вчерашний бал, но не на долго остановился на нем мыслями. «Да, очень блестящий был бал. И еще… да, Ростова очень мила. Что то в ней есть свежее, особенное, не петербургское, отличающее ее». Вот всё, что он думал о вчерашнем бале, и напившись чаю, сел за работу.
Но от усталости или бессонницы (день был нехороший для занятий, и князь Андрей ничего не мог делать) он всё критиковал сам свою работу, как это часто с ним бывало, и рад был, когда услыхал, что кто то приехал.
Приехавший был Бицкий, служивший в различных комиссиях, бывавший во всех обществах Петербурга, страстный поклонник новых идей и Сперанского и озабоченный вестовщик Петербурга, один из тех людей, которые выбирают направление как платье – по моде, но которые по этому то кажутся самыми горячими партизанами направлений. Он озабоченно, едва успев снять шляпу, вбежал к князю Андрею и тотчас же начал говорить. Он только что узнал подробности заседания государственного совета нынешнего утра, открытого государем, и с восторгом рассказывал о том. Речь государя была необычайна. Это была одна из тех речей, которые произносятся только конституционными монархами. «Государь прямо сказал, что совет и сенат суть государственные сословия; он сказал, что правление должно иметь основанием не произвол, а твердые начала. Государь сказал, что финансы должны быть преобразованы и отчеты быть публичны», рассказывал Бицкий, ударяя на известные слова и значительно раскрывая глаза.
– Да, нынешнее событие есть эра, величайшая эра в нашей истории, – заключил он.
Князь Андрей слушал рассказ об открытии государственного совета, которого он ожидал с таким нетерпением и которому приписывал такую важность, и удивлялся, что событие это теперь, когда оно совершилось, не только не трогало его, но представлялось ему более чем ничтожным. Он с тихой насмешкой слушал восторженный рассказ Бицкого. Самая простая мысль приходила ему в голову: «Какое дело мне и Бицкому, какое дело нам до того, что государю угодно было сказать в совете! Разве всё это может сделать меня счастливее и лучше?»
И это простое рассуждение вдруг уничтожило для князя Андрея весь прежний интерес совершаемых преобразований. В этот же день князь Андрей должен был обедать у Сперанского «en petit comite«, [в маленьком собрании,] как ему сказал хозяин, приглашая его. Обед этот в семейном и дружеском кругу человека, которым он так восхищался, прежде очень интересовал князя Андрея, тем более что до сих пор он не видал Сперанского в его домашнем быту; но теперь ему не хотелось ехать. Автор Химическая энциклопедия г.р. И.Л.Кнунянц

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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