Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
плоскость симметрии.
Однако недавно был описан метод получения линейных численных обозначений
для кластерных соединений [7], действительно однозначно описывающий все
возможности изомерии. Применение системы линейных обозначений начинается
с канонической нумерации химического графа кластера. Затем составляется
компактная линейная форма таблицы связности, которая служит однозначным
кодом для каждого структурного изомера, и было показано, что порядок
перечисления этой записи полностью описывает структуру (и конфигурацию).
В настоящей работе алгоритм линейного обозначения и схема канонической
нумерации будут модифицированы и применены к более общим графам.
2. КАНОНИЧЕСКАЯ НУМЕРАЦИЯ
Существует большое число методов для упорядочивания и распознавания
структурно родственных атомов или групп, которые могут быть использованы
в системе канонической нумерации [8-18]. Одним из наиболее удобных
методов является итерационная процедура [уравнение (1)], описание которой
может быть найдено, например, в обычном справочнике Маргенау и Мэрфи [20]
*:
Эта процедура включает итерационное умножение вектор-столбца Uk на
матрицу смежности А с образованием нового вектор-столбца Uk+,. Согласно
справочнику, вектор Ux выбирается таким образом,
* Так называемые дельтаэдры. - Прим. перев.
* В известной степени аналогичным изданием является переведенный на
русский язык справочник: Корн Г., Корн Т. Справочник по математике для
научных работников и инженеров - М.: Наука, 1974. - Прим. перев.
(1)
Каноническая нумерация
269
чтобы все его элементы были равны единице. Известно, что при & -* оо
нормированный вектор аппроксимирует собственный вектор матрицы смежности
А, соответствующий собственному значению, имеющему наибольшую величину,
которое может быть названо главным собственным значением X,.
Процедура, описываемая уравнением (1), применима к 6 для упорядочивания
углеродных атомов химического графа 1,8-нафтохинодиметана. С помощью
данной процедуры атомы разбиваются на 7 классов эквивалентности, которые
непременно являются теми же самыми, что и классы, полученные из
собственного вектора, соответствующего главному собственному значению.
Однако итерационная процедура указывает на возможность возникновения
проблемы осцилляции, поскольку вершины в классах эквивалентности 5 и 6
различимы на шаге 4, но утрачивают различие на следующем шаге. Дальнейшие
итерации будут корректироваться и сохранять упорядочивание, полученное на
шаге 4.
Пример б взят из статьи Моргана [8], в которой понятие расширенной
связности было разработано для компьютерной системы данных в "Chemical
Abstracts Service". Отметим, что векторы, полученные при использовании
уравнения (1), являются как раз векторами, найденными с помощью процедуры
расширенной связности. Видно также, что можно предполагать соответствие
упорядочивания Моргана с полученным при использовании коэффициентов
главного собственного вектора, и оно не должно рассматриваться как
"неожиданное" [9]. Числа расширенной связности совпадают также с
найденными при перечислении маршрутов соответствующей длины, генерируемых
степенями А *, как недавно было показано Рейзинджером [21].
* A"s - число всех маршрутов длины п, лежащих между вершинами г и s. -
Прим. перев.
270
У. Херндон
Осцилляционное поведение и отсутствие сходимости являются общими
недостатками процедуры Моргана, что тем не менее не умаляет ее ценности.
Можно показать, что такое поведение предполагается при рассмотрении
двудольного химического графа, когда собственное значение - X,
принадлежит к тому же типу симметрии, что и X, [23]. В таком случае
предпочтительнее использовать процедуру
в которой полученные векторы всегда сходятся к векторам, соответствующим
единственному собственному значению X, + 1. Эта процедура показана на
схеме 7, где получено (без осцилляций) то же упорядочивание, что и на
схеме 6.
Последняя процедура используется для рассмотрения кластерных соединений
[7] и, как установлено, наиболее эффективна в общем случае для
упорядочивания вершин графов. Это тот же метод, что и использование
расширенной связности для упорядочивания вершин химического графа;
отличие состит в том, что предыдущее число, отнесенное к отдельной
вершине, включается также в итерационную сумму чисел смежности. В таком
случае это эквивалентно процедуре, использованной Шелли и Манком [10] в
их модификации алгоритма Моргана. Трудность, сохраняющаяся в обоих
методах, связана с тем, что изоспектральные точки [23] не будут различимы
при использовании любой из этих процедур, как показано на схеме 8.
Это объясняет неудачу Шелли и Манка при попытке разбиения атомов на
классы эквивалентности в двух из 50 рассмотренных ими химических графов.
В следующем разделе будет показано, что этот недостаток алгоритма
дополненной расширенной связности в действительности не препятствует
получению однозначного обозначения для графа с такими вершинами.
Uk+l = Uk + AUk,
