МУНИЦИПАЛЬНОЕ АВТОНОМНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 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

риложение

Приложение

Причем последние 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В - Р + Г = 1, (*)

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

Доказательство. Докажем, что равенство не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ (рис. 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. Э. Беляев. Ленинград.

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

УДК 547.12:541.14(083.73)

ХИМИКУ - О ТЕОРИИ ГРАФОВ: ГРАФЫ В ХИМИЧЕСКОЙ НОМЕНКЛАТУРЕ

Bryuskc Y.E. To the chemist about graph theory: Graphs in the chemical nomenclature. The author addresses this article on different issues of graph theory and the role of graphs in the chemical nomenclature to chemists.

Монография специально посвящена применению графов в химии. Из трех ее разделов наибольший интерес для изучаемой темы представляет раздел «Графы в структурной химии» . А химику, не знающему ничего о графах, достаточно эффективную помощь может оказать приложение [ 1 г]. Наверно, для химиков подойдут еще монографии . А для ознакомления с современным состоянием теории графов подойдет трудная, по-видимому, для нематематика, как и некоторые другие книги по теории графов, книга .

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

1. МОЛЕКУЛЯРНЫЕ ГРАФЫ

Так что такое граф? Это множество точек (непустое и, обычно, конечное) с соединяющими некоторые из них (иногда ни одной, а иногда - все) линиями (здесь и далее необходимые определения и термины выделены полужирным курсивом). Посмотрев на рис. 1, химик скажет, что это - углеродные скелеты этана, бутана, изобутана и циклобутана. А то, что они нарисованы по-разному, не имеет здесь значения. А у циклобутана точки можно и не ставить, как делают это химики, рисуя, например, молекулы циклогексана, бензола и его аналогов (см., напр., рис. 2г и ). Так, вот, подобным графам-скелетам дали название молекулярных графов (МГ). . Еще осталось добавить, что в теории графов точки наиболее часто называют вершинами, а соединяющие их линии - ребрами. Какие еще особенности графов и, соответственно, МГ необходимо отметить. Для графа «безразлично», как пара его вершин соединена ребром, важно только знать, есть оно или нет. Поэтому графы с кратными ребрами называют мулыниграфами. И, таким образом, мультиграфы представляют здесь МГ с двойными или (и) тройными связями (рис. 2). Но не будем добавлять к ним термина «мультиграфы»; так в последнее время поступают и в самой теории графов (см. ).

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

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

Рис. 1. МГ этапа (а), бутана (б, в), изобутана (г, д) и циклобутана (е, ж)

Рис. 2. МГ с кратными связями (ребрами): бутена-1 (а), бутена-2 (б), метилпропена (в) и циклогексена (г)

Дадим теперь более общее определение графа, несколько измененное по сравнению с .

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

Такое определение (конечно, в более строгой математической форме) имеется, очевидно, во всех книгах по теории графов. Оно показывает, что в графе обычно отвлекаются от качественного различия между вершинами и ребрами. Для конкретного графа важно только, есть ли в нем эта вершина-объект (углеродный атом), а также есть ли ребро-отношение (связь) или нет его между этой парой вершин (атомов). Однако это далеко не всегда так! И когда это не так, то появляются мультиграфы (см. выше) и их усложнение псевдографы (в них ребро соединено с одной и той же вершиной в виде петли), помеченные (пронумерованные) графы, раскрашенные, ориентированные (орграфы), взвешенные графы и другие. Определение таких графов почти всегда включает слова: «Граф, который... (у которого...)». Эти же слова можно было бы поставить и перед определением МГ (см. выше).

1.1. СТРУКТУРА ГРАФА

Что еще нужно знать химику о графах (МГ)?

Вершины графа, соединенные ребром, называются смежными, соединенные вершина и ребро называются инцидентными. Число инцидентных одной и той же вершине ребер называется ее степенью или валентностью. Оба варианта почти равноправны в самой теории графов , а «один из основателей современной теории графов» У. Татт в своей книге применяет только термин «валентность» и пишет что «Термин “валентность” навеян химическими аналогиями». Поэтому здесь применение этого термина тем более оправдано. Вершины, не имеющие ребер (например, МГ метана), называются изолированными, валентности 1 - висячими, валентности 2 -двухвалентными (обычно в МГ таких вершин большинство), валентности 3 и 4 - узловыми. А в МГ их соответственно стоит называть первичными, вторичными (неузловые), третичными и четвертичными вершинами или же углеродными атомами, как называют их химики.

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

Следуя этому подходу, удалим среднюю связь из МГ бутана (рис. 16). Оставшееся - подграф. Но «добраться» от одного конца этого графа до другого по связям невозможно, хотя «в память» об МГ бутана этот подграф - один граф. В теории графов такие графы называются несвязными, а его связные части - компонентами. Если «присмотреться» с химической точки зрения, то полученный так подграф МГ бутана состоит из двух МГ этана (см. рис. 1а). А связный граф, таким образом, состоит из одной компоненты. Граф, состоящий из одних изолированных вершин (см. выше), на-

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

1.2. ЦЕПИ И ЦИКЛЫ

На рис. 1 и 2 видно, что в графе (МГ) почти всегда имеется последовательность чередующихся атомов и связей. Такая последовательность в графе называется цепью. Но число ее «звеньев» в МГ будем считать не по числу ребер-связей, как принято в теории графов, , а по числу вершин-атомов. В теории графов у графа этана, рис. 1а одно звено; у МГ того же этана будем считать два звена, а одно - в МГ метана. В теории графов у графа-точки метана нет звеньев. А в химии важнее знать число атомов в цепи по сравнению с числом связей между ними. Рассматривая так МГ изобутана (рис. 1г), следует считать его состоящим из двух цепей. Более длинная цепь состоит из трех вершин-атомов, более короткая - из одной.

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

Цепь превращается в цикл, если соединить ее начало и конец новой связью.

На рис. 3 показан ациклический МГ (а) с двумя цепями: 1-5 и 6, 7. На этом же рисунке показано, что МГ нафталина (б) и спироундекана (в) содержат по два простых конденсированных цикла, имеющих общие атомы. У МГ нафталина таких атомов два: 5 и 10, а у МГ спироундекана - один, 6. У дифенила циклы разобщены: связь 7, 6 не входит ни в один из них.

10______И 1________________?

Рис. 3. Нумерованные МГ: 3-этилпентана (а), нафталина (б), спироундекана (в) и дифенила (г). В МГ‘ б и г ароматичность циклов не обозначена

1.2.1. БЛОКИ, ТОЧКИ СОЧЛЕНЕНИЯ, МОСТЫ

В теории графов выделяют такие графы, которые становятся несвязными только после удаления более чем одной вершины. Такой граф имеет название блок. МГ циклогексена, рис. 2г, и нафталина, рис. 3 - блоки, а МГ спироундекана не является блоком, так как для того, чтобы сделать его несвязным, достаточно удалить одну вершину 6. Она называется точкой сочленения. В МГ дифенила две точки сочленения - 6 и 7. А удаление ребра, соединяющего эти точки, также приводит к несвязному графу. Такое ребро имеет название мост или перешеек, в структуру циклов эти ребра не входят. Рассматривать ациклический граф в этом аспекте нет смысла, так как в нем все ребра являются мостами, а все вершины, кроме висячих - точками сочленения. Конденсированные циклы, даже имеющие точку сочленения, в органической химии относят к цельной циклической системе, а циклы, разделенные хотя бы одним мостом, являются отдельными системами (в номенклатуре - ансамбли циклов).

1.2.2. ГАМИЛЬТОНОВ ЦИКЛ

В МГ простых циклов имеется замкнутая цепь, содержащая все атомы цикла. Название такого цикла -гамильтонов цикл (не «гамильтоновый»). Кроме простых гамильтонов цикл имеется во многих конденсированных циклах, например, в МГ нафталина, рис. 36. В МГ рис. Зв и Зг цепи содержат все атомы МГ, но не замкнуты в циклы. Такая цепь называется гамильтоновой цепью. Гамильтонова цепь имеется в МГ нормального углеводорода, например, бутана (рис 16, в).

1.2.3. ДЕРЕВЬЯ. ЦИКЛИЧЕСКИЙ РАНГ

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

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

с =

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

циалисту по теории графов, но и химику. Химическим аналогом этой формулы является формула (2)

с= 1/2р3+/?4+ 1, (2)

где Рз - число третичных, а р4 - число четвертичных углеродных атомов.

1.3. ИЗОМОРФИЗМ И ИЗОМЕРИЯ

Весьма важный аспект изоморфизма, общий для теории графов и органической номенклатуры, в теории графов обычно рассматривают вначале. «Невольно» он и отражен здесь в первом же рисунке. На вопрос, идентичны ли пары МГ бутана (16, в), изобутана (1 г, д) и циклобутана (1е, ж), химик ответит «да», а в теории графов ответят «нет». Ответ будет: они изоморфны. Изоморфизм - это отношение эквивалентности на графах , , одним из вариантов которого может быть их идентичность (равносильность), если их можно совместить, не изменяя одного из рисунков. Автор книги по основам современной номенклатуры органических соединений показывает , что можно преобразовывать для совмещения различные формы одной и той же молекулярной структуры (углеродного скелета), а также и то, как можно попыткой подобного совмещения убедиться в том, что сравниваемые структуры не совмещаются и представляют изомерные молекулы, отличающиеся различным порядком связей (структурная изомерия) и не являющиеся, конечно, изоморфными [Там же, с. 43, 44]. Таким образом, изомерные графы так же как и изомерные МГ, описывающие изомерные молекулы, являются неизоморфными графами, имеющими вершины с одним и тем же заданным распределением валентностей. Такие графы и именно в качестве изомерных МГ начали изучать еще в конце XIX века , однако химический термин «изомерные» они получили в теории графов, по-видимому, только в самое последнее время , . Изомерия графов (МГ) соответствует только структурной изомерии молекул и не включает оптическую, конформационную и другие химические виды изомерии, хотя, аналогично перспективным МГ (см. ниже п. 2.2.), образованы еще специальные виды МГ, отражающие эти и другие аспекты структурной химии .

1.3.1. ПРОБЛЕМА ИЗОМОРФИЗМА

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

Рис. 4. Изоморфные МГ углеводорода СцНм

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

2. ПЛАНАРНОСТЬ 2.1. УКЛАДКИ

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

2.2. НЕПЛАНАРНОСТЬ И ДВУДОЛЬНЫЕ ГРАФЫ

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

Любой, даже поверхностно знающий теорию графов, сразу определит, что рис. 56 представляет одну из

Рис. 5. Полный двудольный граф Кз,з, соответствующий МГ диагонального изомера бензола

двух форм наименьшего непланарного графа, так называемый полный двудольный граф А"з-3. Это такой граф, в котором каждая вершина из одной группы (группа (1, рис. 56) соединена со всеми вершинами другой группы (/, рис. 56) и наоборот. Если связи есть не со всеми вершинами другой группы, граф будет просто двудольным, но основной его признак - отсутствие связей внутри группы - не должен нарушаться.

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

2.3. ТОПОЛОГИЧЕСКАЯ СВЯЗНОСТЬ

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

2.4. ВНЕШНИЙ ЦИКЛ

Есть еще один вопрос, ответ на который химики обходят молчанием. Только для трех из пяти правильных выпуклых многогранников можно в принципе синтезировать химические аналоги: тетраэдран (С4Н4), кубан (С8Н8) и додекаэдран (С|2Н12). Почему единственный, по-видимому, синтезированный из них углеводород кубан, имеющий, конечно, шесть граней-циклов, в современной органической номенклатуре называется пентациклооктан , . Частично ответ на это дан выше (циклома-тическое число МГ). Но полный ответ, существенный для органической химии и для органической номенклатуры как ее важной части, дает знаменитая теорема Эйлера, которую знает, пожалуй, любой математик. Она формулируется так : для любого полиэдра, расположенного на сфере и имеющего V точек

Рис. 6. Перспективное изображение (перспективный МГ) кубана (а) и его МГ (уложенный на плоскости - б)

(вершин), Е линий (ребер) и ^ граней (грань ограничена циклом),

У - Е + Е = 2.

Куб здесь не уложен на поверхность сферы, на ней находятся только его вершины-точки. Если оставить такой куб без сферы, то получится рис. 6а; если уложить его на сфере, то его грани (внутренние области простых циклов) займут ее всю, а если же уложить его на плоскости, то получится рис. 66. Посчитаем в нем число циклов (простых). Получим пять (пента). А куда делся цикл 1238? В него теперь вложены остальные пять циклов, он перестал быть простым, и ни в теории графов, ни в органической номенклатуре теперь как бы не считается, что и отражает формула 1. Почему «как бы»? По аналогии со сферой, в теории графов считается, что циклу 1238 «принадлежит» вся бесконечная «часть» плоскости, которой при укладке МГ рис. 6 на сфере соответствует конечная часть ее внутренней поверхности. Поэтому у уложенного на плоскости не только многогранника, но и любого плоского МГ цикл, внутри которого находятся все остальные циклы, назван внешним циклом, а соответствующая ему бесконечная «часть» плоскости - внешней гранью. А формула (3), отличающаяся от формулы (1) «только» единицей, и отражает «добавление» внешнего цикла в любой планарный МГ. И, таким образом, шестигранный кубан правильно назван в номенклатуре пентацикл ооктаном.

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

2.5. ПЕРСПЕКТИВНЫЕ МГ

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

Рис. 7. Структурная формула (а), МГ (б) и перспективный МГ (в) бициклического углеводорода

пространственное расположение системы вершин и соединяющих их ребер, но здесь целесообразно поступить, как в , где приведены перспективные МГ (ПМГ). Если необходимо будет отличать их от «настоящих» планарных МГ, можно называть, как указано выше. В отмеченной выше большой монографии по насыщенным (ациклическим и циклическим) углеводородам приведены 253 рисунка циклических углеродных скелетов. Из них 136 являются планарными (почти все плоские) МГ, а остальные 117 представляют собой упомянутые выше перспективные МГ. На рис. 7 показано, как они же демонстрируют «превращение» структурной формулы в плоский МГ, а его - в МГ перспективный . Довольно много подобных перспективных МГ приводится в упомянутом выше учебнике органической химии .

Интересно немного «пристальнее» рассмотреть МГ рис. 7в. Так же, как и у перспективного изображения кубана (рис. 6а), у него перспективное изображение освобождает внешний семичленный цикл от вложения в него других циклов и придает ему равные «права» с другими циклами. Однако это далеко не всегда так. Если циклы сконденсированы по одному (рис. Зв) или по двум атомам (рис. 36), то перспективное изображение не приведет к освобождению внешнего цикла, хотя любой из шестичленных циклов в каждом из этих МГ можно сделать внешним, вложив в него другой. А у моноциклического МГ цикл «сам себе» внешний и второй цикл в перспективном изображении у него, конечно, не появится.

3. СИММЕТРИЯ

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

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

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

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

4. НУМЕРАЦИЯ

Упомянутая выше (§ 3) одинаковость атомов углерода в МГ уменьшает информативность о структуре молекулы, вследствие уменьшения разнообразия составляющих ее частей. Давно известным и применяющимся во всех вариантах органической номенклатуры способом увеличения информативности является нумерация атомов молекулы (и ее МГ). В теории графов такие графы называются помеченными («метить» можно не только числами). Нумерация атомов позволяет получить необходимую информацию о порядке связей в молекуле и в МГ, для чего достаточно, например, указать номера непосредственно связанных атомов. Выше (рис. 3 и 6) были приведены нумерованные МГ. Уже там эта нумерация увеличила информативность о них и облегчила пояснения, приведенные в тексте. А на рис. 7а показана нумерация углеродных атомов структурной формулы конденсированного углеводорода, которая применяется в современной органической номенклатуре.

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

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

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

4.1. ИЗОМОРФИЗМ НУМЕРОВАННЫХ МГ

Для того чтобы нумерованные графы (МГ) считались изоморфными, необходимо, чтобы при совмещении равносильных (см. п. 1.3) МГ совпали не только атомы (вершины) и связи, но и номера. На рис. 8 приведены знакомые нам (рис. 1) МГ бутана и изобутана. Видно, что все они пронумерованы по-разному. Но МГ 8а и 86 можно совместить вместе со всеми номерами, повернув один из них на 180°, но ни один из этих двух никаким перемещением не удастся совместить с МГ рис. 8в. Таким образом, нумерованные МГ 8а, 86 изоморфны, а МГ 8в не изоморфен ни одному из них, хотя при отсутствии нумерации изоморфными были бы все три. Произошло это потому, что у МГ 8а и 86 одинаковыми номерами помечены симметричные атомы, а у МГ 8в - нет. У нумерованных МГ изобутана с совпадением всех номеров можно совместить любую пару из тройки рис 8г, 8д и 8е, так как все три первичных атома симметричны, а единственный несимметричный третичный атом помечен одним и тем же номером. А в МГ 8ж несимметричный атом помечен другим номером, и этот МГ не удастся совместить ни с одним из МГ тройки 8г, 8д, 8е.

Рис. 8. Различные нумерации МГ бутана (а - в) и изобутана (г-ж)

Сопоставим списки связей для этих МГ. Пара МГ 8а, 86 имеет одинаковые списки: 1,2 - 2,3 - 3,4, а у МГ 8в список другой: 1,2 - 2,4 - 3,4. Также у тройки МГ 8г, 8д, 8е идентичные списки связей: 1,2 - 2,3 - 2,4, а список у МГ 8ж также другой: 1,2 - 1,3 - 1,4.

Изложенное выше приводит к трем основным следствиям.

Первое. Однозначно пронумерованные изоморфные графы (МГ) остаются изоморфными и в результате такой нумерации. Конечно, для этого нужно применить одну и ту же систему правил однозначной нумерации.

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

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

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

4.2. ЦЕПНАЯ НУМЕРАЦИЯ

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

Таким образом, цепных связей в нумерованном МГ больше, чем нецепных (см. рис. 3, 6, 7 и 8), и объем числового представления МГ можно значительно уменьшить, если считать все цепные связи заведомо существующими. Кроме того, наличие в записи наибольшего номера атома (последний номер) однозначно

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

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

рис. За: 06,3-7; 36: 10,1 - 10,5;

Зв: 6,1 - 11,6; Зг: 6,1 - 12,7; рис. 6а и 66: 5,2 - 6,1 - 7,4 - 8,1 - 8,3; рис. 8а и 86: 4; 8г, 8д и 8е: 04,2.

Таким образом, линейно-цепной код МГ состоит из сообщений с разделительными знаками , содержащих информацию о нецепных связях, разделительным знаком является дефис (тире) с пробелами. Сообщение о последнем атоме дают тогда, когда его номер не находится в нецепной связи (коды рис. За и 8а, 86). Поскольку все цепные связи в коде считаются существующими, прямую информацию об отсутствии некоторых из них дают «незначащим» нулем непосредственно перед номером, с которого начинается новая цепь (начальный номер: коды рис. За и 4г, 4д, 4е). Сообщения, в которых нецепные связи образованы одним и тем же большим или меньшим (но не большим и меньшим) номером, объединяют в одно. В объединенном сообщении больший общий номер помещают на первое место, располагая другие номера после него в возрастающем порядке: рис. 36: 10,1,5;

рис. 6а и 66: 5,2 - 6,1 - 7,4 - 8,1,3.

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

Для обеспечения ввода информации об органической молекуле в ЭВМ были разработаны другие самостоятельные системы кодирования структурных формул , . Линейная запись цепного кода МГ также вполне пригодна для непосредственного ввода в ЭВМ.

К упомянутому выше разнообразию способов однозначной нумерации атомов МГ добавлена однозначная цепная нумерация. По аналогии с канонической нумерацией по матрице смежностей (см. выше § 4) она названа цепной канонической нумерацией . В ней нумерацию начинают с атомов более длинных цепей; и выбирают такой ее порядок, при котором связи с непоследовательными номерами своих атомов получают максимально возможные такие номера. В качестве

Рис. 9. Перепроектирование МГ (а) в МГ с большим внешним циклом (б или в) при помощи канонической цепной нумерации

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

Теперь появилась возможность описать получение укладки МГ с наибольшим внешним циклом из МГ рис. 4а. Здесь видно, что внутренний шестичленный цикл больше внешнего пятичленного. Нарисовав шестичленный цикл 3, 4, 5, 6, 7, 8 внешним, помечаем его этими же номерами (рис. 96). Затем присоединяем к нему внутренние атомы, соблюдая тот же порядок номеров связей. Внутри пятичленного цикла рис. 9а есть еще один шестичленный цикл 1, 2, 3, 4, 5, 11. Нарисовав его внешним и присоединив к нему внутренние атомы, получим МГ рис. 9в. Цепная каноническая нумерация всех циклов рис. 9 дает один и тот же код: 8,3 - 9,2 - 10,7 - 11,1,5, что и доказывает изоморфность всех этих МГ.

ЛИТЕРАТУРА

1. Применение теории графов в химии / Под ред. чл.-кор. АН СССР Н.С. Зефирова и канд. хим. наук С.И. Кучанова. Новосибирск: Наука, 1988. 306 с.

а: Станкевич И.В. Графы в структурной химии. С. 7-69. б: Яблонский Г.С.. Евстигнеев В.А., Быков В.И. Графы в химической кинетике. С. 70-143.

в: Кучанов С.И.. Королев С.В.. Потоков С.В. Графы в химической физике полимеров. С. 144-299.

г: Королев С.В., Кучанов С.И. Приложение. Понятия теории графов. С. 300-305.

2. Харари Ф. Теория графов. М.: Мир, 1973. 302 с.

3. Уичсон Р. Введение в теорию графов. М.: Мир, 1977. 208 с.

4. Оре О. Графы и их применение. М.: Мир, 1965. 176 с.

5. Березина Л.Ю. Графы и их применение: Пособие для учителей. М.: Просвещение, 1979. 144 с.

6. Дистель Р. Теория графов: Пер. с англ. О.В. Бородина. Новосибирск: Изд-во Ин-та математики, 2002. 336 с.

7. Татт У. Теория графов: Пер с англ. Г.П. Гаврилова. М.: Мир, 1988. 424 с.

8. Бенкс Дж. Названия органических соединений. М.: Химия, 1980. 304 с.

9. Шилов A.A. О систематизации графов на основе разбиений // Методы и средства работы с документами: Сб. тр. Ин-та системного анализа РАН. М.: Эдиториал УРСС, 2000. 376 с.

10. Шилов A.A. О систематизации безреберных и объединенных графов на основе разбиений // Управление информационными потоками: Сб. тр. Ин-та системного анализа РАН. М.: Едиториал УРСС, 2002. 368 с.

11. Терентьев А.П., Кост A.H.. Цукерман A.M.. Потапов В.М. Номенклатура органических соединений. Обзор, критика, предложения. М.: Изд-во АН СССР, 1955. 304 с.

12. Шилл Г. Катенаны, ротаксаны и узлы. М.: Мир, 1973. 212 с.

13. Кларк Т.. Мак Керви М.А. Насыщенные углеводороды II Общая органическая химия."Г. I. М.: Химия, 1981. С. 56-168.

14. Нейпанд О.Я. Органическая химия. М.: Высш. шк., 1990. 752 с.

15. Гудман С., Хидетниеми С. Введение в анализ и разработку алгоритмов. М.: Мир, 1981. 368 с.

16. Липский В. Комбинаторика для программистов. М.: Мир, 1988. 216с.

17. Брюске Я.Э. Цепная нумерация и кодирование циклических углеводородов // Ж. структурной химии. Т. 36. № 4. С. 729-734.

18. Математический энциклопедический словарь. М.: Совет, энциклопедия, 1988. 848 с.

19. Брюске Я.Э. Линейно-цепное кодирование и названия ациклических углеводородов // Вестн. Тамбов, ун-та. Сер. Естеств. и техн. науки. Тамбов, 1996. Т. 1. Вып. 1. С. 34-38.

20. Брюске Я.Э. Линейно-цепное кодирование формул органических соединений. VIII. Увеличение явной информативности о структуре в кодах углеводородов // Вестн. Тамбов, ун-та. Сер. Естеств. и техн. науки. Тамбов, 2000. Т. 5. Вып. I. С. 38-43.

• Специальность ВАК РФ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. Теоретико-информационные индексы для характериэацж электронной структуры атомов химических элементов

Рекомендованный список диссертаций по специальности «Органическая химия», 02.00.03 шифр ВАК

• Асимптотические задачи комбинаторной теории кодирования и теории информации 2001 год, кандидат физико-математических наук Виленкин, Павел Александрович 2011 год, кандидат физико-математических наук Шуткин, Юрий Сергеевич

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