Классы эквивалентности вершин

Числовые индексы молекулярных графов, называются топологическими индексами [66]. Для использования топологических индексов в качестве кода структуры, а также для исследования корреляций структура—активность катализатора множество элементов молекулярного графа разбивается на классы эквивалентности. Разбиение структуры на классы эквивалентности позволяет оценивать меру ее структурного разнообразия, или структурную неоднородность. Для представления структуры в виде топологических индексов рассмотрим некоторые определения [66]. Маршрутом длины /с в графе С от вершины и до вершины называется последовательность вершин их, М2,. . ., для которой ребро щ, щ+х) и (С) при г = 1, 2,, . /с маршрут замкнут, если Пх = ил+1 в противном случае маршрут открыт. Цепь — это открытый маршрут, в котором все вершины различны. [c.99]

Отношение эквивалентности определяется на множестве вершин молекулярного графа таким образом, что две вершины принадлежат данному классу эквивалентности, если они имеют такую же кратность ребер и одно и то же число соседей требуемого порядка г. одинаковыми степенями. Пусть к — любое неотрицательное число (О < /с р), где р — радиус графа G. Две вершины графа Ид и Уд будут называться эквивалентными относительно окрестности к-то порядка, тогда и только тогда, когда [c.100]

Здесь эквивалентные вершины Si, S , S , S — один класс — второй класс REg, RE- — третий класс тогда [c.101]

Сопоставим теперь каждому дереву клона все различные упорядоченные корневые деревья (см. рис. 1.8), переставляя разными способами его вершины. Упорядоченные деревья, отличающиеся только порядком расположения вершин, будем по определению считать равновероятными, их суммарная вероятность совпадает с вероятностью корневого дерева, из которого они получены. Таким образом, вероятность каждого из /)р(1, д) упорядоченных деревьев с корнем из класса эквивалентности равна [c.201]

В наших ранних исследованиях формализм теории информации применялся к молекулярному графу в целом для расчета некоторых индексов симметрии молекулярной структуры. Согласно соотношению эквивалентности, определенному на множестве вершин У(С) химического графа С, две вершины принадлежат одному и тому же классу эквивалентности, если они имеют одинаковую кратность ребер и одно и то же число соседей первого порядка с одинаковыми степенями. Установлено, что индексы структурной симметрии полезны при рассмотрении связи химической структуры с физическими и биологическими свойствами однотипных соединений [21—27]. Естественным расширением этого подхода явился учет при определении соотношения эквивалентности соседей вершин следующего порядка (т. е. соседей ближайших соседей). Такой метод был разработан, и вычисленные индексы называются индексами симметрии окрестностей [28]. [c.209]

Гетероатомы (атомы элементов, отличных от элемента, атомы которого преобладают) также могут быть включены в нашу схему с помощью формулы Шеннона. Разметка молекулярного графа таким образом, чтобы ранее эквивалентные вершины становились неэквивалентными, увеличивает величину (rj), так как прежде эквивалентные связки по необходимости становятся неэквивалентными. С другой стороны, величина С(т ) не изменяется, когда метка не влияет на классы эквивалентности связок. Тем не менее, будучи помеченной, молекула становится более сложной, и эта сложность может быть рассчитана по уравнению (3) добавив эту величину к уравнению (4), можно получить величину полной сложности j [19]. Предостережением против одновременного суммирования числа сложностей или числа индексов является тот факт, что если это осуществить, то отдельные величины исчезают из виду в этой сумме, и на основании полученного таким образом числа нельзя сказать, присутствуют гетероатомы или же нет. [c.244]

Это объясняет неудачу Шелли и Манка при попытке разбиения атомов на классы эквивалентности в двух из 50 рассмотренных ими химических графов. В следующем разделе будет показано, что этот недостаток алгоритма дополненной расширенной связности в действительности не препятствует получению однозначного обозначения для графа с такими вершинами. [c.270]

Вершины регулярных графов имеют одинаковые связности и, очевидно, не могут быть разбиты на различные классы эквивалентности при использовании любого из двух алгоритмов расширенной связности, обсужденных ранее. Многие графы этого типа встречаются в химической литературе [8, 10, 11, 13, 14], некоторые фигурируют при обсуждении [13, 14] эффективности алгоритмов распознавания молекулярной симметрии. Один такой граф представлен на схеме 13, где он изображен таким образом, чтобы показать симметрию гипотетического насыщенного углеводорода С,дН,д, который имел бы такой химический граф. [c.273]

В регулярном графе при отсутствии очевидной симметрии все вершины должны быть проверены тем же способом. Затем для каждого преобразованного графа получают линейное обозначение для матрицы смежности. Если вершины в исходном графе 13 связаны симметрией, то они будут давать идентичные линейные обозначения для преобразованных графов, приводя к трем различным классам эквивалентности. После нумерации графа линейное обозначение получают в соответствии с правилами 1—3. [c.274]

