Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
(2)
,1 , .2 | 1*1 |>" I |7
Упорядочивание
7
3
9
27
83
Иэослешрмьные точки
8
Каноническая нумерация
271
3. ОДНОЗНАЧНЫЕ ЛИНЕЙНЫЕ ОБОЗНАЧЕНИЯ
В общем случае неэквивалентные вершины графа будут иметь неэквивалентные
дополненные расширенные связности. Двузначное число 01 приписывается
вершине с наибольшим значением расширенной связности, а оставшиеся
вершины упорядочиваются в соответствии с убывающими величинами
расширенной связности. После осуществления такой нумерации записывается
линейная компактная форма помеченной матрицы смежности, при этом
используются следующие правила:
1. В качестве диагональных элементов берутся полученные упорядочивания и
заключаются в скобки.
2. Ребра, связывающие вершины, указываются числовым рядом двузначных
чисел после каждого заключенного в скобки диагонального элемента.
3. Если имеются два или больше возможных правильных обозначений в
соответствии с правилами 1 и 2, то выбирается нумерация, наименьшая в
первой вершине, в которой начинаются различия в обозначениях.
Приведем несколько примеров для иллюстрации применения этих правил.
Рассмотрим сначала не имеющий симметрии граф, показанный на схеме 9.
Алгоритм нумерации приводит ко всем полностью различающимся вершинам в
графе. В этом линейном обозначении, как показано, используются двузначные
числа, не разделенные точкой, и оно однозначно для этого графа, поскольку
однозначно соответствует матрице смежности. В последнем числе все скобки,
нули и номер 1 удалены, и оно также является однозначным числом для этого
конкретного графа. Последний номер при необходимости может использоваться
как регистрационный или идентификационный номер. Можно показать на
примерах, что для сохранения единственности регистрационного номера
необходимо сохранение чисел, первоначально заключенных в скобки.
Упорядочивание 9
272
У. Херндон
Граф, показанный на схеме 10, имеет только 5 классов эквивалентности
вершин в соответствии с алгоритмом упорядочивания, представленным на
схеме 8, тогда как очевидная симметрия этого графа позволяет предположить
наличие 6 независимых классов вершин. Выбор номера 2 для вершины с левой
стороны, принадлежащей классу 2, вынуждает левосторонней вершине класса 3
присвоить номер 4. Тогда верхнюю вершину класса 4 необходимо обозначить
как вершину 6 согласно правилу 3. Противоположный выбор нумерации для
вершин класса 2 приводит к точно такому же линейному обозначению,
показывая тем самым, что вершины 2 и 3 соответственно связаны симметрией.
Граф 11 является примером химического графа, в котором можно заметить
симметрию, но алгоритм упорядочивания далеко не достаточен для отнесения
к классам эквивалентности [14]. Имеются четыре неэквивалентных класса
групп СН2 и три неэквивалентных класса групп СН. Однако, как показано,
правило 3 допускает однозначную нумерацию для графа только в результате
трех попыток установить такую нумерацию. Даже в тех случаях, когда все
вершины в графе фактически эквивалентны, можно быстро получить
однозначное линейное обозначение для графа. Например, однозначное
обозначение для графа кубана приводится на схеме 12.
Упорядочивание
(01>020305(02>04(03)05(04)07(05)07(06)03(07)(08) 236243647676878
10
преопочгпительная нумерация
[01)02070в102)0709(03)050810(04)060810(0911120б)Ш2(07)(Оа1(09110Х11Л12)
11
Каноническая нумерация 273
5 Ч /
" 6
7 4
3 к
(01)020304(02)0508ЙЗ;0507(04)0607(05)08((Ш(07)08(08)
12
Если известны все эквивалентные точки, то, согласно правилу 3, необходима
лишь одна попытка для получения нумерации. Если соотношение
эквивалентности неизвестно, то должны быть проверены все вершины;
установлено, что удобнее всего это осуществить таким образом, как описано
в следующем разделе.
4. КАНОНИЧЕСКАЯ НУМЕРАЦИЯ РЕГУЛЯРНЫХ ГРАФОВ
Вершины регулярных графов имеют одинаковые связности и, очевидно, не
могут быть разбиты на различные классы эквивалентности при использовании
любого из двух алгоритмов расширенной связности, обсужденных ранее.
Многие графы этого типа встречаются в химической литературе [8, 10, 11,
13, 14], некоторые фигурируют при обсуждении [13, 14] эффективности
алгоритмов распознавания молекулярной симметрии. Один такой граф
представлен на схеме 13, где он изображен таким образом, чтобы показать
симметрию гипотетического насыщенного углеводорода С10Н10, который имел
бы такой химический граф.
(01)020304(02)0506(03)0708(04)0910(05)06(06)09(07)08(08)10(09)10(10)
13
Визуальное распознавание трех различных классов вершин позволяет
незамедлительно определить низшее однозначное обозначение в соответствии
с правилом 3, и это показано на схеме 13. Однако что делать, если граф
изображен таким образом, что симметрия неясна? Детально проверялась
процедура, основанная на теории возмущений, и, по-видимому, она работает
для всех примеров химических графов, приведенных в литературе. Процедура
не различает симметрию в больших высоковырожденных графах, кото-
