Научная литература
booksshare.net -> Добавить материал -> Химия -> Кинг Р. -> "Химические приложения топологии и теории графов " -> 109

Химические приложения топологии и теории графов - Кинг Р.

Кинг Р. Химические приложения топологии и теории графов — М.: Мир, 1987. — 560 c.
Скачать (прямая ссылка): himicheskieprilojeniya1987.djvu
Предыдущая << 1 .. 103 104 105 106 107 108 < 109 > 110 111 112 113 114 115 .. 216 >> Следующая

ЭВМ, теория графов играет важную роль, особенно если интерес представляет
аналитическое поведение спектров собственных значений для химических
систем как функции некоторых переменных. По этой причине изучение
спектров графов оказывается полезным, несмотря на доступность современных
ЭВМ. Например, Кинг [31] показал, что аналитическое поведение динамики
колебательных химических реакций может быть прогнозировано в результате
исследования вида спектров соответствующих диаграмм, известных как
диаграммы влияния.
Спектры графов широко применяются в химической кинетике [32] и при
решениях уравнений Навье - Стокса [33]. Характеристические полиномы
графов являются производящими функциями для димеров на соответствующих
решетках и, таким образом, должны быть полезными в статистической
механике.
Одна из целей настоящей статьи - показать использование методов обрезки
для определения симметрии и спектров графов. Метод обрезки использовался
автором данной работы при перечислениях изомеров [34-36], в спектроскопии
ЯМР [37] и для получения групп симметрии и характеристических полиномов
графов [38-40]. В настоящее время автор и Рандич расширяют схему .обрезки
для того, чтобы включить структуры с неэквивалентными взаимодействиями.
2. ОБРЕЗКА ДЕРЕВЬЕВ
Напомним, что дерево - это связный граф, не имеющий циклов. Вершины
дерева со степенью (валентностью) 1 могут быть определены как листья
дерева. Вершины со степенями, ббльшими 1, могут быть определены как корни
или разветвления дерева. Развет-
* См., например, обзоры [49*, 50*] - Прим. перев
** См. также [49*]. - Прим. перев.
280
К. Баласубраманиан
9 Ю
13 14
17
19
РИС I Дерево с 22 вершинами.
вление и связанные с ним листья совместно образуют ветвь. Любое дерево
может быть обрезано у такого разветвления с образованием меньшего дерева
и ветвей или фрагментов. Для примера рассмотрим дерево Г на рис. 1.
Вершины 1, 7, 8, 9, 10, 13, 14, 6, 21, 22, 19, 20, 17 и 16 являются
листьями, а вершины 2, 3, 4, 5, 11, 12, 15 и 18 - корнями и
разветвлениями. Когда дерево, показанное на рис. 1, обрезается в
разветвлениях 2, 3, 4, 5, 11, 12, 15 и 18, получаются меньшее дерево Q1,
изображенное на рис. 2, и фрагменты Тп , Т21 и Т31. Отметим, что все
аналогичные фрагменты помещаются в один "ящик". Точно так же дерево,
изображенное на рис. 1, может быть получено присоединением корней 1 и 8
дерева Q,, показанного на рис. 2, к корню копии Г,,, корней 2, 3, 6 и 7 -
к корню копии Г2,и корней 4 и 5 - к корню Т31. Формулировка такого
продукта была дана Баласубраманианом [34], который назвал его продуктом
корень-к-корню. Процесс обрезки дерева, изображенного на рис. 1, приводит
к намного меньшему дереву (рис. 2) и к фрагментам, полученным в процессе
обрезки. Как нами будет показано здесь, преимущество такой процедуры
обрезки состоит в том, что некоторые теоретико-графовые свойства большего
дерева могут быть получены исходя из соответствующих свойств обрезанного
дерева и меньших фрагментов. Процесс обрезки может повторяться до тех
пор, пока не будет получено очень простое дерево, свойства которого
определяются легко. Рассмотрим, например, дерево, изображенное
Симметрия и спектры графов
281
2
3
8
Г11 Г21 ^1
°г Тп
иИС 2 Дерево Qj и типы фрагментов РИС 3 Дерево Q2 и тип фрагмента Тп,
Г,,, 7"21 н Тм, полученных в результате полученного на втором шаге
обрезки
обрезки дерева, показанного на рнс. 1.
на рис. 2. Это дерево может быть разрезано дальше на дерево Q2,
показанное на рис. 3, и фрагмент Тп. Дерево Q2 имеет только две вершины,
и, таким образом, свойства дерева Q2 и фрагмента Т12 могут быть
определены очень легко. Цель настоящей работы - показать, как такой
процесс обрезки деревьев может быть использован для получения некоторых
интересных теоретико-графовых величин.
3. ОБРЕЗКА ДЕРЕВЬЕВ И ГРУППЫ СИММЕТРИИ ДЕРЕВЬЕВ Матрица смежности
графа определяется следующим образом:
1, если вершины / и j связаны друг с другом,
О в противном случае.
Говорят, что перестановка вершин графа принадлежит к его группе симметрии
(или группе автоморфизмов), если перестановочная матрица Р этой
перестановки удовдетворяет соотношению
Листья дерева (вершины степени 1), присоединенные к одной и той же
вершине, могут быть переставлены между собой, и это будет сохранять
матрицу смежности неизменной. В этом процессе обрезки дерева все листья,
присоединенные к корню (или к разветвлению), обрезаются совместно. Таким
образом, обрезка деревьев позволяет определять группу симметрии любого
дерева. Рассмотрим, например, дерево, показанное на рис. 1. Вершины 1, 7
и 8 могут быть переставлены между собой всеми возможными способами.
(1)
РАР~1 = А.
(2)
282
К. Баласубраманиан
При этом матрица смежности дерева будет оставаться неизменной, Аналогично
вершины 9 и 10 могут быть переставлены между собой. Таким образом, любая
перестановка листьев, присоединенных к одной и той же вершине (корню)
дерева, оставляет дерево неизменным. На этой идее основано применение
Предыдущая << 1 .. 103 104 105 106 107 108 < 109 > 110 111 112 113 114 115 .. 216 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed