Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
автоморфизма. Легче всего это увидеть, если перерисовать граф, как
показано на рис. 20, и заметить, что любой автоморфизм должен фиксировать
вершину 1. Таким образом, группа автоморфизмов изоморфна той подгруппе
группы симметрии кубана, которая фиксирует ребро 29, показанное на рис.
21. Имеются четыре такие операции симметрии: идентичность, вращение
(29)(36)(47)(58) и отражения (29)(38)(47)(56) и (35)(68).
Пусть теперь G - любая группа, действующая транзитивно на множество Я.
Тогда G действует на декартово произведение й х й, состоящее из всех
упорядоченных пар (а, /3) элементов а,
/3 е Я, поэтому мы полагаем, что Д0, Д, Дг_, - это орбиты Е
на Я х Я с диагональю Д" ((a, a) I а е Я). Для каждого / = 0, 1, ... ...
, г - 1 мы составляем суборбитальный граф Г( следующим образом: Г( имеет
множество вершин Я, и имеется направленное ребро (обозначенное /) от а к
/3, если и только если (а, /3) е Д,. Таким образом, множества ребер Д(
взаимно не пересекаются, и их объединение образует полный направленный
граф на Я. (Для любого
5
2
3
7
3
2
6
9
7
6
7
6
РИС. 19.
РИС. 20.
РИС 21.
300
Г. Джонс, Э. Ллойд
а ё ft и / = 0, 1, ... , г - 1 множество {/3 е ftl(a, /3) е Д,) всех
вершин /3, являющихся конечными точками ребер в графе Г( и начинающихся у
а, является орбитой стабилизатора Ga; для / = 0 эта орбита - просто (а).)
Группа G переставляет ^множество вершин ft, оставляя каждое множество
вершин Д( неизменным, следовательно, G < aut Г( для каждого / (где <
обозначает подгруппу данной группы); это показывает, что граф Г, как
вершинно-, так и реберно-транзитивен. Для каждого / Д* = [ф, а)1(а, /3) е
Д,) является орбитой G, таким образом, Д* либо не пересекается с Д(, либо
эквивалентно ему; в последнем случае мы говорим, что орбита ДД= Д*)
является самодвойственной, и, заменяя каждую пару *<$>Р направленных
ребер (а, 3) и ф, а) одним ненаправленным ребром (а, /3), мы можем
рассматривать граф Г, (= Г*) как ненаправленный граф (который все еще
является вершинно- и реберно-транзитивным при G < aut Г()
Например, если G - группа симметрии ?>4 квадрата и ft - множество из
четырех вершин, то имеются г = 3 орбиты на ft X ft, состоящие из всех (а,
/3), таких, что а и 3 соответственно равны, смежны или противоположны.
Все орбиты Д, являются самодвойственными, и полученные графы Г, показаны
на рис. 22.
В качестве другого примера мы покажем, как таким путем получить
реакционный граф ГА (см. рис. 14). Используем в качестве а граф Е,
показанный на рис. 1, и пусть G будет группой S5, действующей на класс
изоморфизма ft = ft?. Тогда ft? содержит граф F (рис. 23), изоморфный Е
при перестановке g = (12)(35) е S5 (среди других) или, что эквивалентно,
при 1,2-сдвиге. При стабилизаторе точки Ga = aut Е четырехэлементная
группа F отображается в графы, показанные на рис. 24. Таким образом, F
лежит на Сгорбите размерности 4, поэтому, если Г - соответствующий
суборбиталь-ный граф [с орбитой множества ребер Д группы S5, содержащей
(Е, F)], Г имеет внешнюю валентность 4. Теперь перестановка
(12)(35) переводит Е в F, и, так как g имеет порядок 2, эта перестановка
также переводит F в Е, следовательно, она переводит (?, F) в (F, Е).
Таким образом, (?, F) и (F, Е) лежат на одной и той же орбите группы S5
на ft х ft, поэтому Д* = Д и Д - самодвойствен-
2
РИС 22
РИС 23
Группы автоморфивмов химических графов
301
ная орбита. Так, например, Г - ненаправленный граф, транзитивный по
вершинам и ребрам, с валентностью 4, с 30 вершинами и с группой
автоморфизмов, содержащей S5. Графы Е', F' связаны ребром в Г, если и
только если существует изоморфизм g е S5, переводящий Е в Е' hFbF, или,
что эквивалентно, если F' может быть получен из графа Е' заменой ребер
таким же образом (вплоть до изоморфизма), как граф F может быть получен
из графа Е. Следовательно, Г - пример "реакционного графа", определенного
указанным выше преобразованием Е в F, а значит, Г - это граф ГЛ,
изображенный на рис. 14. '
В более общем случае мы можем принять G = Sn. Эта группа действует на
класс изоморфизма QE данного графа Е с п вершинами. Выбирая
"перегруппированный граф" F = Е, мы получаем суб-орбиГальный граф Г
(направленный или ненаправленный) с множеством вершин Я?; это реакционный
граф, соответствующий преобразованию Е - F, и, согласно общим свойствам
суборбитальных графов, описанных выше, aut Г содержит группу Sn, так что
Г транзитивен по вершинам и ребрам.
Представляет интерес один вопрос: при каких обстоятельствах реакционный
граф является связным? Мы не можем дать полный ответ на этот вопрос, но в
литературе имеются результаты, дающие некоторую информацию.
Если G - любая группа, действующая транзитивно на множество Q, то G
действует импримитивно, при условии что множество Q может быть разбито на
блоки Ф,, Ф2, ... , Фк (к > 1), все одного размера IФ, I > 1, такие, что
G переставляет блоки, т.е. каждый g е G переводит блоки Ф( в блоки ФJ; в
противном случае G действует примитивно. Например, G = DA действует
