kvm-mtv.ru → Гадания

Графы и химия. Алгебра и гармония в химических приложениях. Основные определения и теоремы теории графов

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

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

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

Страница «ГРАФОВ ТЕОРИЯ» подготовлена по материалам

Изучение связи свойств веществ с их строением – одна из основных задач химии. Большой вклад в ее решение внесла структурная теория органических соединений, в число создателей которой входит великий российский химик Александр Михайлович Бутлеров (1828-1886). Именно он первым установил, что свойства вещества зависят не только от его состава (молекулярной формулы), но и от того, в каком порядке связаны между собой атомы в молекуле. Такой порядок назвали «химическим строением». Бутлеров предсказал, что составу C 4 H 10 могут соответствовать два вещества, имеющие разное строение – бутан и изобутан, и подтвердил это, синтезировав последнее вещество.

Идея о том, что порядок соединения атомов имеет ключевое значение для свойств вещества, оказалась очень плодотворной. На ней основано представление молекул с помощью графов, в которых атомы играют роль вершин, а химические связи между ними – ребер, соединяющих вершины. В графическом представлении длины связей и углы между ними игнорируются. Описанные выше молекулы C 4 H 10 изображаются следующими графами:

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

Графы – это математические объекты, поэтому их можно характеризовать с помощью чисел. Отсюда появилась идея выражать строение молекул числами, которые связаны со структурой молекулярных графов. Эти числа в химии называют «топологическими индексами». Рассчитав какой-либо топологический индекс для большого числа молекул, можно установить связь между его значениями и свойствами веществ, и затем использовать эту связь для предсказания свойств новых, еще не синтезированных веществ . К настоящему моменту химиками и математиками предложены сотни разнообразных индексов, характеризующих те или иные свойства молекул.

Методы расчета топологических индексов

Способы расчета топологических индексов могут быть самыми разнообразными, но все они должны удовлетворять вполне естественным требованиям:

1) каждой молекуле соответствует свой, индивидуальный индекс;

2)близкие по свойствам молекулы имеют похожие индексы.

Посмотрим, как реализуется эта идея на примере предельных углеводородов – алканов. Ключевым для построения многих индексов служит понятие «матрицы расстояний» D. Так называют матрицу, элементы которой показывают число ребер, разделяющих соответствующие вершины молекулярного графа. Построим эту матрицу для трех изомерных углеводородов состава C 5 H 12 . Для этого изобразим их молекулярные графы и перенумеруем вершины (в произвольном порядке):

Диагональные элементы матрицы расстояний для углеводородов равны 0. В первом графе вершина 1 связана с вершиной 2 одним ребром, поэтому элемент матрицы d 12 = 1. Аналогично, d 13 = 2, d 14 = 3, d 15 = 4. Первая строка в матрице расстояний нормального пентана имеет вид: (0 1 2 3 4). Полные матрицы расстояний для трех графов:

молекула химия топологический индекс

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

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

(1)

Для указанных выше графов, соответствующих пентанам C 5 H 12 , индекс Винера принимает значения 20, 18 и 16. Можно предположить, что он описывает степень разветвленности углеводорода: наибольшие значения соответствуют наименее разветвленным углеводородам. С увеличением длины углеродного скелета индекс Винера растет, так как в матрице расстояний становится больше элементов. Статистический анализ на примере нескольких сотен углеводородов показал, что индекс Винера коррелирует с некоторыми физическими свойствами алканов: температурами кипения, теплотами испарения, молярным объемом.

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

(2)

где v i – степень i-й вершины, то есть число ребер, от нее отходящих. Для указанных выше графов индекс Рандича равен:

(3)

(4)

(5)

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

Алканы – самый скучный с химической точки зрения тип органических молекул, так как он не содержит никаких «особенностей» – двойных и тройных связей или атомов других элементов, кроме водорода и углерода (такие элементы называют гетероатомами). Введение гетероатомов в состав молекулы может кардинально изменить свойства вещества. Так, добавление всего одного атома кислорода превращает довольно инертный газообразный этан C 2 H 6 в жидкий этанол C 2 H 5 OH, проявляющий довольно высокую химическую и биологическую активность.

