Теория граф (диаграмм)

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

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

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

Такая диаграмма называется топологической диаграммой, т.к. она показывает только связи между атомами и тип связей между ними. Этот тип структурной презентации не содержит данных о 3D структуре, топографии молекулы.

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

Рис. 2.11. Фенилаланин можно представить в теории граф в качестве маркированной диаграммы плотности с различными типами атомов и связей.

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

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

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

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

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

Дата добавления: 2015-06-04