Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
непересекающихся подмножеств At мощности я( (7 = 1, 2, ... , h; ? nt = п)
с помощью соотношения эквивалентно-
I
сти, определенного на А. Тогда этому распределению может быть соотнесена
вероятностная схема
где pt - вероятность того, что выбранный случайным образом элемент
множества А будет находиться в /-м подмножестве. Энтропия (или сложность)
структуры, связанная с данным видом разбиения, рассчитывается затем по
формуле Шеннона [20]
Из рассмотренного выше очевидно, что мера сложности структуры зависит как
от способа, согласно которому множество А было получено из структуры, так
и от используемого для разбиения соотношения эквивалентности. Для данной
химической структуры классы эквивалентности, полученные при разбиении
множества вершин графов со "стертыми" атомами водорода, будут отличаться
от непересекающихся подмножеств, полученных из множества вершин целого
(без удаления атомов водорода) молекулярного графа. Ра-шевский [29],
Трукко [30] и Мовшович [31] рассчитали информационное содержание графов
со "стертыми" атомами водорода, в которых топологически эквивалентные
вершины (т. е. вершины, составляющие орбиты группы автоморфизмов)
размещались в одном и том же подмножестве. Кайер [32] рассчитал
информационное содержание целого молекулярного графа, в котором множество
его вершин было разбито на классы эквивалентности на основе операций
симметрии и экспериментальных данных спектроскопии ЯМР. Эквивалентность
вершин на основании геометрической группы симметрии, порядок расстояний в
матрице расстояний и распределение связок (connections), определенных как
число пар смежных ребер, также использовались авторами в качестве
критериев для определения соотношения эквивалентности на множестве вершин
[3, 33, 34].
? р, = 1; р, > 0 (/' = 1, 2, ... , /г);
Информационное содержание = -р{ log2 pt бит.
(1)
212
В Магнусон, Д. Харрис, С. Бейсак
Согласно формализму, разработанному Саркаром и сотр. [35], Бейсаком и
сотр. [21] и Раухаудхури [36], для определения разнообразных теоретико-
информационных инвариантов графа использовался целый молекулярный граф, и
этот метод является достаточно общим для того, чтобы включать линейные
графы, так же как и мультиграфы. Соотношение эквивалентности определялось
на множестве вершин V(G) таким образом, что две вершины принадлежат
данному классу эквивалентности, если они имеют такую же кратность ребер и
одно и то Же число соседей первого порядка с одинаковыми степенями. Ни
химическая идентичность вершин, ни тип связывания соседей более высокого
порядка (элементы, расположенные на расстоянии 2, 3, ... , р от
выделенной вершины) не рассматривались. Первым подходом, следующим этому
методу, явилась работа Рея и др. [37], в которой информационное
содержание связывания второго порядка (2В1С) определялось с целью
установления корреляции антиканцерогенной активности группы три-азенов.
Впоследствии Рой и др. [28, 38] развили далее схему, согласно которой
различные порядки теоретико-информационных инвариантов графа
рассчитывались из соответствующего соотношения эквивалентности,
определенного на V(G).
2.3. СООТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ
Пусть к - любое неотрицательное целое число, 0 < к < р, где р - радиус
графа G. Две вершины графа, и0 и и0, будут называться эквивалентными
относительно окрестности fc-ro порядка, если и только если:
1) deg и0 - deg v0, причем и0 и v0 - атомы одного и того же химического
элемента;
2) I/V'(m0)I = 1Лт'(д0)1 для / = 1, 2, ... , к, где IjV'(m0)I и I TV'
(f0) I представляют собой соответственно мощности TV' (uQ) и W'(t'o);
3) в соответствии с каждой цепью ри0 = м0, м,, м2 •••"/> ui 6 е для I
- 1,2, ... , к имеется цепь pv0 = v0, t>,, v2...vl, v, e
e rl(v0) для I - 1, 2, ... , к, такая, что: a) deg ut = deg vt, причем и,
и t>; являются атомами одного и того же элемента при i s= 1,2,..., ... ,
к; б) E(ut, m,_,) = E(vt, i = 1, 2, ... , к, гдеД^м,, - число ребер,
соединяющих и( и н(_,, тогда как E(vt, - число
ребер, соединяющих д( и vt_ {.
Приведенное выше соотношение является соотношением эквивалентности в силу
рефлективности, симметричности и транзитивности и применяется для
получения разбиений множества вершин V(G) относительно окрестностей
различных порядков.
Топологические индексы
213
Информационное содержание графа относительно окрестности к-то порядка
(1C*), представляющее собой информационное содержание в расчете на одну
вершину, рассчитывается при использовании уравнения (1). Полное
информационное содержание (TIC*), т. е. мера сложности в расчете на один
граф, и другие производные индексы, структурное информационное содержание
(SIC*), информационное содержание связывания (BIC*) и комплементарное
информационное содержание (CIC*) могут быть рассчитаны следующим образом:
где п - мощность множества V(G) и N - полное число ребер (ковалентных
связей) в молекулярном графе.
Мовшович [31] отметил, что информационное содержание графов можно
рассматривать как количественные меры их относительной сложности. Для
