Применение теории графов в химии. Теория Графов в химии и нерешённые задачи

МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 2

Подготовил

Легкоконец Владислав, ученик 10А класса

Практическое применение Теории Графов

Руководитель

Л.И. Носкова, учитель математики

ст.Брюховецкая

2011 г.

1.Введение………………………………………………………………………….………….3

2.История возникновения теории графов………………………………………….………..4

3.Основные определения и теоремы теории графов……………………………….………6

4.Задачи,решаемые при помощи графов……………………………..……………………..8

4.1 Знаменитые задачи………………………………….………………………...8

4.2 Несколько интересных задач………………………………….……………..9

5.Применение графов в различных областях жизни людей……………………………...11

6.Решение задач……………………………………………………………………………...12

7. Заключение………………….…………………………………………………………….13

8. Список литературы………….……………………………………………………………14

9.Приложение…………………………………………………………………….…………15

Введение

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

Решение многих жизненных задач требует длинных вычислений, а иногда и эти вычисления не приносят успеха. В этом и состоит проблема исследования . Возникает вопрос: нельзя ли для их решения найти простое, рациональное, короткое и изящное решение. Упрощается ли решение задач, если использовать графы? Это определило тему моего исследования : «Практическое применение теории графов»

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

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

Задачи исследования:

1.Изучить литературу и ресурсы сети Интернет по данной проблеме.

2.Проверить эффективность метода графов при решении практических задач.

3. Сделать вывод.

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

В работе используются следующие методы: наблюдение, поиск, отбор, анализ.

История возникновения теории графов

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года.

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

[Приложение рис.1] Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [Приложение рис.2] , на котором A обозначает остров, а B ,C иD – части континента, отделенные друг от друга рукавами реки

По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал:

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A , B , C , D . Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Основные определения и теоремы теории графов

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

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

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

В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B , C , D . Иногда граф в целом будем обозначать одной заглавной буквой.

Определение 2. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.

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

Обозначение: O "– граф с вершинами, не имеющий ребер

Определение 4. Граф, в котором каждая пара вершин соединена ребром, называется полным.

Обозначение: U " – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n –угольник, в котором проведены все диагонали

Определение 5. Степеньювершиныназывается число ребер, которым принадлежит вершина.

Определение 6. Граф, степени всех k вершин которого одинаковы, называется однороднымграфомстепениk .

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

Определение 8. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.

Определение 9. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.

Понятия плоского графа и грани графа применяется при решении задач на "правильное" раскрашивание различных карт.

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

Определение 11. Цикломназывается путь, в котором совпадают начальная и конечная точка.

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

Определение 13. Длиной пути, проложенного на цикле, называется число ребер этого пути.

Определение 14. Две вершины A и B в графе называются связными(несвязными), если в нем существует (не существует) путь, ведущий из A в B .

Определение 15. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.

Определение 16. Деревомназывается связный граф, не содержащий циклов.

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

Определение 17. Несвязный граф, состоящий исключительно из деревьев, называется лесом.

Определение 18. Дерево, все n вершин которого имеют номера от 1 до n , называют деревом с перенумерованными вершинами.

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

Задачи решаемые при помощи графов

Знаменитые задачи

Задача коммивояжера

Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё обламывали зубы лучшие математики.

Постановка задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Метод решения задачи коммивояжера

Жадный алгоритм “иди в ближайший (в который еще не входил) город”.
“Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.
Рассмотрим для примера сеть на рисунке [приложение рис.3] , представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

Задача о Кенигсбергских мостах.

Задача формулируется следующим образом.
Город Кенигсберг расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Вопрос: можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту.
Мосты через реку Прегель расположены как на рисунке [приложение Рис.1].

Рассмотрим граф, соответствующий схеме мостов [приложение рис.2].

Чтобы ответить на вопрос задачи, достаточно выяснить, является ли граф эйлеровым. (Хотя бы из одной вершины должно выходить четное число мостов). Нельзя, прогуливаясь по городу, пройти по одному разу все мосты и вернуться обратно.

Несколько интересных задач

1. "Маршруты".

Задача 1

