Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
являются графами, в которых атомы
Топологические индексы
207
представляются вершинами, а ковалентные химические связи - ребрами. Такой
граф описывает связность атомов в молекулярном скелете независимо от
метрических свойств, т. е. равновесного межъядерного расстояния,
валентных углов и т. д., соответствующих данной химической структуре.
Следовательно, при теоретикографовом описании отражаются те особенности
молекулярной структуры, которые зависят от связности в противоположность
свойствам, обусловленным точным геометрическим расположением составляющих
молекулу атомов в пространстве. Именно в этом смысле химические графы
являются топологическими (а не геометрическими) представлениями
молекулярных структур [11].
Особый интерес для химиков представляют изоморфизм и кодирование графов
[10]. Говорят, что два графа G, и G2 изоморфны (это записывается как G, =
G2), если существует такое взаимно однозначное отображение вершин графа
G, на вершины графа G2, при котором сохраняется смежность, т. е. две
вершины являются смежными в графе G,, если и только если соответствующие
вершины в графе G2 также являются смежными [12]. По сути, изоморфные
графы - это идентичные графы, но изображенные по-разному. В случае
небольших графов для определения изоморфных графов достаточным
оказывается визуальное рассмотрение двумерных диаграмм; этот метод
непригоден для практического применения в случае графов с большим числом
вершин. Альтернативно графы могут быть представлены матрицами, такими,
как матрица смежности, матрица расстояний, матрица инцидентности и т. д.
Но в этом случае возможно столько же матриц, сколько существует возможных
способов нумерации вершин графа. Следовательно, для того чтобы
установить, являются ли два графа G, и G2 с п вершинами изоморфными или
же нет, необходимо осуществить п2 х п! операций. Молекулярные структуры
являются графами особого вида, и основная проблема химической
документации состоит в присвоении каждой вершине кода, такого, что два
графа G, и G2 имеют одинаковый код, если и только если G, = G2. Очевидно,
что элегантное решение проблемы кодирования явится в равной мере и
хорошим решением проблемы изоморфизма. В настоящее время приемлемое
решение неизвестно, хотя предложены различные системы номенклатуры
химических соединений *. Был проведен де-
* Наиболее удачной на сегодняшний день является, по-видимому,
номенклатура, предложенная Бончевым и Балабаном и основанная на
топологическом центрическом кодировании Она применима к соединениям,
графы которых могут быть однозначно уложены на плоскости [49*, 50*]. -
Прим. перев.
208
В. Магнусон, Д. Харрис, С. Бейсак
тальный поиск редуцированной формы матрицы смежности графа, с которой
удобнее работать, чем с самой матрицей, и которая тем не менее
обеспечивает однозначную характеристику структуры. Спиальтер [13-15]
высказал предположение, что характеристический полином, полученный из
матрицы смежности, т. е. матрицы связности атомов, мог бы однозначно
описывать топологию молекулы. Однако Балабан и Харари [16] опровергли
утверждения Спи-альтера и показали, что различные неизоморфные графы
могут иметь одинаковые характеристические полиномы. Такие графы
называются изоспектральными или коспектральными. Следовательно, ни
характеристический полином, ни спектр графа не способны дать простую и
редуцированную форму матрицы смежности, однозначно характеризующую
топологию молекулы.
Различные инварианты графа представляют собой важные характеристики
графа. Инвариант графа - это теоретико-графовое свойство, сохраняющееся
при изоморфизме [12]. Характеристический полином матрицы смежности
является инвариантом графа, хотя матрица смежности изменяется в
зависимости от нумерации вершин. Инвариантом графа могут быть полином,
последовательность чисел или числовой индекс. Числовые индексы,
полученные из топологических характеристик соответствующих химических
графов, называются топологическими индексами. Очевидно, что совпадение
всех инвариантов графов и G2 является необходимым предварительным
условием изоморфизма графов G, и G2. Но это не достаточное условие для
изоморфизма. На сегодняшний день невозможно обнаружить общий набор
инвариантов, которые были бы способны дать однозначную характеристику
графа и тем самым решить проблему изоморфизма [12]. Тем не менее были
предложены практические схемы для различения изомеров, в которых
одновременно используется целый ряд различных топологических параметров
[12]. Недостатком представления молекул с помощью графов является то, что
при этом теряются все стереохимияеские особенности молекулярной
структуры. Однако графы все же описывают полную топологию молекулы;
известно, что многие важные характеристики молекул, такие, как энергия,
порядок связи и плотность заряда, существенно зависят от топологии [18].
Поскольку топологические индексы являются численными выражениями
определенных топологических свойств молекулярной структуры, не
