Обрезка деревьев и группы симметрии деревьев

Процесс обрезки может повторяться до тех пор, пока не будет получено простое дерево, группа симметрии которого определяется тривиально. [c.282]

Метод обрезки деревьев и графов использован для получения групп симметрии и спектров графов, представляющих интерес для химии. Группы симметрии некоторых графов могут быть вложены в обобщенные сплетения групп. Показано использование этого метода в некоторых областях химической физики, таких, как спектроскопия ЯМР, статистическая механика и т. д. С помощью методов, описанных здесь в обшил чертах, могут быть легко получены спектральные полиномы некоторых графов. [c.278]

ОБРЕЗКА ДЕРЕВЬЕВ И ГРУППЫ СИММЕТРИИ ДЕРЕВЬЕВ Матрица смежности графа определяется следующим образом [c.281]

Листья дерева (вершины степени 1), присоединенные к одной и той же вершине, могут быть переставлены между собой, и это будет сохранять матрицу смежности неизменной. В этом процессе обрезки дерева все листья, присоединенные к корню (или к разветвлению), обрезаются совместно. Таким образом, обрезка деревьев позволяет определять группу симметрии любого дерева. Рассмотрим, например, дерево, показанное на рис. 1. Вершины 1, 7 и 8 могут быть переставлены между собой всеми возможными способами. [c.281]

Таким образом, процесс обрезки деревьев позволяет охарактеризовать группы симметрии любого дерева. В общем случае пусть Г — дерево, с которого мы начинаем процесс обрезки, и Qj — дерево, полученное при У-й итерации обрезки. Пусть T.j, i = 1, 2,. ..) — множество фрагментов (типов), полученных нау-й итерации. Пусть G, — группа симметрии Qj, и пусть Я — группа симметрии T-j. Тогда мы имеем следующее соотношение, связывающее группу симметрии дерева на (J - 1)-м и j-м шагах итерации [c.282]

При ЭТОМ матрица смежности дерева будет оставаться неизменной. Аналогично вершины 9 и 10 могут быть переставлены между собой. Таким образом, любая перестановка листьев, присоединенных к одной и той же вершине (корню) дерева, оставляет дерево неизменным. На этой идее основано применение схемы обрезки. Рассмотрим теперь обрезанное дерево, изображенное на рис. 2. Все его вершины, имеющие один и тот же символ, могут бь1ть переставлены между собой, поскольку этот процесс будет оставлять матрицу смежности дерева неизменной. Предположим, что Н-- — группа симметрии фрагмента T-j. Пусть Gj — группа симметрии дерева Qj. В этом примере Я,, = S , Я , = Sj н = ,, где — группа перестановки, содержащая и элементов, тл — группа идентичности, действующая на п элементов. Группа симметрии дерева, показанного на рис. 1, является просто сплетением G, с Я,,, Я,., и Яз,. Если сказанное выше выразить в символах, то получим [c.282]

Справочник химика 21

Химия и химическая технология