Определим два механизма как эквивалентные, если они содержат одни и те же стадии и если каждая стадия имеет один и тот же знак в выражениях для обоих механизмов. Это — соотношение эквивалентности, которое разбивает многогранник (6), представляющий все механизмы, не содержащие циклы, на 48 классов эквивалентности последние являются внутренностями следующих видов множеств (10 вершин, 20 ребер, 14 граней и 4 тела), изображенных [c.475]

В общем случае при фиксированном значении а существуют три простых механизма, представленные верщинами на диаграмме (17), и два класса эквивалентности механизмов без циклов (но не простых), представленных сегментами вертикальных линий между вершинами. В двух отдельных случаях (а - - 1/3 и а = 1/3) имеются два простых механизма и один класс эквивалентности механизмов без циклов (но не простых). Эти результаты суммированы в таблице (18), где фиф — любые положительные действительные числа, такие, что ф + ф = 1. [c.480]

При данном числе мономерных звеньев / молекулы могут различаться их пространственной конфигурацией, а соответствующие им молекулярные графы будут иметь различную топологическую структуру. Пронумеруем все изомеры с I звеньями индексом ] и обозначим Wij число способов, которыми можно образовать каждый (/ )-изомер из I различных мономерных звеньев. Тогда величина Wi из формулы (2.32) равна сумме Wц по всем значениям /. Для определения с помощью теории графов необходимо ввести некоторый параметр, характеризующий топологическую структуру соответствующего молекулярного графа. Такой величиной для каждого (/ )-изомера будет число его изоморфов G,y. Два графа называются изоморфными, если существует взаимнооднозначное отображение одного на другой, при котором сохраняется смежность и раскраска вершин. Другими словами, при таком отображении каждая вершина одного графа переходит в одну из вершин того же цвета другого графа, причем, две смежные вершины вместе с соединяющим их ребром переходят в пару смежных вершин тех же цветов и ребро между ними. Например, при изоморфном отображении любой узел (мономерное звено) вместе с висячими вершинами (функциональными группами) переходят в такое же образование. На рис. 2.2 изображены все изоморфы молекулярного графа с тремя трехфункциональными узлами. При этом все узлы и висячие вершины пронумерованы, так что каждому изоморфу соответствует определенный выбор нумерации. Следует подчеркнуть, что изоморфы являются пронумерованными графами. Из рис. 2.2 видно, что каждая вершина при изоморфном отображении может меняться местами лишь с некоторыми из остальных вершин, например вершина 1 — со 2, 3 и 4-й, а И1 — ни с одной. В соответствии с этим, все вершины графа можно разбить на группы, называемые его классами эквивалентности. Граф, изображенный на рис. 2.2, имеет 4 таких класса (1, 2, 3, 4), (5), (I, II), (III). [c.53]

Число всех изоморфов графа есть число всех возможных способов нумерации вершин, производимых независимо для вершин из каждого класса эквивалентности. Заметим, что из любой вершины, принадлежаш ей некоторому классу эквивалентности, выходит одно и то же число ребер. [c.54]

Для класса симметрии тетраэдра существуют два эквивалентных способа описания 3/2-ш или же 3/5. Наклонная линия, связывающая две оси, показывает, что они не ортогональны. Символ 3/2 т обозначает две не ортогональные поворотные оси 3 и 2, а также включающую их плоскость симметрии. Эти три элемента симметрии показаны на рис. 2-74. Класс симметрии 3/2 т эквивалентен паре осей третьего порядка и четверной зеркально-поворотной оси. В обоих случаях тройные оси проходят через вершину тетраэдра и центр его противоположной грани. Четверные зеркально-поворотные оси совпадают с осями второго порядка. Наличие четверной зеркально-поворотной оси хорошо видно, если тетраэдр повернуть на 90° относительно оси второго порядка, а затем отразить в плоскости, перпендикулярной этой оси. Таким образом, операции симметрии, выбранные в качестве основных, порождают остальные элементы симметрии. Это доказывает эквивалентность обоих описаний. [c.86]

Граф, показанный на схеме 10, имеет только 5 классов эквивалентности вершин в соответствии с алгоритмом упорядочивания, представленным на схеме 8, тогда как очевидная симметрия этого графа позволяет предположить наличие 6 независимых классов вершин. Выбор номера 2 для вершины с левой стороны, принадлежащей классу 2, вьшуждает левосторонней вершине класса 3 присвоить номер 4. Тогда верхнюю вершину класса 4 необходимо обозначить как вершину 6 согласно правилу 3. Противоположный выбор нумерации для вершин класса 2 приводит к точно такому же линейному обозначению, показывая тем самым, что вершины 2 и 3 соответственно связаны симметрией. [c.272]

