В - Р + Г = 1, (*)

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

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

а) б)

Рис.2

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

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

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

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

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

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

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

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

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

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

B - Р + Г= 1.

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

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

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

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

Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г= 1.

Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9.

Следовательно, Г = 5. Каждая из пяти граней имеет, по крайней мере, четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше (5 4)/2 = 10, что противоречит условию, по которому их число равно 9.

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

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

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

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

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

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

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

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

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

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

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

5. Количественные методы в социологических исследованиях, М., 1966; Беляев Э. В., Проблемы социологических измерения, "ВФ", 1967, No 7; Bavelas. Communication patterns in task oriented groups, в кн. Lerner D., Lass well H., Policy sciences, Stanford, 1951;

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

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

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

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

УДК 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.

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

риложение

Приложение

Реферат по предмету высшая математика на тему:

Применение в химии теории графов

Выполнил студент группы НХ-202

Москва 2011
Графами называется область конечной математики, изучающая дискретные структуры; применяется для решения различных теоретических и прикладных задач.
Некоторые основные понятия. Граф - совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединенных линиями (рис. 1,а). Если на графе линии ориентированы (т.е. стрелками показано направление связи вершин), они называются дугами, или ветвями; если неориентированы, - ребрами. Соответственно, граф, содержащий только дуги, называется ориентированным, или орграфом; только ребра-неориентированным; дуги и ребра - смешанным. Граф, имеющий кратные ребра, называется мультиграфом; граф, содержащий только ребра, принадлежащие двум его непересекающимся подмножествам (частям), - двудольным; дуги (ребра) и (или) вершины, которым отвечают определенные веса или числовые значения каких-либо параметров, - взвешенным. Путь в графе - чередующаяся последовательность вершин и дуг, в которой ни одна из вершин не повторяется (напр., a, b на рис. 1,a); контур-замкнутый путь, в котором первая и последняя вершины совпадают (напр.,f, h); петля - дуга (ребро), которая начинается и кончается в одной и той же вершине. Цепь графа - последовательность ребер, в которой ни одна из вершин не повторяется (например, с, d, e); цикл - замкнутая цепь, в которой ее начальная и конечная вершины совпадают. Граф называется связным, если любая пара его вершин соединена цепью или путем; в противоположном случае граф называется несвязным.
Дерево - связный неориентированный граф, не содержащий циклов или контуров (рис. 1,б). Остовный подграф некоторого графа - его подмножество, содержащее все вершины и лишь определенные ребра. Остовное дерево некоторого графа - его остовный подграф, представляющий собой дерево. Графы называются изоморфными, если существует взаимно однозначное соответствие между совокупностями их вершин и ребер (дуг).
Для решения задач графов теории и ее приложений графы представляют с помощью матриц (смежности, инцидентности, двустрочных и др.), а также спец. числовых характеристик. Например, в матрице смежности (рис. 1,в) строки и столбцы отвечают номерам вершин графа, а ее элементы принимают значения 0 и 1 (соответственно, отсутствие и наличие дуги между данной парой вершин); в матрице инцидентности (рис. 1,г) строки отвечают номерам вершин, столбцы - номерам дуг, а элементы принимают значения 0, + 1 и - 1 (соответственно, отсутствие, наличие дуги, входящей в вершину и выходящей из нее). Наиболее употребительные числовые характеристики: число вершин (т), число дуг или ребер (n), цикломатическое число, или ранг графа (п - т + k, где k-число связных подграфов в несвязном графе; например, для графа на рис. 1,б ранг будет: 10-6+ 1 =5).
Применение теории графов базируется на построении и анализе различных классов химических и химико-технологических графов, которые называются также топологияческими моделями, т.е. моделями, учитывающими только характер связи вершин. Дуги (ребра) и вершины этих графов отображают химические и химико-технологические понятия, явления, процессы или объекты и соответственно качественные и количественные взаимосвязи либо определенные отношения между ними.

Рис. 1. Иллюстрация некоторых основных понятий: а-смешанный граф; б-остовное дерево (сплошные дуги a, h, d, f, h) и нек-рый подграф (пунктирные дуги с, e, g, k, l) орграфа; в, г-матрицы соотв. смежности и инцидентности орграфа.
Теоретические задачи. Химические графы дают возможность прогнозировать химические превращения, пояснять сущность и систематизировать некоторые основные понятия химии: структуру, конфигурацию, конформации, квантовомеханические и статистико-механические взаимодействия молекул, изомерию и др. К химическим графам относятся молекулярные, двудольные и сигнальные графы кинетических уравнений реакций.
Молекулярные графы, применяемые в стереохимии и структурной топологии, химии кластеров, полимеров и др., представляют собой неориентированные графы, отображающие строение молекул (рис. 2). Вершины и ребра этих графов отвечают, соответственно, атомам и химическим связям между ними.

