Оглавление (стр. 9 )

.

1.1.16. Графы в классической теории химического строения.

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

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

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

В случае углеводородов типичным представителем молекул с древообразным графом является молекула метана и ее гомологи. МГ содержат только вершины степени единица и четыре. Вершинам степени единица соответствуют ядра атомов водорода, а вершинам четвертой степени – ядра атомов углерода. Общая эмпирическая формула таких соединений СпН2п+2. МГ этих соединений при п £ 4 изображены на рис. 1.1.6.

Рис.1.1.6. Общая эмпирическая формула для соединений СnH2n+2.

степени соответствует атом углерода с тетраэдрическим расположением связанных с ним атомов. Более детальное описание этих структур провести трудно, потому что уже в случае этана появляется неоднозначность во взаимном расположении атомов водорода разных групп СН3, которая может быть устранена, например, с помощью квантово-химических расчетов или При п = 4 имеются два неизоморфных графа, которым соответствуют две различные углеводородные молекулы: бутан и изобутан. В случае п = 5 существует три изомера, при увеличении п число изомеров резко возрастает. С помощью графов описанного выше типа можно в общих чертах восстановить локальную геометрию углеводородных молекул. Каждой вершине четвертой расчетов по методу атом-атом потенциалов.

1.1.17. Понятия теории графов

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

Рис. 1.1.7. Графы.

называются взвешенными. Вершины степени 1 называют висячими вершинами, а степени 3 и выше – узлами.

Маршрутом называют путь по графу, последовательно соединяющий смежные вершины. Маршрут можно задать последовательностью вершин v0,v1,…vn либо ребер х1 = (v0, v1), x2 = (v1, v2), ...,xn = (vn−1, vn). Число ребер n – длина маршрута. Если все ребра хi маршрута различны, то они называются цепью, а если различны к тому же и все вершины vi, то просто цепью. Замкнутая цепь называется циклом, а замкнутая простая цепь – простым циклом. Для орграфов определено так же понятие ориентированных маршрутов (следовательно, цепей и циклов), когда переходы между вершинами возможны только от начальной вершины ребра к конечной, но не наоборот.

Дадим теперь строгое определение графам. Граф ζ состоит множества V вершин vi и множества Х неупорядоченных пар вершин (vi, vj). Каждую пару х = (vi, vj) = (vj, vi) называют ребром графа ζ, соединяющим вершины vi и vj. Если пары (vi, vj)являются упорядоченными, т. е. (vi, vj)≠(vj, vi), то получаем определение орграфа. Каждому орграфу соответствует неориентированный граф, у которого вершины vi и vj соединены ребром тогда и только тогда, когда существует дуга (vi, vj) или (vj, vi). Следовательно, все понятия, определенные для неориентированных графов, автоматически переносятся на графы, если для их ребер употреблять термин «дуга».

Говорят, что ребро х = (u, v) инцедентно вершинам u и v. Дуга х выходит из начальной для этой дуги вершины u и входит в конечную вершину v. Вершины u и v, соединенные ребром х, называются смежными.. У полного графа все вершины смежные. Два ребра являются смежными в том случае, если они инцидентны одной и той же вершине. Степенью f вершины называется число инцидентных ей ребер. Если ребро является петлей, то при подсчете кратности вершины его следует учесть дважды. Вершинам, ребрам и дугам могут быть приписаны некоторые числа (положительные или отрицательные) – веса этих элементов. контура.

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

Один и тот же граф можно изображать по-разному. Например, граф, соответствующий кубу, можно представить в виде объемной фигуры. Однако обычно графы изображают на Такие графы Простая ориентированная цепь носит название плоскости. При этом произвольный граф может иметь различные начертания, называемые его геометрическими реализациями. Совсем необязательно чертить ребра графа прямолинейными, каждое из них можно заменить линией любой формы и длины. Кроме того, можно произвольным образом менять расположение вершин в плоскости рисунка. Обе указанные операции, хотя и меняют изображение графа (рис. П.2), тем не менее сохраняют его топологическую структуру, которая определяется лишь характером смежности вершин. Форма и длина ребер не несут обычно в теории графов никакой информации. Граф может быть начертан таким образом, что все точки пересечения ребер приходятся только на его вершины (см. рис. П.2). Граф, который допускает такое начертание, носит название планарного, а соответствующая геометрическая реализация называется плоским графом (изомеров (J= 4). Поэтому полное число нумераций n!= 24 получается путем умножения числа изоморфов J = 4 графа одной произвольной нумерации на число W = 6 различных таких нумераций. Отсюда следует хорошо известная в теории графов формула W = n!/J. Хотя величина J определена см. рис. П.1).

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

Теперь рассмотрим помеченные (пронумерованные) графы, в которых каждой из n вершин приписывается отличное от других целое число от 1 до n. Ясно, что непомеченный граф может быть пронумерован n! способами, но при этом некоторые из них могут совпадать. Так, из 4!=24 возможных способов нумерации графа (рис. П3) различных оказывается всего 6 ,а каждый из остальных 18 способов совпадает с одним из этих шести. Например, способ нумерации (1, 4, 3, 2) ничем не отличается от первого среди указанных на рис. П.3 способа (1, 2, 3, 4), поскольку оба соответствующих им помеченных графа могут быть совмещены путем поворота вокруг ребра, соединяющего вершины 1и 3. Следовательно, эти два графа являются одинаковыми. Два (помеченных) графа считаются одинаковыми и называются изоморфными, если существует взаимооднозначное отображение множества вершин одного графа на множество вершин другого, при котором сохраняется смежность вершин (и распределение пометок на них). Приведем все возможные изоморфные графы (изоморфы) соответствующего помеченного графа(1, 2, 3, 4) (рис. П.4). Каждый из остальных пяти помеченных графов на рис. П.3 имеет такое же количество выше на множестве помеченных графов, однако она имеет смысл и для непомеченных графов, поскольку ее значение не зависит от способа их нумерации. Для каждого непомеченного графа число J, называемое порядком его группы автоморфизмов, равно числу изоморфов любого из соответствующих ему помеченных графов. Величина J характеризует степень симметрии непомеченного графа и значение ее тем больше, чем больше совпадающих способов распределения пометок в нем. Значение J равно числу автоморфизмов непомеченного графа, т. е. таких отображений вершин графа на себя, которые сохраняют смежность.

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