Как вы помните, охотник за мертвыми душами Чичиков побывал у известных помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжолго, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни одной из дорог Чичиков не проезжал более одного раза [приложение рис.4].

Решение :

По схеме дорог видно, что путешествие Чичиков начал с имения Е, а окончил имением О. Замечаем, что в имения В и С ведут только две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD ; перечеркнем DK . Перечеркнем МО и МН; отметим жирной линией MF ; перечеркнем FO ; отметим жирной линией FH , НК и КО. Найдем единственно возможный при данном условии маршрут. И получаем: имение Е – принадлежит Манилову, D - Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F - Бетрищеву, Н – Петуху, К – Констанжолго, О – Кошкареву [приложение рис.5] .

Задача 2

На рисунке изображена схема местности [приложение рис.6].

Передвигаться можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? Какой маршрут самый короткий и какой - самый длинный.

Решение :

Последовательно "расслаиваем" схему в дерево, начиная с вершины 1[приложение рис.7] . Получим дерево. Число возможных способов попадания из 1 в 9 равно числу "висячих" вершин дерева (их 14). Очевидно, кратчайший путь-1-5-9; самый длинный - 1-2-3-6-5-7-8-9.

2 "Группы, знакомства"

Задача 1

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

а) всего было передано четное число конвертов;

б) число участников, обменявшихся конвертами нечетное число раз, четно.

Решение: Пусть участники фестиваля А 1 , А 2 , А 3 . . . , А n – вершины графа, а ребра соединяют пары вершин, изображающих ребят, обменявшихся конвертами [Приложение рис.8]

Решение:

а) степень каждой вершины А i показывает число конвертов, которое передал участник А i своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа N = степ. А 1 + степ. А 2 + + . . . + степ. А n -1 + степ. А n , N =2p , где p – число ребер графа, т.е. N – четное. Следовательно, было передано четное число конвертов;

б) в равенстве N = степ. А 1 + степ. А 2 + + . . . + степ. А n -1 + степ. А n сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся конвертами нечетное число раз, четное.

Задача 2

Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто не сумел созвониться и поэтому не пришёл на встречу?

Решение:

Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д. Это первые буквы имён. Соединим те точки, которые соответствуют именам созвонившихся ребят.

[ приложение рис.9]

Из рисунка видно, что каждый из ребят – Андрей, Борис и Володя - созвонились со всеми остальными. Поэтому эти ребята и пришли к кинотеатру. А Галя и Даша не сумели созвониться между собой (точки Г и Д не соединены отрезком) и поэтому в соответствии с договорённостью в кино не пришли.

Применение графов в различных областях жизни людей

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

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

Молекулярные графы , применяемые в стереохимии и структурной топологии, химии кластеров, полимеров и др., представляют собой неориентированные графы, отображающие строение молекул [приложение рис.10] . Вершины и ребра этих графов отвечают соответственным атомам и химическим связям между ними.

Молекулярные графы и деревья: [приложение рис.10] а, б - мультиграфы соотв. этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).

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

Белковые сети

Белковые сети - группы физически взаимодействующих белков, которые функционируют в клетке совместно и скоординированно, контролируя взаимосвязанные процессы, происходящие в организме [приложение рис. 11].

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

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

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

Пример генеалогического дерева моей семьи [приложение рис.12].

Еще один пример. На рисунке показано библейское генеалогическое дерево [приложение рис.13].

Решение задач

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

Решение:

Для начала составим граф всех возможных путей проезда [приложение рис.14] , учитывая реальные дороги между данными населенными пунктами и расстояние между ними. Для решения этой задачи нам потребуется составить еще один граф, древовидный [приложение рис.15] .

Для удобства решения обозначаем города цифрами: Краснодар – 1, Крымск – 2, Темрюк – 3, Славянск – 4, Тимашевск – 5.

В результате вышло 24 решения, но нам нужны только кратчайшие пути. Из всех решений удовлетворяют только два, это 350 км.

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

Логическая задача на переливание. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Решение:

Ситуацию в каждый момент можно описать тремя числами [приложение рис.16].

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Заключение

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

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

