Зачет по медицинской химии. Вопросы билетов по компьютерному молекулярному моделированию и методам QSAR.

Общие сведения

Аббревиатура QSAR является сокращением от английского Quantitative Structure Activity Relationships, что в переводе на русский язык обозначает Количественное Cоотношение Cтруктура Активность (поэтому иногда в русскоязычной литературе используют сокращение КССА).

Одной из важнейших задач современной химической науки является установление зависимостей между структурой и свойствами веществ. Число вновь синтезируемых новых органических соединений постоянно увеличивается поэтому самой актуальной задачей является количественное предсказание конкретных свойств для новых еще не синтезированных веществ на основании определенных физико-химических параметров отдельных соединений.

Исторически всё началось с попыток учёных найти количественную связь между структурами веществ и их свойствами и выразить эту связь в количественном виде, например в виде математического уравнения. Это уравнение должно отражать зависимость одного числового набора (представляющих свойства) от другого числового набора (представляющего структуры). Выразить в числовом виде свойство достаточно просто – физиологическую активность серии веществ можно измерить количественно. Гораздо сложнее численно выразить структуры химических соединений. Для такого выражения в настоящее время в QSAR используются так называемые дескрипторы химической структуры.

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

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

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

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

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

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

Вопрос №3. Понятие о молекулярных графах и их инвариантах. Типы дескриптором молекулярной структуры. Понятие о топологических индексах. Индексы Винера, Рандича, Кира-Холла и другие топологические индексы. QSAR с использованием топологических индексов.

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

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

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

Топологический индекс - инвариант (инвариант - термин, обозначающий нечто неизменяемое) молекулярного графа в задачах компьютерной химии. ЭЭто некоторое (обычно числовое) значение (или набор значений), характеризующее структуру молекулы. Обычно топологические индексы не отражают кратность химических связей и типы атомов (C,N,O и.т.д.), атомы водорода не учитываются. К наиболее известным топологическим индексам относятся индекс Хосои, индекс Винера, индекс Рандича, индекс Балабана и другие.

Глобальные и локальные индексы

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

Дискриминирующая способность и супериндексы

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

Вычислительная сложность

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

Применение

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

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

Молекулярные дескрипторы. Типы молекулярных дескрипторов.

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

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

2. Топологические индексы .(информацию по ним см. выше)

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

4. Квантово-химические дескрипторы - это числовые величины, получаемые в результате квантово-химических расчетов. Наиболее часто в качестве дескрипторов используются: энергии граничных молекулярных орбиталей (ВЗМО и НСМО), частичные заряды на атомах и частичные порядки связей, индексы реакционной способности Фукуи (индекс свободной валентности, нуклеофильная и электрофильная суперделокализуемость), энергии катионной, анионной и радикальной локализации, дипольный и высшие мультипольные моменты распределения электростатического потенциала.

5. Дескрипторы молекулярных полей - это числовые величины, аппроксимирующие значения молекулярных полей путем вычисления энергии взаимодействия пробного атома, помещенного в узел решетки, с текущей молекулой. На построении корреляций между значениями дескрипторов молекулярных полей и числовым значением биологической активности при помощи метода частичных наименьших квадратов (Partial Least Squares - PLS) основаны методы 3D-QSAR, наиболее известным из которых является CoMFA .

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

7. Фармакофорные дескрипторы показывают, могут ли простейшие фармакофоры, состоящие из пар или троек фармакофорных центров со специфицированным расстоянием между ними, содержатся внутри анализируемой молекулы.

8. Дескрипторы молекулярного подобия указывают на меру сходства (молекулярного подобия) с соединениями из обучающей выборки.

Индекс Винера (англ. Wiener index), известный также как число Винера (англ. Wiener number), - топологический индекс неориентированного графа , определяемый как сумма кратчайших путей (англ.) d(vi,vj) между вершинами графа:

Индекс Рандича (англ. Randić index ), известный также как индекс связности неориентированного графа , является суммой вкладов по ребрам , где v i и v j - вершины, образующие ребро, d (v k ) - степень вершины v k :

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

Часто химические связи образуются за счёт электронов, расположенных на разных атомных орбиталях (например, s – и р – орбитали). Несмотря на это, связи оказываются равноценными и расположены симметрично, что обеспечено гибридизацией атомных орбиталей.

Гибридизация орбиталей - это изменение формы некоторых орбиталей при образовании ковалентной связи для достижения более эффективного перекрывания орбиталей.