Следовательно, в топологических индексах молекул, более сложных, чем алканы, надо учитывать присутствие кратных связей и гетероатомов. Это делается путем присвоения вершинам и ребрам графов определенных числовых коэффициентов – «весов» . Например, в матрице расстояний диагональные элементы можно определить через заряд ядра Z i (напомним, что для углерода Z = 6):

(6)

Недиагональные элементы определяются суммированием по ребрам, причем каждому ребру, соединяющему атомы с зарядами Z i и Z j , присваивается вес

(7)

где b равно порядку связи между атомами (1 для одинарной связи, 2 для двойной, 3 для тройной). Для обычных одинарных связей углерод-углерод, k = 1. Сравним индексы Винера пропана C 3 H 8 и трех близких по составу кислородсодержащих веществ: пропилового спирта C 3 H 8 O, изомерного ему изопропилового спирта C 3 H 8 O и ацетона C 3 H 6 O.

Для этого рассчитаем по указанным правилам матрицы расстояний. В молекулярных графах укажем все атомы, кроме атомов водорода.1) Пропан

2) В молекуле пропилового спирта кислород связан с крайним атомом углерода:

Для одинарной связи C–O весовой коэффициент равен 36/(68) = 0.75. Диагональный элемент матрицы, отвечающий кислороду:

d 44 = 1 – 6/8 = 0.25.

Для молекул, содержащих гетероатомы, индекс Винера перестает быть целым. 3) В молекуле изопропилового спирта кислород связан со средним атомом углерода:

4) В ацетоне порядок соединения атомов – такой же, как в изопропиловом спирте, но связь между углеродом и кислородом – двойная:

Для двойной связи C=O весовой коэффициент равен 36/(268) = 0.375

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

В - Р + Г = 1, (*)

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

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

а) б)

Рис.2

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

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

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

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

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

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

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

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

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

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

B - Р + Г= 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;

Причем последние 12 лет своей жизни Эйлер тяжело болел, ослеп и, несмотря на тяжелый недуг, продолжал работать и творить.

Статистические подсчеты показывают, что Эйлер в среднем делал одно открытие в неделю.

Трудно найти математическую проблему, которая не была бы затронута в произведениях Эйлера.

Все математики последующих поколений так или иначе учились у Эйлера, и недаром известный французский ученый П.С. Лаплас сказал: "Читайте Эйлера, он – учитель всех нас".

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

С именем Эйлера, является задача о трех домиках и трех колодцах.

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

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

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

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

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

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

Можно совместить все три графа для всех позиций либо только для одной, и в результате мы получаем ясное представление о конкретной структуре к.-л. данной роли. Так, для роли позиции 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, (*)

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

а) б)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Э. Беляев. Ленинград.

Страница 8, как и неорганической, ... замуж за авантюристаЗакон >> Исторические личности

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

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

Графы служат, прежде всего, средством изображения молекул. При топологическом описании молекулы её изображают в виде мо-лекулярного графа (МГ), где вершины соответ-ствуют атомам, а рёбра - химическим связям (теоретико-графовая модель молекулы). Обыч-но в таком представлении рассматривают толь-ко скелетные атомы, например, углеводороды со «стёртыми» атомами водорода.

Валентность химических элементов на-кладывает на степени вершин определённые ограничения. У деревьев-алканов (связных гра-фов, не имеющих циклов) степени вершин (г) не могут превышать четырёх (г = 1, 2, 3, 4).

Графы можно задавать в матричном виде, что удобно при работе с ними на ЭВМ.

