Графы и химия. Графов теория

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

Е. Бабаев.   Кандидат химических наук.

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

Возьмём, например, четыре точки, произвольно расположенные на плоскости или в пространстве, и соединим их между собой тремя чёрточками. Как бы ни были расположены эти точки (называемые вершинами) и каким бы образом ни соединяли их между собой черточками (называемыми ребрами), мы получим лишь две возможные структуры-графа, различающиеся между собой взаимным расположением связей: один граф, похожий на буквы "П" или "И", и другой граф, похожий на буквы "Т", "Э" или "У". Если же вместо четырёх абстрактных точек взять четыре атома углерода, а вместо черточек – химические связи между ними, то два указанных графа будут соответствовать двум возможным изомерам бутана – нормального и изо-строения.
      Чем вызван всё нарастающий интерес химиков к теории графов, этому причудливому, но весьма простому языку точек и чёрточек?
      Граф обладает тем замечательным свойством, что он остаётся неизменным при любых деформациях структуры, не сопровождающихся разрывом связей между её элементами. Структуру графа можно исказить, полностью лишив её симметрии в обычном понимании; тем не менее, у графа останется симметрия в топологическом смысле, определяемая одинаковостью, взаимозаменяемостью концевых вершин. Учитывая эту скрытую симметрию, можно, например, предсказать число различных изомерных аминов, получаемых на основе структур бутана и изобутана заменой атомов углерода на атомы азота; графы позволяют использовать простые физические соображения и для понимания закономерностей типа "структура – свойство".
      Другая, несколько неожиданная идея – выражать с помощью чисел структурные качества графов (например, степень их разветвлённости). Интуитивно мы чувствуем, что изобутан более разветвлён, чем нормальный бутан; количественно это можно выразить, скажем, тем, что в молекуле изобутана трижды повторяется структурный фрагмент пропана, а в нормальном бутане – лишь дважды. Это структурное число (называемое топологическим индексом Винера) удивительно хорошо коррелирует с такими характеристиками предельных углеводородов, как температура кипения или теплота сгорания. Последнее время появилась своеобразная мода на изобретение различных топологических индексов, их уже набралось более двадцати; манящая простота делает этот пифагорейский метод всё более популярным * .
      Использование теории графов в химии не ограничивается лишь структурой молекул. Ещё в тридцатые годы А. А. Баландин, один из предшественников современной математической химии, провозгласил принцип изоморфного замещения, согласно которому один и тот же граф несёт единую информацию о свойствах самых разнородных структурированных объектов; важно лишь чётко определить, какие именно элементы выбираются в качестве вершин и какие именно отношения между ними будут выражаться рёбрами. Так, помимо атомов и связей в качестве вершин и рёбер можно выбрать фазы и компоненты, изомеры и реакции, макромолекулы и взаимодействия между ними. Можно подметить глубокое топологическое родство между правилом фаз Гиббса, стехиометрическим правилом Хориути и рациональной классификацией органических соединений по степени их ненасыщенности. С помощью графов успешно описываются взаимодействия между элементарными частицами, срастание кристаллов, деление клеток... В этом смысле теория графов служит наглядным, практически универсальным языком междисциплинарного общения.

Развитие каждой научной идеи традиционно проходит ступени: статья – обзор – монография – учебник. Соцветье идей, именуемое математичесой химией, уже миновало стадию обзоров, хотя ещё и не достигло статуса учебной дисциплины. Ввиду разнообразия направлений, основной формой публикаций в этой области сейчас служат сборники; несколько таких сборников увидели свет в 1987-1988 гг.
      Первый сборник под редакцией Р. Кинга – "Химические приложения топологии и теории графов" (М., "Мир", 1987) – содержит перевод докладов международного симпозиума с участием химиков и математиков разных стран. Книга даёт полноценное представление о пёстрой палитре подходов, возникших на стыке теории графов и химии. В ней затронут весьма широкий круг вопросов – начиная от алгебраической структуры квантовой химии и стереохимии, магических правил электронного счёта и кончая структурой полимеров и теорией растворов. Химиков-органиков, без сомнения, привлечёт новая стратегия синтеза молекулярных узлов типа трилистника, экспериментальная реализация идеи молекулярного листа Мёбиуса. Особый интерес вызовут обзорные статьи по использованию уже упоминавшихся выше топологических индексов для оценки и предсказания самых разнообразных свойств, вплоть до биологической активности молекул.
      Перевод этой книги полезен ещё и тем, что затронутые в ней вопросы, возможно, прозволят снять ряд дискуссионных проблем в области методологии химической науки. Так, неприятие некоторыми химиками в 50-е годы математической символики резонансных формул сменилось в 70-е годы отрицанием отдельными физиками самой концепции химической структуры. В рамках математической химии такого рода противоречия могут быть устранены, например, с помощью комбинаторно-топологического описания как классических, так и квантово-химических систем.
      Хотя работы советских учёных в этом сборнике не представлены, отрадно отметить повышенный интерес к проблемам математической химии в отечественной науке. Примером может служить первое рабочее совещание "Молекулярные графы в химических исследованиях" (Одесса, 1987), собравшее около ста специалистов со всей страны. По сравнению с зарубежными исследованиями, отечественные работы отличает более выраженный прикладной характер, направленность на решение задач компьютерного синтеза, создания разнообразных банков данных. Несмотря на высокий уровень докладов, совещание отметило недопустимое отставание в деле подготовки специалистов по математической химии. Лишь в Московском и Новосибирском университетах эпизодически читаются курсы по отдельным её вопросам. Вместе с тем, пора серьёзно поставить вопрос – какую математику должны изучать студенты-химики? Ведь даже в университетских математических программах химических факультетов такие разделы, как терия групп, комбинаторные методы, терия графов, топология практически не представлены; в свою очередь, университетские математики и вовсе не изучают химию. Кроме проблемы обучения остро стоит вопрос о научных коммуникациях: необходим общесоюзный журнал по математической химии, выходящий хотя бы раз в год. За рубежом уже много лет издаётся журнал "MATCH" (Mathematical Chemistry), а наши публикации разбросаны по сборникам и самым разнообразным периодическим изданиям.

