Инварианты графов и их применение к водородно-связанным кластерам (H2O) X

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Химия
Вестник Нижегородского университета им. Н. И. Лобачевского, 2007, № 6, с. 59−64
59
УДК 544. 13
ИНВАРИАНТЫ ГРАФОВ И ИХ ПРИМЕНЕНИЕ К ВОДОРОДНО-СВЯЗАННЫМ КЛАСТЕРАМ (Н20)х
© 2007 г. А. Г. Разуваев, С. К. Игнатов, О. Б. Гаджиев, О.А. Усачева
Нижегородский госуниверситет им. Н.И. Лобачевского
ignatov@ichem. unn. ru
Поступила в редакцию 05. 11. 2007
Метод оценки энергии и термодинамических параметров водородно-связанных кристаллических структур, основанный на теории инвариантов графов, развивается для решения задачи о вычислении величины покрытия и термодинамических параметров молекул, адсорбированных на поверхности твердого тела, способного к образованию ориентационных изомеров. В работе приводится формулировка основных положений теории в более общей форме по сравнению с опубликованными ранее и проводится их адаптация к задаче перечисления адсорбционных структур на поверхности водородносвязанных кристаллов. Новый подход апробируется на примере гексамера воды (Н20)6 октаэдрической
конфигурации.
Введение
Изучение адсорбции и кинетики реакций на поверхности твердого тела, в частности водородно-связанных кристаллов и аморфных тел, является фундаментальной задачей современной физической химии. Интерес к ней возрос в последние годы в связи с моделированием физико-химических процессов в земной атмосфере, где, как предполагается, кластеры воды и микрочастицы льда могут играть роль катализаторов, существенно ускоряющих химические реакции по сравнению с газофазными условиями [1]. С точки зрения теории задача предсказания термодинамических параметров адсорбции и кинетических параметров реакций на поверхности водного льда и льдоподобных кластеров обладает важной особенностью — структурная разупорядоченность сетки водородных связей приводит к возникновению огромного числа изомеров, каждый из которых дает свой вклад в кинетические и термодинамические параметры [2]. Оценка термодинамических параметров такой системы путем простого перебора невозможна. Ранее для решения этой задачи был предложен алгебраический подход, основанный на теории инвариантов графов [3]. В его основе лежит идея нахождения таких элементов структуры (инвариантов), из которых аддитивно складываются скалярные свойства (например энергия и термодинамические функции) любой водородно-связанной структуры определенного класса. Ранее такой подход был успешно применен к описанию изолированных кластеров в газовой фазе [3]. В данной работе формализм инвариантов графа развивается таким образом,
чтобы приблизить его к решению задачи о вычислении величины покрытия и термодинамических параметров адсорбции на поверхности твердого тела. Целью работы является формулировка основных положений в более общей форме и адаптация их к задаче перечисления адсорбционных структур на поверхности водородно-связанных кристаллов.
1. Задание кластеров льда графами
Рассмотрим модель водородно-связанной структуры, где атомы кислорода находятся в узлах плоской квадратной решетки, между которыми на отрезках 0−0 вблизи одного из атомов кислорода находятся атомы водорода. Положения атомов Н в решетке подчиняются «правилам льда» [4]: на каждой связи находится только один атом Н, а вблизи каждого узла -только два атома Н. На рис. 1 приведён пример такой структуры (т.н. «квадратный лед»), где для атомов О с номерами 1,…, 12 указана ориентация атомов Н по О-О-связям. Атомы будем считать вершинами графа и нумеровать числами 1, 2, ., х, связь 0-Н .0 изображать ребром, соединяющим соответствующие вершины. Для фрагмента (Н2О)4, выделенного на рис. 1, граф определён на вершинах 1, 2, 3, 4, а для задания «разорванных» связей концы таких ребёр считаем идущими в «фиктивные» вершины с номерами 5, ., 12 тех атомов О, с какими они были связаны в кристалле. Полученный неориентированный граф обозначаем у и называем графом кислородного остова кластера (Н2О)4. Положение молекулы Н2О будем задавать ориентацией ребер: если в кластере О-О связь образована
между двумя атомами кислорода с номерами і и у и атом Н ковалентно связан с атомом О с номером і, то направление ребра считаем идущим от і к у. На рис. 2 изображен граф у кластера (Н2О)4 и ориентируемый граф Г1, задающий положение молекул воды как во фрагменте на рис. 1.
Рис. 1. «Квадратный лёд». Атомы кислорода
О находятся в узлах квадратной решётки, а водорода • - на водородных связях. Фрагмент (Н2О)4 выделен пунктирной линией
6
12
11
Рис. 2. а — Неориентированный граф у кислородного остова (Н2О)4 определён на вершинах 1, 2, 3, 4. Нумерация 5,…, 12 отвечает фиктивным вершинам графа. б — Ориентированный граф Г 1, задающий ориентацию молекул воды
5
а
б
В общем случае кластера (Н2О)х граф у будет определен на х вершинах, а задание ориентации молекул Н2О сводится к построению на у ориентированного графа Г, причем «правило льда» означает, что с каждой вершиной связаны два входящих и два выходящих ребра: степень входа-выхода равна двум. Всюду далее будем считать, что построенный на у ориентированный граф Г удовлетворяет этому условию.
Каждый кластер (Н2О)х может иметь много изомеров, различающихся ориентацией молекулы Н20. В терминах графов задача перечисления всех изомеров сводится к задаче перечисления всех возможных ориентированных графов Г, которые можно построить на данном у.
2. Алгоритм перечисления
В неориентируемом графе у с каждой вершиной связаны четыре ребра. Каждому ребру, соединяющему вершины і и у (включая «фиктивные» вершины), приписываем символ ау, если і& lt-у, и -ау в противном случае. С каждой вершиной связывается четверка символов, которые записываем в порядке возрастания вторых индексов. Для кластера (Н2О)х такие 4х четверок формируем в виде строки в порядке возрастания номеров вершин. Полученный 4х-мерный вектор называем каноническим вектором. Например, для графа у на рис. 2а канонический вектор есть:
(а12,а14,а15,а1б I -а12,а2з, а27, а281 -а2з, аз4, аз9,аз, 101 -а14,-аз4,а4,ц, а4,12).
От двойной индексации в обозначениях координат вектора переходим к одинарной, заменяя символы ау на Ьг, г= 1, 2, …, где индекс г увеличивается от первой координаты. Новую запись называем стандартной записью канонического вектора:
(Ь1,Ь2,ЬзЬ4 I -Ь1,Ь5,Ьб,^7 I -Ь5,Ь8,Ь9,Ью I
-Ь2,Ь8,Ьп, Ьп).
Канонический вектор позволяет «закодировать» любой ориентированный граф Г в виде вектора Г. Для этого каждому символу Ьг=ау-приписываем значение 1, если ребро выходит из
і и у, и -1 в противном. Например, для графа Г1, заданного на рис. 2б, вектор Г1 есть:
Г1=(1,1,-1,-1 I -1,-1,1,1 I 1,1,-1,-1 I -1,-1,1,1).
Поскольку степень входа-выхода в любом графе Г равна двум, то с каждой вершиной может быть связано одно из шести распределений: 1: (1,1,-1,-1) — 2: (1,-1,1,-1) — 3: (1,-1,-1,1) —
4: (-1,-1,1,1) — 5: (-1,1,-1,1) — 6: (-1,1,1,-1). (1)
Алгоритм перечисления состоит в последовательном присвоении каждой четверке коор-
динат канонического вектора всех возможных распределений. Так, например, могут быть получены векторы:
Г2=(-1,1,1,-1 I 1,-1,1,-1 I 1,1,-1,-1 I -1,-1,1,1),
Гз=(-1,-1,1,1 I 1,-1,-1,1 I 1,-1,1,-1 I 1,1,-1,-1).
С учетом нумерации четверок (1) каждый из 16-мерных векторов Гі, Г2, Гз можно «свернуть» в четырехмерный вектор: Г1 = [1, 4, 1, 4], Г2 = [6, 2, 1, 4], Гз = [4, з, 2, 1]. Такая сокращённая запись будет использована в дальнейшем.
Предлагаемая процедура на языке векторов Г позволит построить множество 3 всех ориентируемых графов Г, которые можно образовать на данном у. Это эквивалентно заданию списка 3 всех изомеров кластера (Н2О)х, которые различаются положением молекул воды на данном каркасе кислородного остова.
3. Симметрия кластеров
Пусть кластер (Н2О)х обладает группой симметрии G кислородного остова у. Наличие группы приводит к тому, что в списке 3 всех изомеров кластера будут одинаковые — симметрично эквивалентные структуры. На языке графов: если gєG, то в результате такого преобразования симметрии граф Г перейдет в граф Гг. Действие всех элементов g1, g2, … єG приводит к образованию орбиты Г^, Гё2, … на множестве 3. Задача перечисления всех различных изомеров сводится к задаче определения числа всех орбит на 3.
Рассмотрим пример гексамера (Н2О)6 с группой симметрии G = D2d. Граф у кислород-
ного остова приведён на рис. 3. Согласно выбранной нумерации вершин у, стандартная запись канонического вектора есть:
(61, 62, Ьз, Ь4 | -61, 65, Ьб, Ь- | -65, & amp-8, 69, Ью |
-Ь2, -Ь%, Ьц, 612 | -Ьб, — Ьц, 613, 614 |
-Ьз, -69, 615, Ь1б). (2)
Использование этого вектора в процедуре перечисления дает список 3, состоящий из 194 векторов Г. Теория групп дает 27 орбит (27 различных изомеров) гексамера (Н2О)6. В терминах векторов Г их список приведён ниже (3):
Г1=
Г2
Гз:
Г4:
Гз
Г6
Гг
Г*
Г9
[1, 4, [1, 4, [1, 4, [1, 4, [1, 4, [1, 4, [1, 4, [1, 4, [1, 4,
Г ю=[1, 4 Гц=[1, 5 Г12=[1, 5 Г 1з=[1, 5 Г14=[1, 5
1, 4, 4, 1]
2, 5, 5, 2] 2, 5, 5, з] 2, 5, 6, 2]
2, 5, 6, з]
2, 6, 4, 2]
2, 6, 4, з]
3, 5, 5, 1] з, 5, 6, 1]
, з, 6, 4, 1], 4, 5, 1, 2], 4, 6, 2, 2], 4, 6, 2, з], 4, 6, з, 2]
Г15=
Г16=
Г17=
Г18=
Г19= Г20= Г21= Г22= Г2з= Г24= Г25=
Г26=
Г27=
1, 5, 4, 6, з, з]-
1, 6, 4, 6, 4, 2]
2, 5, 5, 2, 2, 5] 2, 5, 5, 2, 2, 6] 2, 5, 5, 2, з, 5] 2, 5, 5, 2, з, 6] 2, 5, 5, з, 1, 5] 2, 5, 5, з, 1, 6] 2, 5, 6, 2, 2, 4] 2, 5, 6, 2, з, 4] 2, 5, 6, з, 1, 4]
2, 6, 6, 2, 4, 4]
3, 5, 5, з, 1, 1].
(3)
Предложенный выше алгоритм (составление списка 3, построения орбит на 3 с последующим выбором их представлений, т. е. решение задачи перечисления всех различных изомеров кластера (Н2О)х) требует хранения списка 3 и попарного сравнения элементов из 3. С ростом х список 3 всех изомеров кластера (Н2О)х становится огромным. Согласно оценке Полинга,
18
для (Н2О)100 число элементов 3~10 [5]. Оче-
видно, что для больших х хранение массива 3 и попарное сравнение элементов в нем становится практически нереальным.
В работе [3] был предложен метод инвариантов графов, позволяющий в ряде случаев сократить объём вычислений. Ниже предложен «орбитальный» подход к определению инвариантов графа, что позволяет доказать ряд их свойств, используемых в дальнейшем.
4. Инварианты графа. Орбитальный подход
Пусть Б={Ь,…, Ьп} есть множество рёбер ориентированного графа Г и О — конечная группа порядка О с единичным элементом g1=e. Действие О на ?, т. е. отображение Ох ?^?, удовлетворяющее условиям g1 (ЬГ)=ЬГ и gpa (Ь=р (Ьг)) для любых ga, gp О О считаем заданным, причём полагаем ga (Ьг)= ± Ь и знак плюс берём, когда рёбра ga (Ьг) и Ь имеют оди-
наковую ориентацию в Г, и минус в противном случае. С точностью до знака действие каждого gа О G сводится к перестановке рёбер графа и относительно действия G множество 5 будет распадаться на некоторое число р орбит ^(1), …, F (p). Переобозначая элементы 5 так, чтобы в каждой орбите они шли в порядке возрастания индексов, запишем 5 в виде:
5 = {Л1,…, Л1} и… и {//,… /}, (4)
где І1 + ^+Ір=п и li=F (i) — длина орбиты F (і) = {/1,…, /і }. Элементы F (i) будем рассматривать как базисные векторы линейного пространства V1 размерности Іі.
На базисе F (i) определим вектор Jlг є Vі как линейную комбинацию:
ЛГ = 1 gа (/Г). где Г = 1 Іг. (5)
а
Определение (5) задаёт систему, состоящую из п векторов Jгг. Ниже рассматриваются свойства этих векторов и дан простой алгоритм поиска базы в этой системе.
Каждый вектор ЛГ есть результат симметризации базисного вектора ЗГ О F (i) по единичному представлению группы G и, следовательно, gр Л- для любого gр О G. Каждый такой век-
тор будем называть инвариантом 1 -го порядка
ЛГ. Среди Іі инвариантов Л1,…Л, определён-
ч
ных на орбите F (i), лишь один, например Л, будет уникальным. Точнее, справедливо свойство:
10 Для любого Г = 1, Іі Л1= ± ЛГ.
Действительно, пусть gр /1)= ± /Г. Тогда
для любого ga О G:
ga (/1і)) = ga (±/rl) = ± ga (/г). Поэтому:
Л1 = I gу (Я) = I gаgp (/1) =
у а
= ±! gа (/Г) = ±Лг.
а
Рассмотрим инвариант Л. Т.к. |G| & gt- Іі, то в сумме (5) с точностью до знака могут возникать одинаковые слагаемые: ga (/1 1) = gр (/1) и их число будет равным М (і) — порядку стабилизатора G (/11) О G элемента /1 О F (i), т. е. М (і)= =|G (/1 1)|=^(і)|& quot-^|. Это позволяет записать (5) в виде разложения по базису F (i):
Л1 = А1/1 +… + А Л +… +Аіі Л, & gt- (6)
где каждое слагаемое в (6) с номером t определяется суммой тех М (і) слагаемых из (5), для которых:
ga1 (/1) = +//& gt-… >- gaN (г)) = ±Л. (7)
Пусть в последовательности (7) найдётся такая пара $а, gp О О, что ga /Х) = //, g^ С/1г) = / Тогда из равенства ga /Х) = /Х)
следует существование такого gr = g/g ga, что gyf 1) = -/1. Согласно [3], в этом случае / = 0, т. е. все коэффициенты А (- координаты вектора /1 — нулевые. В противном случае А (= +N (1). Этим доказано следующее свойство инвариантов:
20 Вектор /1 либо нулевой, либо все его координаты с точностью до множителя #(/)=|^(/)|-1|О| равны +1, где |?(/)|=/г -длина орбиты ?(г).
Свойства 1 0, 20 инвариантов позволяют, в частности, легко решать задачу поиска базы — минимальной системы линейно независимых инвариантов /Д Согласно 10, достаточно рассматривать только «первые» инварианты /. Поскольку ненулевые векторы и З, отвечающие различным (/^/) орбитам, линейно независимы, то перечисление всех линейно независимых инвариантов вида (2), согласно свойству 20, сводится к отбрасыванию из системы /Д…, /1 нулевых векторов.
Для любой пары орбит ?(1), ?(7) определим
множество формальных произведений С* =
= / • Л, считая выполненным условие симметрии:
с* = С*. (8)
Множество С (/, 7) = {СЦ,…, С*,…, С*, } рассмотрим как базис линейного пространства V 11. Условия симметрии (8) позволяют сделать следующие замечания. Во-первых, для гф] в пространстве Vг размерности 1у=Щ можно всегда полагать г& lt-]. Во-вторых, при г=1 для базисных
векторов Ск е С (г, ]) можно считать, что Ъ& lt-к и, следовательно, размерность Vг равна
к = 2 Ь (1г +1).
Определим действие группы О на С (г, 1) по закону:
ga (С*) = ga (/)ga (/к).
Относительно действия О на С (г, 1) это множество распадается на некоторое число орбит ^(г,/),…, ?ч (г, 1) и, аналогично обозначениям, введённым в (4), представим С (г, 1) в виде:
С (г, 1) = {/?,…, /у и… и /,…, /*,},
где т1+. +тя=1г/ и т=-(1,1)| - длина орбиты
? (г, 1) = {/1!,… ,/I}.
Аналогично определению инварианта 1-го порядка /Г (5) на каждой орбите -Хг'-/) определим инварианты 2-го порядка:
// = Xga (/И) =1 ga (Л)ga (//), (9)
a a
где Г = 1, т* как векторы из пространства V7. Общее число векторов для всех 1 & lt- г & lt- / & lt-р
равно — п (п + 1). Поиск базы в этой системе
векторов и координатное описание структуры каждого такого вектора определяются свойствами 1 0 и 20, которые здесь принимают форму:
т.д. Каждый инвариант вычисляется согласно определений (5), (9), (10). Например:
/г = Ь3 + Ь6 + Ь9 + Ь11,
/12 = Ь3Ь6 + Ь3Ь11 + Ь6Ь9 + Ь9Ь11,
/12 = Ь3Ь14 + Ь9Ь13 + Ь11Ь16 + Ь15Ь16,
/123 = Ь1Ь2Ь10 — Ь1Ь5Ь12 + Ь2Ь7Ь8 — Ь1Ь5Ь8.
Применение свойства 20 к инвариантам первого и второго порядков позволяет легко проверить, что среди них будет 24 независимых:
/ 2 / 3 / 4 /11 /11 /11 /12 /12 /13 /13
31, 31, 31, /11, 312, /14, /11, /12, /11, З13 ,
т14 т14 Л 22 Л 22 Л 2з т 2з т 24 т 24 т 33 Л11, Л12, Л11, Л12, Л11 ' Л12 ' Л11 ' Л12, Л11 '
Л зз л 34 т 34 т 44 т 44
•& gt- Л11 5 Л12' Л11 ,
(11)
10 Для каждого г = 1, т*.
20 Вектор /1* размерности I/ либо нулевой, либо все его координаты с точностью до множителя. Щ/, 1'-)=|-Хг'-, /)|- |О| равны +1, где |?ж (г'-, /)| = т* - длина орбиты? ж (г'-, /). Алгоритм поиска всех линейно независимых
инвариантов из системы — п (п +1) векторов
/1* такой же, как описанный выше алгоритм
для инвариантов /гг.
Определение инвариантов /Г (5) первого и
(9) второго порядков очевидным образом
распространяется на инварианты высших порядков:
7 =Х ga (/Г ^ (/Ь)… &-, /), (10)
a
которые обладают свойствами, аналогичными
00
свойствам 1, 2, доказанным для инвариантов и /11*.
5. Метод инвариантов
Использование инвариантов в задаче перечисления различных изомеров кластера (Н2О)х рассмотрим на примере гексамера (Н2О)6. Множество 5 состоит из символов Ь1, …, Ь16 ребер графа у, выбранных стандартной записью канонического вектора (2). В результате действия группы О=и2й множество 5 распадается на четыре орбиты:
?(1)={Ьь 62, 65, Ь8}, ?(2)={Ьз, Ь6, 69, Ь"},
Ь7, Ь10, Ь12} Ь14, Ь15, Ь16}.
Согласно свойства 1 0 инвариантов, достаточно рассмотреть инварианты /, /1* (г'- & lt- /) и
12 11 12 11 12
00
С использованием свойств 1, 2 также вычисляются все 121 линейно независимые инварианты третьего порядка (і & lt- у & lt- к) и т. д.
Задание графа Г определяется заданием вектора Г с координатами ЬГ= ±1, что позволяет говорить о значении инварианта на графе Г. Так, например, для графов Г1 и Г2 из списка (3)
т-2 т-22 т-24
значения Л, Л12, есть:
12
(12)
/2 (г)= 0, /22 (г)= -4, /24 (г)=-4,1 /? (а)= 0, /22 (г 2)= 0, (Г2)= 0.
Значения всех инвариантов на графах, принадлежащих одной орбите множества 3, совпадают. Однако обратное не верно: если графы Га и ГЪ принадлежат различным орбитам множества 3, то может оказаться, что найдется такой инвариант /, что /(Га)=/(ГЪ). Пример из (12):
/ 2 (г ,)= / 2 (г 2).
Определение полной системы инвариантов: подмножество Р из множества инвариантов первого, второго и т. д. порядков будем называть полной системой, если для графов Га и ГЪ из разных орбит множества 3 найдется такой инвариант / е3, что /(Га) ^ / (Г ъ).
Для кластера (Н2О)б полная система может быть получена, например, присоединением к множеству из 24 инвариантов (11) трех из 121
т-113 т-123 г234
инвариантов третьего порядка: /123, /112, /123.
Если известна полная система Р, то задача перечисления всех различных изомеров кластера (Н2О)х не требует хранения списка всех векторов Г, задающих структуру каждого отдельного кластера, и исключает процедуру сравнения элементов из этого списка. Задача построения полной системы инвариантов в полном объеме остается пока открытой и является предметом дальнейших исследований.
Работа выполнена при поддержке гранта РФФИ № 07−03−390.
Список литературы
1. Girardet C., Toubin C. // Surface Science Reports. 2001. V. 44. P. 159−238.
2. Sennikov P.G., Ignatov S.K., Schrems O. // J. Phys. Chem. 2005. V. 6(3). P. 392−412.
3. Kuo J. -L., Coe J.V., Singer S.J., Band Y.B., Ojamae L. // J. Chem. Phys. 2001. V. 114(6). P. 25 272 540.
4. Bernal D., Fowler R.H. // J. Chem. Phys. 1933. V. 1(8). P. 515−548.
5. Pauling L. // J. Am. Chem. Soc. 1935. V. 57(12).
GRAPH INVARIANTS AND THEIR APPLICATION TO HYDROGEN-BONDED CLUSTERS (H2O)* A.G. Razuvaev, S.K. Ignatov, O.B. Gadzhiev, O.A. Usacheva
Based on the graph invariant theory, a new method for estimating the energy and thermodynamic parameters of hydrogen-bonded crystalline structures has been developed. The method serves to solve the problem of calculating the adsorption coverage and thermodynamic parameters of the molecules adsorbed on the surface of a solid capable of forming orientation isomers. The basic statements of the theory have been formulated in a more general form as compared to those published earlier, and they have been adapted to the enumeration problem of adsorption structures on the surface of hydrogen-bonded crystals. The new approach has been tested on water hexamer (H2O)6 of octahedral configuration used as a model system.
Р. 2680−2684.

ПоказатьСвернуть
Заполнить форму текущей работой