Матрица смежности вершин простого графа - это квадратная матрица А = [аσχ] с эле-ментами аσχ = 1, если вершины σ и χ соедине-ны ребром, аσχ = 0 - в противном случае. Ма-трица расстояний - это квадратная матрица D = с элементами dσχ, определяемыми как минимальное число рёбер (наикратчайшее рас-стояние) между вершинами σ и χ. Иногда при-меняются также матрицы смежности и расстоя-ний по рёбрам (А е и D e).

Вид матриц А и D (А е и D e) зависит от спо-соба нумерации вершин (или рёбер), что вызы-вает неудобство при обращении с ними. Для характеризации графа применяются инварианты графа - топологические индексы (ТИ).

Число путей длины один

pi = хсс 0 = m = n-1

Число путей длины два

Число троек смежных ребер (с общей вершиной)

Число Винера (W), определяемое как по-лусумма элементов матрицы расстояний рассма-триваемого графа:

и т.д.

Методология изучения связи «структура-свойство» через топологические индексы в теоретико-графовом подходе включает в себя следующие этапы .

Выбор объектов исследования (обучаю-щая выборка) и анализ состояния численных данных по свойству Р для данного круга соеди-нений.

Отбор ТИ с учетом их дискриминирую-щей способности, корреляционной способности со свойствами и т.д.

Изучение графических зависимостей «Свойство Р - ТИ графа молекулы», например, Р от n - числа скелетных атомов, Р от W - чис-ла Винера и т.п.

Установление функциональной (аналити-ческой) зависимости Р = _ДТИ), например,

Р = а(ТИ) + b ,

Р = аln(ТИ) + b ,

Р = а(ТИ) 1 +b(ТИ) 2 +...+n(ТИ) n +с

и т.п. Здесь а, b, с - некоторые параме-тры (не следует путать их с параметрами адди-тивных схем.), подлежащих определению.

Численные расчеты Р, сопоставление рас-считанных значений с экспериментальными.

Предсказание свойств еще не изученных и даже не полученных соединений (вне данной выборки).

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

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

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

Нами были построены аддитивные схе-мы и найдены аналитические зависимости вида Р = У(ТИ) для ряда органических и других мо-лекул. По полученным формулам выполнены численные расчеты физико-химических свойств рассматриваемых соединений, с .

Список литературы

Виноградова М.Г., Папулов Ю.Г., Смо-ляков В.М. Количественные корреляции «струк-тура свойство « алканов. Аддитивные схемы расчета. Тверь, 1999. 96 с.
Химические приложения топологии и теории графов / Под ред. Р. Кинга. М.: Мир, 1987. 560 с.
Применение теории графов в химии / Под ред. Н.С. Зефирова и С.И. Кучанова. Ново-сибирск: Наука, 1988. 306 с.
Станкевич М.И., Станкевич И.В., Зе-фиров Н.С. Топологические индексы в органи-ческой химии // Успехи химии. 1988. Т.57, №3,С.337-366.
Виноградова М.Г., Салтыкова М.Н. Теоретико-графовый подход в изучении взаимосвязи между строением и свойствами алкилсиланов.// Фундаментальные исследования, 2009. №1. С. 17-19.
Виноградова М.Г., Салтыкова М.Н., Ефремова А.О., Мальчевская О.А. Взаимосвязь между строением и свойствами алкилсиланов //Успехи современного естествознания, №1, 2010. С.136-137.
Виноградова М.Г., Салтыкова М.Н.,Ефремова А.О. Корреляции «Структура - свойство» алкилсиланов: теоретико-графовый подход // Успехи современного естествознания, №3, 2010. С.141-142.

Библиографическая ссылка

Виноградова М.Г. ТЕОРИЯ ГРАФОВ В ХИМИИ // Международный журнал прикладных и фундаментальных исследований. – 2010. – № 12. – С. 140-142;
URL: https://applied-research.ru/ru/article/view?id=1031 (дата обращения: 17.12.2019). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»

Графы и химия. Алгебра и гармония в химических приложениях. Основные определения и теоремы теории графов

Методы расчета топологических индексов

Библиографическая ссылка