Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
схемы обрезки. Рассмотрим теперь обрезанное дерево, изображенное на рис.
2. Все его вершины, имеющие один и тот же символ, могут быть переставлены
между собой, поскольку этот процесс будет оставлять матрицу смежности
дерева неизменной. Предположим, что Htj - группа симметрии фрагмента Т .
Пусть G - группа симметрии дерева Q . В этом примере Ни = S2, H2l = S3 и
//3, = ?,, где Sn - группа перестановки, содержащая п) элементов, и Еп -
группа идентичности, действующая на п элементов. Группа симметрии дерева,
показанного на рис. 1, является просто сплетением G, с Ни, Н21 и Нп. Если
сказанное выше выразить в символах, то получим
G = Gt (3)
где G - группа симметрии дерева, показанного на рис. 1. Этот процесс
может быть повторен. Дерево, изображенное на рис 2, может обрезаться
далее до получения дерева Q2 и фрагмента Ti2> представленных на рис. 3.
Таким образом, если G2 - группа симметрии дерева Qz и НХ2 - группа
симметрии фрагмента ^2. то
G, == С2[Я12]. (41
В этом примере G2 - S2 и Цп = S2. Следовательно, группа симметрии дерева,
показанного на рис. 1, задается соотношением
G = S2[S2](S2, S3, ?,). (5)
Таким образом, процесс обрезки деревьев позволяет охарактеризовать группы
симметрии любого дерева. В общем случае пусть Г - дерево, с которого мы
начинаем процесс обрезки, и Q} - дерево, полученное при у-й итерации
обрезки. Пусть ( Т , i = 1, 2, ...} - множество фрагментов (типов),
полученных на j-й итерации. Пусть - группа симметрии QJt и пусть Нц -
группа симметрии Т Тогда мы имеем следующее соотношение, связывающее
группу симметрии дерева на О - 1)-м и j-м шагах итерации:
G,_, = СДЯ,,,/^, ...]. (6)
Процесс обрезки может повторяться до тех пор, пока не будет получено
простое дерево, группа симметрии которого определяется тривиально.
Симметрия и спектры графов
283
4. СПЕКТРАЛЬНЫЕ ПОЛИНОМЫ ДЕРЕВЬЕВ,
ПОЛУЧАЕМЫЕ С ПОМОЩЬЮ ПРОЦЕССА ОБРЕЗКИ
Вековой определитель матрицы смежности известен как характеристический
полином или спектральный полином графа. Собственные значения матрицы
смежности образуют спектр графа. Спектральный полином графа является
инвариантом графа в том смысле, что он не зависит от нумерации вершин.
Характеристические полиномы, спектральные моменты и подсчет случайных
блужданий настолько связаны между собой, что изучение одного может
привести к определению свойств другого.
Схема обрезки деревьев служит естественным путем получения
характеристического полинома дерева из характеристического полинома
обрезанного дерева и характеристических полиномов фрагментов.
Предположим, что Q - дерево, полученное на одном из шагов обрезки, и Т -
соответствующие фрагменты. Пусть Н1 - характеристический полином
фрагмента Tt, а Я/ - характеристический полином фрагмента T(t полученного
при удалении корней Тг Пусть вершины дерева Q разбиты на множества Yl,
Y2, ... таким образом, что все вершины в У(, если они присоединены к
копии одного и того же фрагмента, образую" исходное дерево. Определим
матрицу А следующим образом:
Определитель матрицы А является характеристическим полиномом исходного
дерева. Преимущество этого метода состоит в том, что он определяет
характеристический полином большого дерева с помощью характеристических
полиномов меньшего дерева [39, 48].
Описанный выше процесс может быть повторен до получения достаточно малого
дерева, такого, что его характеристический полином может быть легко
определен. Пусть Qy - дерево, полученное нау-й итерации, а Т - тип
фрагмента, полученного нау-й итерации. Пусть вершины дерева Q разбиты на
множества YtJ таким образом, что все вершины, принадлежащие множеству У ,
присоединены к копии одного и того же типа фрагмента Т . Пусть tffl -
матричный элемент матрицы смежности Т Тогда матрицу D(,'A определим
следующим образом
А
Нк, если i - у и i e Yk,
~Hkq:j, если i Ф j и i е Yk.
(7)
если I = tn и I € У* ,,
если ' Ф m и I е Y( _,,
(8)
284
К. Баласубраманиан
вековой определитель матрицы D(k
,j-1)
вековой определитель матрицы D'(k<J lj. строки и столбца в матрице
и Не-
которая получена удалением
соответствующих
Тк Нк. - просто характеристический полином типа тк
корню . Если
тип Тк1 содержит i вершин, то этот характеристический полином будет
обозначаться как А(, а полином, полученный при удалении как h'r Отметим,
что в общем случае h: = х' - (/' -
корня Г,
к\"
1-1
- 1)х'~2 и h[ = х
Процесс обрезки может быть повторен. Предположим, что п - последний шаг
обрезки. Тогда матрицу А определим следующим образом:
л!т
я.
кп >
¦щп
ч1
если
если
/ = т I Ф т
le Y,
к, п >
/е К
(9)
где - элементы матрицы смежности дерева Qn, полученного при последней
итерации. Найденный выше определитель матрицы А является
характеристическим полиномом дерева, с которого мы начинали процесс
обрезки.
Проиллюстрируем эту процедуру на примере дерева, показанного на рис. 1.
Это дерево разрезается на дерево, представленное на рис. 2, и в конце
концов на дерево, показанное на рис. 3, на втором шаге итерации. Все