В результате гибридизации появляются новые гибридные орбитали , которые ориентируются в пространстве таким образом, чтобы после их перекрывания с орбиталями других атомов образующиеся электронные пары оказались максимально удалёнными друг от друга. Это сводит к минимуму энергию отталкивания электронов в молекуле.

Гибридизация не является реальным процессом. Это понятие введено для описания геометрической структуры молекулы. Форма частиц, возникающих при образовании ковалентных связей, в которых участвуют гибридные атомные орбитали, зависит от числа и типа этих орбиталей. При этом σ – связи создают жёсткий «скелет» частицы:

Орбитали участвующие в гибридизации	Тип гибридизации	Пространственная форма молекулы	Примеры
s, p	sp – гибридизация	Линейная	BeCl 2 CO 2 C 2 H 2 ZnCl 2 BeH 2 Две sp - орбитали могут образовывать две σ - связи ( BeH 2 , ZnCl 2 ). Еще две p - связи могут образоваться, если на двух p - орбиталях, не участвующих в гибридизации, находятся электроны (ацетилен C 2 H 2 ).
s, p, p	sp 2 – гибридизация	Треугольная (плоская тригональная)	BH 3 BF 3 C 2 H 4 AlCl 3 Если связь образуется при перекрывании орбиталей по линии, соединяющей ядра атомов, она называется σ - связью . Если орбитали перекрываются вне линии, соединяющей ядра, то образуется π - связь . Три sp 2 - орбитали могут образовывать три σ - связи ( BF 3 , AlCl 3 ). Еще одна связь (π - связь) может образоваться, если на p - орбитали, не участвующей в гибридизации, находится электрон (этилен C 2 H 4 ).
s, p, p, p	sp 3 – гибридизация	Тетраэдрическая	С H 4 NH 4 + PO 4 3- BF 4 -

На практике вначале экспериментально устанавливают геометрическую структуру молекулы, после чего описывают тип и форму атомных орбиталей, участвующих в её образовании. Например, пространственная структура молекул аммиака и воды близка к тетраэдрической, но угол между связями в молекуле воды равен 104,5˚, а в молекуле NH 3 – 107,3˚.

Чем это можно объяснить?

Аммиак NH 3

Молекула аммиака имеет форму тригональной пирамиды с атомом азота в вершине . Атом азота находится в sp 3 - гибридном состоянии; из четырех гибридных орбиталей азота три участвуют в образовании одинарных связей N–H, а четвертая sp 3 - гибридная орбиталь занята неподеленной электронной парой, она может образовать донорно-акцепторную связь с ионом водорода, образуя ион аммония NH 4 + , а также является причиной отклонения от тетраэдрического угла в строении

Вода H 2 O

Молекула воды имеет угловое строение: представляет собой равнобедренный треугольник с углом при вершине 104,5°. Атом кислорода находится в sp 3 - гибридном состоянии; из четырех гибридных орбиталей кислорода две участвуют в образовании одинарных связей О–H, а две другие sp 3 - гибридные орбитали заняты неподеленными электронными парами, их действие является причиной уменьшения угла от 109,28˚ до 104,5°.

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

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

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

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

1. Графическое представление молекул и их свойств - теория графов в химии

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

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

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

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

Инфракрасные спектры молекул

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

Исследование строения органических соединений с помощью физических методов

Всевозможные положения молекул в трехмерном пространстве сводятся к поступательному, вращательному и колебательному движению. Молекула, состоящая из N атомов, имеет всего 3N степеней свободы движения...

Квантовохимическое изучение фотофизических свойств полианилина

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

Макромолекули лінійних аморфних полімерів

Молекула - найдрібніша частинка речовини, що володіє її основними хімічними властивостями і складається з атомів, зєднаних між собою хімічними звязками. Молекули можуть відрізнятися між собою природою або кількістю атомів...

2.1 Описание измерения, составление его модели и выявление источников неопределенности Любой процесс измерения можно представить в виде последовательности выполняемых операций...

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

Если мерой неопределенности является суммарная стандартная неопределенность, то результат может быть записан так: у(единиц) при стандартной неопределенности uc(y) (единиц). Если мерой неопределенности является расширенная неопределенность U...

Развитие периодического закона. Зависимость свойства элементов от ядра его атома

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

Причем последние 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. Э. Беляев. Ленинград.