С самого начала, на первом этапе, оно заключается в том, что нужно суметь проанализировать и закодировать условие задачи. Второй этап – схематическая запись, которая состоит в геометрическом представлении графов, и на этом этапе элемент творчества очень важен потому, что далеко не просто найти соответствия между элементами условия и соответствующими элементами графа.

Решая транспортную задачу или задачу на составление генеалогического дерева я сделал вывод, что безусловно метод графов интересен, красив и нагляден.

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

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

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

Литература

Берж К. Теория графов и ее применения. -M.: ИИЛ, 1962.

Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. -M.: ИИЛ, 1963.

Оре О. Графы и их применение. -M.: Мир, 1965.

Харари Ф. Теория графов. -M.: Мир, 1973.

Зыков А.А. Теория конечных графов. -Новосибирск: Наука, 1969.

Березина Л.Ю. Графы и их применение. -M.: Просвещение, 1979. -144 c.

"Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старинные занимательные задачи", М. "Наука", 1988(часть 2, раздел 8; приложение 4);

Приложение

Рис. 6

Рис. 7

Рис. 8

риложение

Приложение

Рис. 14

риложение

Приложение

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). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»

Изучение связи свойств веществ с их строением – одна из основных задач химии. Большой вклад в ее решение внесла структурная теория органических соединений, в число создателей которой входит великий российский химик Александр Михайлович Бутлеров (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 миллионов. Ее решение, по-видимому, будет найдено в результате использования составных топологических индексов.

Специальность ВАК РФ02.00.03
Количество страниц 410

Оглавление диссертации доктор химических наук Вончев, Данаил Георгиев

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

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

После опубликования фундаментальных трудов Шеннона и Винера по теории информации и кибернетики непрерывно усиливается интерес и к теopeтико-информационным методам исследования. Первоначальный смысл термина "информация" связан со сведениями, сообщениями и их передачей. Уто понятие быстро вышло из пределов теории связи и кибернетики и проникло в раз,личные науки о живой и неживой природе, обществе и познании. Процесс развития теоретико-информационного подхода в науке сложнее, чем формальный перенос кибернетической категории информации в другие области знания. Информационный подход - это не просто перевод с менее общих языков на метаязык. Он предлагает иной взгляд на системы и явления и позволяет получить новые результаты. Расширяя связи меж,ну различными научными дисциплинами, этот метод дает возможность найти полезные аналогии и общие закономерности между ниш. Развиваясь, современная наука стремится к все большей степени обобщения, к единству. В этом плане теория информации является одним из наиболее перспективных направлений

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

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

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

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

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

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

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

ГЛАВА 2. МЕТОД ИССЛЕДОВАНИЯ 2Л. ТЁОРЕЖО-ИНШРМАЦИОННШ МЕТОД 2.1.1» Введение

Информация является одним из самых фундаментальных понятий в современной науке, поняти«не менее общим,чем понятия вещество и Энергия. Этот взгляд находит обоснование в самих определениях информации. По Винеру^ "информация - это не материя и не энергия".

Эшби рассматривает информацию в качестве "меры разнообразия в данной системе". По Глушкову х "информация - это мера негомогенности в распределении пространства и времени". На этой основе сегодня все более осознается тот факт, что кроме вещественной и энергетической природы объекты и явления в природе и технике обладают также информационными свойствами. Некоторые прогнозы идут дальше,предсказывая, что центр научных исследований будет все более смещаться в сторону информационной природЫ процессов, которая, составит главный объект исследования в XXI веке. Эти прогнозы существенным образом основываются на возможности оптимального управления систем и процессов посредством информации, что,собственно? является главной функцией информации в кибернетике. В перспективе эти идеи могут привести к созданию технологий, в которых каждый атом и молекула будет управляем информацией,"" возможность^ нашедшая реализацию пока только в живой природе.

Возникновение теории информации обычно относится к 1948 году, когда Клод Шеннон опубликовал свой фундаментальный труд. Идея об информации, однако, как о величине,связанной с энтропией, является значительно старше. Еще в 1894 году Больцман установил, что любая информация, полученная о данной системе, является связанной с уменьшением числа ее возможных состояний и следовательно.увеличение энтропии означает "потерю информации". В 1929 году

Сциллард развил эту идею на общий случай информации в физике. ее кп

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

Возникшая как "специальная теорияобщения" теория информации быстро перерослаои первоначальные пределы и нашла применение в разнообразных областях науки и техники: в химии, биологии, медицине, лингвистике, психологии, естетике и др. Раньше всего была осознана роль информации в биологии. Выли решены важные вопросыязанные хранением, обработкой и передачей информации в живых организмах, в том числе, кодирование генетической информации 60-7? оценка возможности спонтанного самозарождения жизни на Земле^, формулировка основных законов биологической термодинамики^, анализ вопросов биоэнергетики и др. Информационное содержание объектов было использовано в качестве количественного критерия

А А А эволюции ". Выл поставлен вопрос об информационном характере процессов питания^®^^.

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

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

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

Кобозев с сотрудниками связали селективность и активность катализаторов с их информационным содержанием. Они также сформулировали оптимальные информационные условия характеризации и предсказания каталитических свойств. Формирование и рост крис

Ой. рп оо таллов были рассмотрены как информационный процесс ». Раков подвергнул информационному анализу обработку, катализаторных поверхностей различными химическими агентами.

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

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

Теоретико-информационные методы оказались полезными и в геохимии для характеризования честот распределения химических соединении в геохимических системах170» , для оценки степени сложности и для классификации этих систем

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

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

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

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

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

Проблема. связи, существующей между структурой и свойствами является другой областью успешного применения теоретико-информационного подхода в химии. Эффективность этого подхода будет показана в диссертационном труде для качественно различных структурных уровней в химии- электронных оболочек атомов, молекул, полимеров, кристаллов и даже атомных ядер^»^. Он может быть реализован как в качественном, так и в количественном аспекте. В первом случае на информационной основе могут быть дефинированы различные структурные правила, отражающие взаимное влияние двух и более структурных факторов. Возможно также получение количественных корреляций между информационными индексами и свойства?®. При этом в- принципе информационные индексы обеспечивают лучшие корреляции по сравнению с другими индексами, так как они отражают полнее осо-бености химических структур. Успешные корреляции возможны не только с величинами, прямо связанных с энтропией, но и с такими величинами, как энергия связи, чья связь с информацией далеко не очевидна. Здесь включаются свойства как отдельной молекула" или атома, но и их больших агрегатов, т.е. свойства, зависимые от взаимодействия между молекулами и атомами, а не только от их внутренной структуры. В дополнение., процессы в химии тоже могут быть предметом информационного анализа на основе изменения информационных индексов при взаимодействий.

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

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

В этой главе введены впервые теоретико-информационные индексы:,/ характеризующие электронную структуру атомов, а также новые информационные индексы о симметрии, топологии и электронной структуре молекул. Применение этих структурных характеристик рассмотрено в главе III, разделы IV.2 и V 1.

2.1.2. Необходимые сведения из теории информации

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

Понятие количества информации тесно связано с понятием энтропии в качестве меры неопределенности. В 1923 г. Хартли характеризовал неопределенность опыта с П различными исходами числом ¿од п. В статистической теории информации Шеннона^, опубликованной в 1948 г., количество информации определяется через понятие вероятности. Известно, что это понятие используется для описания ситуации, в которой существует неопределенность, связанная с выбором одного или нескольких элементов (исходов) из некоторого множества. Следуя Шеннону, мера неопределенности исхода X/ опыта X с вероятностью р(Х¡) -¿Оу(Х}) . Мера средней неопределенности полного опытаХ с Хц,Х2, ♦ возможными исходами, с вероятностями^ соответственно, р(Х4), р(Х2),. чр(Хп), является величина

