Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
274
У. Херндон
рые были собраны Матоном с целью критического обсуждения этого типа
алгоритмов теории графов [24]. Тем не менее эффективные алгоритмы,
основанные на аналогичных процедурах, оказываются успешными при
определении автоморфных свойств графов Матона [22].
Получение различных классов вершин в графе 13 осуществляется следующим
образом. К каждой вершине поочередно добавляется петля, и, используя
алгоритм дополненной расширенной связности, получают каноническое
упорядочивание. Это проиллюстрировано на схеме 14 для каждого из
визуально наблюдаемых классов вершин.
(01)020304(02)0506(03)0708(04)0910(05)0607(06)09(07)08(08)10(09)10(10)
(01)020304(02)0305(03)06(04)0708(05)0709(06)0910(07)08(08)10(09)10(10)
14
В регулярном графе при отсутствии очевидной симметрии все вершины должны
быть проверены тем же способом. Затем для каждого преобразованного графа
получают линейное обозначение для матрицы смежности. Если вершины в
исходном графе 13 связаны симметрией, то они будут давать идентичные
линейные обозначения для преобразованных графов, приводя к трем различным
классам эквивалентности. После нумерации графа линейное обозначение
получают в соответствии с правилами 1-3.
В некоторых случаях визуальное определение симметрии может приводить к
ошибочному разбиению вершин графа на классы эквивалентности. Граф 15 взят
из работы Рандича [25] по случайным блужданиям в графах и иллюстрирует то
обстоятельство, что сим-
Каноническая нумерация
275
метрия графа может быть намного выше симметрии, которая выявлялась бы при
рассмотрении модели или изображения. В этом случае проверка классов
вершин, кажущихся различными (а, b и с в 15), показывает, что в
действительности все они идентичны.
Такие проблемы нечасто возникают при рассмотрении химических графов,
поскольку они обычно представляют фиксированную трехмерную структуру с
легко устанавливаемой точечной группой симметрии. Тем не менее
вероятность возникновения подобных ситуаций намного больше в графах более
общего типа, и особенно для больших регулярных графов.
5. ВЫВОДЫ
В этой статье предложена схема однозначного обозначения для графов,
которая, по-видимому, широко применима. Предполагается, что алгоритм
нумерации будет применим ко всем химическим графам и трудности возникнут
лишь для очень больших высокорегулярных графов, подобных предложенным
Матоном [24]. Если получена однозначная нумерация графа, то решение
проблемы однозначного кодирования или номенклатуры достигается
использованием линейной компактной формы матрицы смежности для
представления графа. Также показано, что метод однозначных обозначений
позволяет решить многие проблемы распознавания симметрии графов и их
изоморфизма, и в частности может быть использован для
-b/с \у\/ esV--Х/65 \У
(01)020304(02)0506(03 >0507(04)0608(05)08(06)07(07)08(08)
15
276
У. Херндон
получения правильного разбиения вершин графа на классы эквивалентности.
Теоретико-графовые характеристики химических графов использовались и
могут быть использованы для решения двух основных задач. Первая из них,
обсуждаемая в настоящей статье, связана с получением кодирования,
полезйого при рассмотрении химических структур. Конечно, желательно иметь
однозначный код для любого данного типа структуры, и эта проблема, по-
видимому, полностью решается с использованием подхода, предложенного
здесь и во многих других предыдущих работах [7-21].
Вторым применением теории графов для описания химических графов является
получение численных данных о химической структуре, которые могут быть
использованы для корреляции с биологическими, физическими или химическими
свойствами. В книге Кай-ера и Холла [26], в статьях Уилкинса и др. [27,
28] суммированы результаты ряда систематических исследований такого типа,
которые можно с успехом применять для корреляции свойств. В некоторых
недавних работах [29-33] * было высказано предположение, что теоретико-
графовые индексы могут также оказаться пригодными для решения проблем
изоморфизма графов и различения изомеров. Тем не менее, даже когда десять
индексов структуры графа комбинируются в один "супериндекс" для
различения изомеров
[27]г все же нельзя показать, что он достаточен для установления
изоморфизма, и представляется, что процедура канонической нумерации
является более полезным подходом к решению подобных проблем.
Автор признателен Robert A. Welch Foundation (Хьюстон, шт. Техас) за
финансирование этой работы.
Литература
1. Balaban A.T. (Ed.), Chemical Applications of Graph Theory, Academic
Press, N.Y., 1976.
2. Rouvray D.H., R.I.C. Revs., 1971, v. 4, p. 173.
3. Rouvray D.H., Balaban A.T., In: Applications of Graph Theory, R.J.
Wilson, L.W. Beineke, Eds., Academic Press, N.Y., 1979, Ch. 7.
4. Mislow K., Bull. Soc. Chim. Belg., 1977, v. 86, p. 595.
5. Mislow K., Introduction to Stereochemistry, W.A. Benjamin, N.Y., 1965,
Ch. 2.
6. Casey J.B., Evans W.J., Powell W.H., Inorg. Chem., 1981, v. 20, p.