До недавнего времени познакомиться с математической химией советский читатель мог лишь по книге В. И. Соколова "Введение в теоретическую стереохимию" (М.: Наука, 1979) и брошюре И.С.Дмитриева "Молекулы без химических связей" (Л.: Химия, 1977). Частично восполняя этот пробел, сибирское отделение издательства "Наука" выпустило в прошлом году книгу "Применение теории графов в химии" (под редакцией Н. С. Зефирова С. И. Кучанова). Книга состоит из трёх разделов, причём первый посвящён использованию теории графов в структурной химии; во второй части рассмотрены графы-реакции; в третьей показано, как с помощью графов можно облегчить решение многих традиционных задач химической физики полимеров. Конечно, эта книга – ещё не учебник (значительная часть обсуждаемых идей представляет собой оригинальные результаты авторов); тем не менее, первую часть сборника можно вполне рекомендовать для первоначального ознакомления с предметом.
      Ещё один сборник – труды семинара химического факультета МГУ "Принципы симметрии и системности в химии" (под редакцией Н. Ф. Степанова) увидел свет в 1987 году. Главная тема сборника – теоретико-групповые, теоретико-графовые и теоретико-системные методы в химии. Нетрадиционен круг обсуждаемых вопросов, ещё менее стандартны ответы на них. Читатель узнает, например, о причинах трёхмерности пространства, о возможном механизме возникновения дисимметрии в живой природе, о принципах конструирования периодической системы молекул, о плоскостях симметрии химических реакций, об описании молекулярных форм без использования геометрических параметров и о многом другом. К сожалению найти книгу можно только в научных библиотеках, поскольку в широкую продажу она не поступала.
      Коль скоро речь зашла о принципах симметрии и системности в науке, нельзя не упомянуть ещё об одной необычной книге – "Система. Симметрия. Гармония" (М.: Мысль, 1988). Эта книга посвящена одному из вариантов так называемой общей теории систем (ОТС), предложенному и развиваемому Ю.А.Урманцевым и нашедшему на сегодняшний день наибольшее число сторонников среди учёных самых разных специальностей – как естественных, так и гуманитарных. Исходные принципы ОТС Урманцева составляют понятия системы и хаоса, полиморфизма и изоморфизма, симметрии и асимметрии, а также гармонии и дисгармонии.
      Думается, что теория Урманцева должна вызвать самое пристальное внимание химиков уже хотя бы потому, что в ней традиционно химические понятия состава, изомерии, дисимметрии, возведены в ранг общесистемных. В книге можно встретить поразительные симметрийные аналоги – например между изомерами листьев и молекулярных структур ** . Конечно, при чтении книги местами необходим определённый уровень профессиональной непредвзятости – скажем, когда речь заходит о химико-музыкальных параллелях или обосновании зеркально-симметричной системы элементов. Тем не менее, книгу пронизывает центральная идея – найти универсальный язык, выражающий единство мироздания, сродни которому разве что касталийский язык "игры в бисер" Германа Гесса.
Говоря о математических конструкциях современной химии, нельзя обойти вниманием и замечательную книгу А. Ф. Бочкова и В. А. Смита "Органический синтез" (М.: Наука, 1987). Хотя её авторы – "чистые" химики, ряд обсуждаемых в книге идей весьма близок затронутым выше проблемам. Не останавливаясь на блестящей форме изложения и глубине содержания этой книги, после прочтения которой хочется заняться органическим синтезом, подчеркнём лишь два момента. Во-первых, рассматривая органическую химию сквозь призму её вклада в мировую науку и культуру, авторы проводят отчётливую параллель между химией и математикой как универсальными науками, черпающими объекты и проблемы своих исследований внутри самих себя. Иными словами, к традиционному статусу математики как царицы и служанки химии, можно добавить и своеобразную ипостась её сестры. Во-вторых, убеждая читателя в том, что органический синтез – точная наука, авторы апеллируют к точности и строгости как самой структурной химии, так и к совершенству логики химических идей.
      Если так говорят экспериментаторы, то можно ли сомневаться, что час математической химии пробил?

________________________
  * См. "Химию и жизнь", 1988, № 7, с.22.
** См. "Химию и жизнь", 1989, № 2.