Н(х) = - рсх,) Log p(Xi) сгл>

В статистической теории информации Н(Х)называется энтропией распределения вероятностей. Последние, в случае /7 различных исходов, образуют конечную вероятностную схемму, т.е.

Понятие вероятности может быть - определено более общим путем с точки зрения теории множеств. Пустьконечное множество, является разбиением А на /Т)класса в котором /\ непересекающиеся множества; по некоторому отношению эквивалентности X * Множество классов эквивалентности

R/X = (2.2; называется фактор-множеством R по X

Вероятностная функция Колмогорова (вероятностное соответствие) р подчиняется трем условиям:

Числовой ряд PfXf) , Р(Х2) , ., Р(ХГГ)) называется распределением разбиения Л, а функция Шеннона Н(X) из уравнения (2.1) выражает энтропию разбиения X

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

Количество информации X выражается величиной отстранённой неопределенности. Тогда средняя энтропия данного события со множеством возможных исходов равна среднему количеству информации, необходимому для выбора любого события X из множества ^ ,Х^,. и определяется формулой Шеннона (у-е 2.1):

I(x) = -K$Lp(x,-)logp(K) = Hw

Здесь К - положительная постоянная, определяющая единицы "измерения информации. Полагая К= 4 , энтропию (соответственно, информацию) измеряют в десятичных единицах. Наиболее удобная сис -тема измерения основывается на двоичных единицах (битах). В этом случае К ~ Щ2 и логарифм вур-и(2.4) берется при основании два и \-! обозначается для краткости через. Одна двоичная единица информации (или 1 бит) это количество информации, которое получается, когда станет известен результат выбора между двумя равновероятными возможностями, а единицах энтропии,¿.дгасГ\ переводным множителем является постоянная Вольцмана (1.38.10 yj.gra.d~разделенная на /а?Ю.

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

