Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
36. Balasubramanian K., Annal. New York Acad. Sci., 1979, v. 319, p. 33.
37. Balasubramanian K., J. Chem. Phys., 1980, v. 73, p. 3321.
38. Balasubramanian K., Int. J. Quant. Chem., 1982, v. 21, p. 411.
39. Balasubramanian K., Int. J Quant. Chem.. 1982, v. 22, p. 581.
Симметрия и спектры графов
287
40. Balasubramaman К., Randic М., Theor. Chim. Acta, 1982, v. 61,
p. 307.
41. Balasubramaman K., Randic М. (готовится к печати).
42. Spnnggate М., Poland D., J. Chem. Phys., 1975, v. 15, p. 680.
43. Kilpatrick J.F., In: Adv. Chem. Phys., I. Prigogine (Ed.), Wiley-
Interscience, N.Y., 1971.
44. Монтролл Э.В. - В сб.: Прикладная комбинаторная математика. - М.:
Мир, 1968, с. 9-60.
45. Peruggi F., Liberia F., Monroy G., J. Phys. A., 1983, vb 16, p.
811.
46. Flurry R.L., Int. J. Quant. Chem., 1984, v. 25, p. 309.
47. Randic М., Klein D.I., Int. J Quant. Chem., 1982, v. 21, p. 647.
48. Godsil C.D., McKay B.D. - Bull. Australian Math. Soc., 1978, v. 18,
p. 21. 49*. Тринайстич H. - В кн.: Полу эмпирические методы расчета
электронной
структуры. - М.: Мир, 1980, т. 1, с. 13-46.
50*. Глуховцев М.Н., Симкин Б.Я., Минкин В.И. - Успехи химии, 1985, т.
54, с. 86.
51' Randic М., Kotovic К, Trinajstic N., In: Symmetries and Properties of
Non-Rigid Molecules, Comp. Survey Proc. Int. Symp., Amsterdam, 1983, p.
399.
ГРУППЫ АВТОМОРФИЗМОВ НЕКОТОРЫХ ХИМИЧЕСКИХ ГРАФОВ
Г. Джонс (G.A. Jones), Э. Ллойд (Е.К. Lloyd)
Faculty of Mathematical Studies, The University, Southampton, S09 5NH,
United Kingdom
Многие из обсуждаемых в химической литературе реакционных графов являются
примерами графов, которые ряд специалистов по теории групп называют
суборбитальными графами. Рассматривая их в этом аспекте, мы можем
получить некоторую информацию о группах автоморфизмов графов.
1. ВВЕДЕНИЕ
Реакционные графы, введенные впервые в 1966 г. Балабаном и сотр. [1],
упоминаются во многих статьях. Позднее был проявлен интерес, в
особенности в работах Рандича [2-6], к нахождению их групп автоморфизмов.
В общем случае определение группы автоморфизмов - трудная задача.
Рандичем получен алгоритм, который, по-видимому, полезен для нахождения
числа автоморфизмов, а Мак-Кеем [7] представлен алгоритм для нахождения
группы автоморфизмов в виде набора менее чем п генераторов, где п - число
вершин графа. Утверждается, что последний алгоритм достаточно экономичен
по расходу времени и пределы его применимости простираются до графов с
более чем тысячью вершинами.
В настоящей статье мы покажем, что многие реакционные графы являются
примерами графов, называемых некоторыми специалистами по теории групп
суборбитальными графами (а другими авторами - орбитальными или
окрашенными графами), и это позволит нам сделать вывод, что группа
автоморфизмов имеет по крайней мере конечную размерность. Перед тем как
перейти к описанию суборбитальных графов, мы рассмотрим некоторые
результаты из литературы по теории графов (см. разд. 2) и затем ряд
примеров реакционных графов, для которых довольно легко получить группу
автоморфизмов (разд. 3).
Группы автоморфизмов химических графов
289
2. НЕКОТОРЫЕ ГРАФЫ И ИХ ГРУППЫ
Под графом мы понимаем структуру, состоящую из нескольких точек,
называемых вершинами', в такой структуре некоторые пары этих точек
соединены линиями, называемыми ребрами. На рис. 1 изображен пример графа
с 5 вершинами и 7 ребрами, который мы назовем гомотетраэдрическим графом
Е.
Автоморфизм g графа - однозначное отображение вершин, такое, что ug и vg
соединены ребром, если и только если вершины и и v соединены ребром (где
ug и vg обозначают образы и, v при действии g). Граф Е имеет четыре
автоморфизма: идентичность, транспозиция (23) взаимопереставляемых вершин
2 и 3, транспозиция (45) и произведение (23)(45), которое осуществляет
одновременно две перестановки. Множество всех автоморфизмов графа А
образует группу, обозначаемую aut А.
Полный граф Кп имеет п вершин, каждая пара которых соедйне-на ребром;
граф К5 показан на рис. 2. Ясно, что группой автоморфизмов графа Кп
является симметрическая группа S" всех перестановок множества f 1, 2, ...
, п).
Дополнение А графа А имеет jro же множество вершин, что и А, но две
вершины соединены в А, если и только если они не соединены в А. Так же
как и отображение пары вершин, соединенных ребром, в пару вершин,
соединенных ребром, каждый автоморфизм А переводит пару вершин, не
соединенных ребром, в пару вершин, не соединенных ребром; таким образом,
группы aut А и aut А идентичны.
Линейный граф L(A) графа А имеет вершину, соответствующую каждому ребру
графа А, и две вершины L {А) соединены ребром, если и только если
соответствующие ребра графа А имеют общую вершину. Линейный граф L{E)
гомотетраэдрического графа Е показан на рис. 3. Если мы перенумеруем
вершины графа Л, то в таком случае можем пометить вершины линейного графа
L (А) неу-
25
/i5\ 35
РИС. 1 Граф Е.
рис. 2. Граф .
РИС. 3. Граф L(E).
290
Г. Джонс, Э. Ллойд