Рис. 2. Молекулярные графы и деревья: а, б - мультиграфы соотв. этилена и формальдегида; в-мол. изомеров пентана (деревья 4, 5 изоморфны дереву 2).
В стереохимии органических веществ наиболее часто используют молекулярные деревья -остовные деревья молекулярных графов, которые содержат только все вершины, соответствующие атомам С (рис. 2, а и б). Составление наборов молекулярных деревьев и установление их изоморфизма позволяют определять молекулярные структуры и находить полное число изомеров алканов, алкенов и алкинов (рис. 2, в).
Молекулярные графы дают возможность сводить задачи, связанные с кодированием, номенклатурой и структурными особенностями (разветвлепность, цикличность и т.п.) молекул различных соединений, к анализу и сопоставлению чисто математических признаков и свойств молекулярных графов и их деревьев, а также соответствующих им матриц. Для выявления количественных корреляций между строением молекул и физико-химическими (в т.ч. фармакологическими) свойствами соединений разработано более 20 тысяч названий топологических индексов молекул (Винера, Балабана, Хосойи, Плата, Рандича и др.), которые определяют с помощью матриц и числовых характеристик молекулярных деревьев. Например, индекс Винера W = (m 3 + m)/6, где m-число вершин, отвечающих атомам С, коррелирует с молекулярными объемами и рефракциями, энтальпиями образования, вязкостью, поверхностным натяжением, хроматографическими константами соединений, октановыми числами углеводородов и даже физиологической активностью лекарственных препаратов.
Важными параметрами молекулярных графов, используемыми для определения таутомерных форм данного вещества и их реакционной способности, а также при классификации аминокислот, нуклеиновых кислот, углеводов и других сложных природных соединений, являются средняя и полная (Н) информационные емкости. Параметр вычисляется по формуле энтропии информации Шеннона: , где p t -вероятность принадлежности вершин m графа i-тому виду, или классу эквивалентности, k; i = , Параметр. Изучение молекулярных структур типа неорганических кластеров или лент Мёбиуса сводится к установлению изоморфизма соответствующих молекулярных графов путем их укладки (вложения) в сложные многогранники (например, полиэдры в случае кластеров) или спец. многомерные поверхности (например, римановые). Анализ молекулярных графов полимеров, вершины которых отвечают мономерным звеньям, а ребра - химическим связям между ними, позволяет объяснить, например, эффекты исключенного объема, приводящие к качественным изменениям прогнозируемых свойств полимеров.

Рис. 3. Графы реакций: а-двудольный; б-сигнальный ур-ний кинетики; r 1 , г 2 -р-ции; а 1 -а 6 -реагенты; k-константы скорости р-цнй; s-комплексная переменная преобразования Лапласа.
С применением графов теории и принципов искусственного интеллекта разработано программное обеспечение информационно-поисковых систем в химии, а также автоматизированных систем идентификации молекулярных структур и рационального планирования органического синтеза. Для практической реализации на ЭВМ операций выбора рациональных путей химических превращений на основе ретросинтетического и синтонного принципов используют многоуровневые разветвленные графы поиска вариантов решений, вершины которых соответствуют молекулярным графам реагентов и продуктов, а дуги изображают превращения веществ.