Как единичная, так и средняя информация всегда положительны. Это свойство связано с фактом, что вероятность всегда меньше единицы, а постоянная в уравнении (2.4) берется всегда положительной. Е|&кольку ^ У, то

13 р(х,-) = Н(х,о с2.5) и неравенство это сохраняется и после усреднения.

Среднее количество информации для данного события (опыта) X достигает максимум при равномерном распределении вероятностей р(Х,) -р(Х2)= . . .=р(Хп)* т.е. при р(Х}) для любого П:

Для пары случайных зависимых событий X и у среднее количество информации тоже выражается формулой Шеннона:

1(ху> = - р(х,yj) № pix, yj) (2.7)

Уравнение (2.7) можно обобщить для любого конечного множества, независимо от природы его элементов:

1(ху) = -Z Z. P(X,nYj) 16P(X-,nYj) (2.8) являются двумя фактормножествами Р по двум различным реляциям эквивалентности х и у, а К/ху - фактором-множеством сечений X; и:

Записав совместную вероятностьв уравнении (2.7) в виде произведения безусловной и условной вероятности р(х;,у^ = p(><¡)"P(Уj/x¡) , и представив логарифм в виде сумш»получается уравнение:

1(Ху) = 1(Х) ч- 1(у/Х) (2.9) в котором Т(х/у) это среднее количество условной информации, содержащейся в у относительно х, и дается выражением:

1(у/Х) = -У р(Х,у1) 1В р(У;/Х-,) (2.10)

Определяя функцию:

1(Х,у.! = 1(У> - 1(у/Х) (2-Ш и замещая ее в уравнении (2.9):

1(ху) - 1(Х) + 1(у) -1(х,у) (2.12) становится ясным, чтоТ(Х,у) выражает отклонение информации о сложном событии (Х,у") от аддитивности информации об индивидуальных событиях (исходах): х и у. Поэтому Г(Х,У) является мерою степени статистической зависимости (связи) между X и у.В силе также равенство: 1(Х,У) - 1(ух) (2.13) которое характеризует связь между X и у3 симметричном виде.

В общем случае дл^ статистической связи между х и у и средним количеством безусловной информации относительно X или у в силе следующие неравенства: т!1(х>

Равенство в силе, когда второй член в уравнении (2.11) ноль, т.е. когда каждому / соответствует I , для которого р(у. ¡Х})=

Если величины X ж у независимы, т.е. если в уравнении (2.12) Т(Х,у) =0 , то

1(ху) =1(Х) <2Л5>

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

1(х„х2,.,хп) = 11 1(х/) (2.16)

Известны также и невероятностные подходы к количественному определению информации. Ингарден и Урбаникх предложили ак-сиоштичеснов/сизвдэдение- шеьйновской информации без вероятностей, в виде функции конечных булевых колец. Значительный интерес составляет предложенная Колмогоровым^^ эпсилон-энтропия (комбинаторный подход) и особенно алгоритмическое определение количества информации. По Колмогорову количество информации, содержащееся в одном объекте (множестве) относительно другого объекта (множества) , рассматривается в качестве "минимальной длины" программ, записанной в виде последовательности нолей и единиц, и позволяющей однозначног преобразование; первого объекта во второй:: = Н(Х/у) = Ш "Ш I (Р) (2-17)

Алгоритмический подход Колмогорова предлагает новые

17 логические основы теории информации на основе понятий сложность и последовательность,такча&Йн-понятия "энтропия" и "количество информации" оказались применимыми к индивидуальным объектам.

Невероятностные методы в теории информации расширяют содержание понятия количества информации от количества уменьшенной неопределенности к количеству уменьшенного однообразия или к количеству разнообразия в согласии с трактовкой Эшби. Любое множество вероятностей, нормированное к единице, можно рассматривать соответным некоторому множеству элементов, азбладающеш^разнообразием. Под разнообразием подразумевается характеристика элементов множества, заключающаяся в их различии, несовпадении по отношению к некоторой реляции эквивалентности. Эт@ может быть совокупность" различных элементов, связей, отношений, свойств объектов. Наименьшая единица информации, бит, при этом подходе выражает минимальное различие, т.е. различие двух объектов, которые нетождественны, различаются по некоторым свойством.

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

Пусть в данной структуре содержатся А/ элементов и они распределены по некоторому критерию эквивалентности в подмножествах эквивалентных элементов: . Этому распределению соответствует конечная вероятностная схема подмножества вероятности ^ рп р2> . . ?Рп элементы

2.18) где ¿Г -Л/"и является вероятностью одного; случайно) выбранного элемента попасть в / - тое подмножество, у которого А/,-элементов. Энтропию Н распределения вероятностей элементов этой структуры, определенную по уравнению (2.4), можно рассматривать/ в качестве меры среднего количества информации, I, которое содержится в одном элементе структуры: - п

1и Р/ , бит на элемент (2.19)

Общее информационное содержание структуры дается уравнением^ производным (2.19):

1-М1-А//0/ч-хнмм, <*.»>

В литературе нет единого мнения о том, как называть величины, определенные посредством у-ий (2.19) и (2.20). Некоторые авторы предпочитают называть их соответственно средним и общим информационным содержанием. Так, согласно Моушовитцу^, I не является мерой энтропии в смысле, в котором она используется в теории информации, как как не выражает среднюю неопределенность структуры, состоящей из/\/ элементов, в ансамбле всех возможных структур, обладающих;:тем же самым:числом элементов. I является скорее информационным содержанием рассматриваемой структуры по отношению к системе трансформаций, оставляющих систему инвариантной. Согласно Решг из уравнения (2.4) измеряет количество информации после эксперимента, а до него Н(х) мера энтропии, связанной с неопределенностью эксперимента. По нашему мнению, "эксперимент", уменьшающий неопределенность химических структур (атомов, молекул и т.д.), это сам" процесс формирования этих структур из их несвязанных элементов. Информация находится здесь в связанной форме, она содержится в структуре, и поэтому часто используется термин "информационное содержание" структуры.

Концепция структурной информации, основанной на приведенной интерпретации1 уравнений (2.19) и (2.20), согласуется хорошо с идеями Эшби о количестве информации как количестве разнообразия. Когда система состоит из одинаковых элементов, в ней нет никакого разнообразия. В ©том случае в у-ях (2.19) и (2.20)/="/

При максимальном разнообразии элементов в структуре Л£ = / и информационное содержание структуры максимальное:

4«* -N16 и, Т^^вИ

2.1.3. Теоретико-информационные индексы для характериэацж электронной структуры атомов химических элементов