Отношение изоморфизма является отношением эквивалентности, разбивающим множество всех му.тьтиграфов на классы эквивалентности, которые можно рассматривать как абстрактные мультиграфы. Изоморфные мультиграфы представляют собой один и тот же абстрактный мультиграф. В настоящее время в связи с отсутствием стандарта на машинное представление [84] существует многс способов ввода в ЭВМ структурных формул и их топологическиг графов. К наиболее перспективным способам ввода относятся а) ввод структурных формул с помощью оптических считывающие устройств в) ввод с помощью стандартных дисплеев в) ввод с по мощью специализированных устройств типа граф [85]. Струк турную, формулу при этом рассматривают в виде взвешенного гра фа, т. е. как функцию, заданную на вершинах и ребрах графе Весом вершины при этом служит символ химического элемент или радикала, а весом ребра — кратность химической связи. [c.96]

Из рассмотренного выше очевидно, что мера сложности структуры зависит как от способа, согласно которому множество А было получено из структуры, так и от используемого для разбиения соотношения эквивалентности. Для данной химической структуры классы эквивалентности, полученные при разбиении множества вершин графов со стертыми атомами водорода, будут отличаться от непересекающихся подмножеств, полученных из множества вершин целого (без удаления атомов водорода) молекулярного графа. Ра-шевский [29], Трукко [30] и Мовшович [31] рассчитали информационное содержание графов со стертыми атомами водорода, в которых топологически эквивалентные вершины (т. е. вершины, составляющие орбиты группы автоморфизмов) размещались в одном и том же подмножестве. Кайер [32] рассчитал информационное содержание целого молекулярного графа, в котором множество его вершин было разбито на классы эквивалентности на основе операций симметрии и экспериментальных данных спектроскопии ЯМР. Эквивалентность вершин на основании геометрической группы симметрии, порядок расстояний в матрице расстояний и распределение связок ( onne tions), определенных как число пар смежных ребер, также использовались авторами в качестве критериев для определения соотношения эквивалентности на множестве вершин [3, 33, 34]. [c.211]

Согласно формализму, разработанному Саркаром и сотр. [35], Бейсаком и сотр. [21] и Раухаудхури [36], для определения разнообразных теоретико-информационных инвариантов графа использовался целый молекулярный граф, и этот метод является достаточно общим для того, чтобы включать линейные графы, так же как и мультиграфы. Соотнощение эквивалентности определялось на множестве вершин F(G) таким образом, что две вершины принадлежат данному классу эквивалентности, если они имеют такую же кратность ребер и одно и то Же число соседей первого порядка с одинаковыми степенями. Ни химическая идентичность вершин, ни тип связывания соседей более высокого порядка (элементы, расположенные на расстоянии 2, 3.....р от выделенной вершины) не [c.212]

Граф 11 является примером химического графа, в котором можно заметить симметрию, но алгоритм упорядочивания далеко не достаточен для отнесения к классам эквивалентности [14]. Имеются четыре неэквивалентных класса групп СН2 и три неэквивалентных класса групп СН. Однако, как показано, правило 3 допускает однозначную нумерацию для графа только в результате трех попыток установить такую нумерацию. Даже в тех случаях, когда все вершины в графе фактически эквивалентны, можно быстро получить однозначное линейное обозначение для графа. Например, однозначное обозначение для графа кубана приводится на схеме 12. [c.272]

В некоторых случаях визуальное определение симметрии может приводить к ошибочному разбиению вершин графа на классы эквивалентности. Граф 15 взят из работы Рандича [25] по случайным блужданиям в графах и иллюстрирует то обстоятельство, что сим- [c.274]

Теорема об узлах деревьев. Для обратимой сети, у которой удалены ее реакции входа и выхода , строится граф. Вершины графа соответствуют классам эквивалентности соединений, причем классы эквивалентности определяются при утверждении, что все вешества в комплексе эквивалентны. Ребра графа — реакции, и они связывают классы эквивалентности реагентов и продуктов. Если граф является деревом, то в таком случае стационарные состояния оказываются локально асимптотически устойчивыми. Эта теорема частично распространена на необратимые сети при наличии подхо-дяшей модели необратимых реакций (см.-[2, 7, 8]). [c.380]

Предложен систематический метод определения всех химических механизмов, возможных с точки зрения комбинаторики, в предположении о том, что возможны суммарные реакции и определенные элементарные процессы столкновения. Все такие механизмы сводятся к конечному числу классов эквивалентности. Класс эквивалентности отдельного механизма т представляется внутренней областью выпуклого многогранника в конечномерном пространстве. Граням многогранника, имеющим более низкую размерность, соответствуют подмеханизмы /я, а не допускающие дальнейшее упрощение механизмы, т. е. простые механизмы отвечают вершинам многогранника. Таким образом, показано, что каждый механизм может быть описан с помощью простых механизмов, точно так же как выпуклый многогранник описывается своими вершинами. [c.472]

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

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