Рис. 4. Одноконтурная химико-технологическая система и соответствующие графы: а-структурная схема; б, в-материальные потоковые графы соотв. по общим массовым расходам и расходу компонента А; г- тепловой потоковый граф; д-фрагмент системы ур-ний (f 1 - f 6) материального баланса, полученной из анализа графов на рис. 4, б и в; е-двудольный информационный орграф; ж-информационный граф, I-смеситель; II-реактор; III-ректификационная колонна; IV-холодильник; I 1 -I 8 -технол. потоки; q-массовый расход; H-энтальпия потока; i. s и i*, s*- соотв. реальные и фиктивные источники и стоки материальных и тепловых потоков; с-концентрация реагента; V-объем реактора.
Матричные представления молекулярных графов различных соединений эквивалентны (после преобразования соответствующих элементов матриц) матричным методам квантовой химии. Поэтому теорию графов применяют при выполнении сложных квантово-химических расчетов: для определения числа, свойств и энергий молекулярных орбиталей, прогнозирования реакционной способности сопряженных альтернантных и неальтернантных полиенов, выявления ароматических и антиароматических свойств веществ и др.
Для изучения в химической физике возмущений в системах, состоящих из большого числа частиц, используют так называемые диаграммы Фейнмана - графы, вершины которых отвечают элементарным взаимодействиям физических частиц, ребра - их путям после столкновений. В частности, эти графы позволяют исследовать механизмы колебательных реакций и определять устойчивость реакционных систем.
Для выбора рациональных путей превращения молекул реагентов при заданном множестве известных взаимодействий используют двудольные графы реакций (вершины соответствуют молекулам и этим реакциям, дуги - взаимодействиям молекул в реакции; рис. 3,a). Такие графы позволяют разрабатывать диалоговые алгоритмы выбора оптимальных путей химических превращений, для которых требуется наименьшее число промежуточных реакций, минимальное число реагентов из перечня допустимых или достигается наибольший выход продуктов.
Сигнальные графы уравнений кинетики реакций отображают системы кинетических уравнений, представленных в алгебраическо-операторной форме (рис. 3,б). Вершины графов отвечают так называемым информационным переменным, или сигналам, в виде концентраций реагентов, дуги - взаимосвязям сигналов, причем веса дуг определяются кинетическими константами. Такие графы применяют при изучении механизмов и кинетики сложных каталитических реакций, сложных фазовых равновесий при образовании комплексных соединений, а также для расчета параметров аддитивных свойств растворов.
Прикладные задачи. Для решения многомерных задач анализа и оптимизации химико-технологических систем (ХТС) используют следующие химико-технологические графы (рис. 4): потоковые, информационно-потоковые, сигнальные и графы надежности. К потоковым графам, представляющим собой взвешенные орграфы, относятся параметрические, материальные по общим массовым расходам физических потоков и массовым расходам некоторых химических компонентов либо элементов, а также тепловые графы. Перечисленные графы соответствуют физико-химическим превращениям веществ и энергии в данной ХТС.
Параметрические потоковые графы отображают преобразование параметров (массовых расходов и др.) физических потоков элементами ХТС; вершины графов отвечают математическим моделям аппаратов, а также источникам и стокам указанных потоков, а дуги - самим потокам, причем веса дуг равны числу параметров соответствующего потока. Параметрические графы служат для разработки алгоритмов анализа технологических режимов многоконтурных ХТС. Такие алгоритмы устанавливают последовательность расчета систем уравнений математических моделей отдельных аппаратов какой-либо системы для определения параметров ее выходных потоков при известных значениях переменных входных потоков.
Материальные потоковые графы отображают изменения расходов веществ в ХТС. Вершины графов отвечают аппаратам, в которых трансформируются общие массовые расходы физических потоков и массовые расходы некоторых химических компонентов или элементов, а также источникам и стокам веществ потоков либо данных компонентов; соответственно, дуги графов отвечают физическим потокам или физическим и фиктивным (химические превращения веществ в аппаратах) источникам и стокам каких-либо компонентов, а веса дуг равны массовым расходам обоих типов. Тепловые потоковые графы отображают балансы теплоты в ХТС; вершины графов соответствуют аппаратам, в которых изменяются расходы теплоты физических потоков, и, кроме того, источникам и стокам тепловой энергии системы; дуги отвечают физическим и фиктивным (физ.-хим. превращения энергии в аппаратах) тепловым потокам, а веса дуг равны энтальпиям потоков. Материальные и тепловые графы используют для составления программ автоматизированной разработки алгоритмов решения систем уравнений материальных и тепловых балансов сложных ХТС.
Информационно-пстоковые графы отображают логико-информационную структуру систем уравнений математических моделей ХТС; применяются для составления оптимальных алгоритмов расчета этих систем. Двудольный информационный граф (рис. 4, е) неориентированный или ориентированный граф, вершины которого отвечают, соответственно, уравнениям f l -f 6 и переменным q 1 - V, а ветви отображают их взаимосвязь. Информационный граф (рис. 4, ж) - орграф, изображающий порядок решения уравнений; вершины графа отвечают этим уравнениям, источникам и приемникам информации ХТС, а ветви - информационным переменным.
Сигнальные графы соответствуют линейным системам уравнений математических моделей химико- технологических процессов и систем. Вершины графов отвечают сигналам (например, температуре), ветви - связям между ними. Такие графы используют для анализа статических и динамических режимов многопараметрических процессов и ХТС, а также показателей ряда их важнейших свойств (устойчивости, чувствительности, управляемости).
Графы надежности применяют для расчета различных показателей надежности ХТС. Среди многочисленных групп этих графов (например, параметрических, логико-функциональных) особенно важны так называемые деревья отказов. Каждое такое дерево - взвешенный орграф, отображающий взаимосвязь множества простых отказов отдельных процессов и аппаратов ХТС, которые приводят к множеству вторичных отказов и результирующему отказу системы в целом.
Для создания комплексов программ автоматизированного синтеза оптимальных высоконадежных производств (в том числе ресурсосберегающих) наряду с принципами искусственного интеллекта применяют ориентированные семантические, или смысловые, графы вариантов решений ХТС. Эти графы, которые в частном случае являются деревьями, изображают процедуры генерации множества рациональных альтернативных схем ХТС (например, 14 возможных при разделении ректификацией пятикомпонентной смеси целевых продуктов) и процедуры упорядоченного выбора среди них схемы, оптимальной по некоторому критерию эффективности системы.
и т.д.................