Инварианты графа

Для описания пространственных структур достаточно двух топологических инвариантов N — числа несвязанных частей и G — рода поверхности раздела фаз. Величина G характеризует связность пространства фазы (безразлично какой), она определяется числом сквозных сечений участков многосвязной области, для которого число несвязанных частей фазы сохраняется неизменным, Любое преобразование многосвязной области, происходящее в результате ее деформации без разрывов и склеек, т. е. без изменений ее связности, называется гомеоморфным. Таким образом, все геометрические объекты, характеризуемые одним числом связности G, гомеоморфны (топологически эквивалентны). Топологическая эквивалентность тел класса G сохраняется также и при изменении размерности тела — при преобразовании точки в объем, при преобразовании участков контакта объемов или поверхностей в отрезки и наоборот. Это справедливо только для гомеоморфных преобразований. Характеристика тела G совпадает с характеристикой связности топологически эквивалентного ему графа — первой группы Бетти, В . Очевидно также равенство числа отдельных частей N тела G = и числа несвязанных частей эквивалентного ему графа N = В . Считая каждую из фаз -фазной. системы телом, ограниченным поверхностью класса G , для эквивалентного ему графа (или сети) может быть записано следующее уравнение Вц = С — -f B i, где B i — нулевая группа гомологий (или нулевая группа Бетти) — число разобщенных частей графа Вц — первая группа гомологий (первая группа Бетти) — число замкнутых одномерных циклов графа Pi — число узлов i — число связей между ними. [c.134]

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

Различные инварианты графа представляют собой важные характеристики графа. Инвариант графа — это теоретико-графовое свойство, сохраняющееся при изоморфизме [12]. Характеристический полином матрицы смежности является инвариантом графа, хотя матрица смежности изменяется в зависимости от нумерации вершин. Инвариантом графа могут быть полином, последовательность чисел или числовой индекс. Числовые индексы, полученные из топологических характеристик соответствующих химических графов, называются топологическими индексами. Очевидно, что совпадение всех инвариантов графов G и 02 является необходимым предварительным условием изоморфизма графов О и С . Но это не достаточное условие для изоморфизма. На сегодняшний день невозможно обнаружить общий набор инвариантов, которые были бы способны дать однозначную характеристику графа и тем самым решить проблему изоморфизма [12]. Тем не менее были предложены практические схемы для различения изомеров, в которых одновременно используется целый ряд различных топологических параметров [12]. Недостатком представления молекул с помощью графов является то, что при этом теряются все стереохимические особенности молекулярной структуры. Однако графы все же описывают полную топологию молекулы известно, что многие важные характеристики молекул, такие, как энергия, порядок связи и плотность заряда, существенно зависят от топологии [18]. Поскольку топологические индексы являются численными выражениями определенных топологических свойств молекулярной структуры, не удивительно, что различные топологические индексы в значительной степени коррелируют с физико-химическими и биологическими свойствами разнообразных групп молекул [9, 10]. [c.208]

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

Прежде всего отметим общность метода. Сравнимость структур является математической частью анализа и зависит от 1) выбора инвариантов (структурных) графа для характеристики молекул [c.233]

Применение теории графов к этой проблеме преврашается в задачу нахождения инварианта (количественной величины, характеризующей граф она не будет изменяться при различных укладках графа), который увеличивается всякий раз, когда число топологических характеристик, перечисленных на рис. 1, возрастает. Это не так легко, как может показаться на первый взгляд. Как видно из обзора Балабана, предложено значительное число (примерно 20) топологических индексов и индексов разветвленности [18] . Большинству этих индексов присущи два основных недостатка, что препятствует использованию их для нашей цели. Многие из них не удовлетворяют минимальному набору критериев, перечисленных выше, т.е. они уменьшаются при увеличении одной или более топологических характеристик или же вообше не отражают такое увеличение. Другой недостаток многих индексов состоит в том, что они фактически являются суммами наборов чисел, которые обычно возрастают с увеличением размера молекулы. Использование таких индексов требует применения ЭВМ для всех молекул, за исключением самых небольших, и их физическая интерпретация часто не является простой. [c.239]

Как было показано в предыдущем разделе, то, что некоторые типы стационарных состояний не существуют, может являться следствием свойств графа и стехиометрии, но, когда нет положительных инвариантов, существование стационарных состояний не может быть установлено, не зная зависимости Р,(с) от с. В этом разделе мы приведем некоторые результаты для класса сетей, которые называются вершинно-управляемыми. В этих системах поток через г-е ребро зависит только от концентрации вещества в реакционном комплексе, соответствующем этому ребру. Так, например, если ребро (/р 2) помечено /, то дР /дс = О, при условии что у не является индексом вещества в СО,). Этот класс, конечно. [c.341]

В настоящее время одним из важных вопросов теории химических графов является разработка теоретико-информащтонных инвариантов графа [19]. Множество соответствующих элементов, полученных из молекулярного графа, разбивается на основе соотнощения эквивалентности на непересекающиеся подмножества, и для расчета информационного содержания структуры используется формула Шеннона [20] . Информационное содержание графа может рассматриваться как количественная мера его структурной неоднородности или же разнообразия. Например, из двух графов и [c.209]

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

МОЩЬЮ концепции линейной комбинации инвариантов графов (ЛКИГ) Гордон и сотр. [301, 302] дали корректное математическое обоснование различных аддитивных схем, использующихся для предсказаний стандартных термодинамических данных. Концепция ЛКИГ позволила объяснить оценки стандартных энтальпии и энтропии в алканах [301]. Было показано, что различия в энтропии отдельных изомерных структур можно интерпретировать с помощью так называемой комбинаторной энтропии [303] — абстрактного понятия в рамках теории графов. С помощью представления о комбинаторной энтропии была также проанализирована связь между третьим законом термодинамики и явлением изомерии [304]. [c.88]

Теоретико-информационные инварианты могут использоваться в качестве представления структуры в базах знаний каталитических систем искусственного интеллекта наряду с матрицами и их каноническими представлениями. Различные инварианты молекулярного графа представляют собой важные характеристики графа. РТнвариант графа — это теоретико-графовое свойство, сохраняющееся при изоморфизме [86]. Более точно [80] пусть Р — функция, относящая каждому графу С, некоторый элемент из множества М произвольной природы (элементы М чаще всего числа, векторы, матрицы, многочлены). Эту функцию будем называть инвариантом, если на изморфных графах ее значения совпадают, т. е. для любых [c.99]

Таким образом, применение характеристики Эйлера совместно с теорией графов позволяет выявить все многообразие топологических инвариантов расположения изокритериальных многообразий в концентрационном симплексе. [c.156]

Каждой органической молекуле можно сопоставить граф. Для каждого графа можно построить различные наборы инвариантов, т, е. совокунности чисел, которые не зависят от способа нумерации вершин графа. Такие инварианты называют в теоретической химии топологическими индексами. Тонологические индексы бывают локального и интегрального типов. В первом случае топологические индексы сопоставляются отдельным вершинам или ребрам графа. Примерами таких индексов являются элементы матрицы илотно-сги — заряды на атомах и порядки связей. Индексы интегрального типа относятся к МГ в целом. В качестве примеров таких индексов могут служить коэффициенты характеристического полинома матрицы смежности. Из отдельных индексов можно устраивать разные комбинации. В результате получают топологические мультииидексы. [c.38]

Теоретико-информационные инварианты могут быть использованы для количественного описания молекул при ККСА-исследованиях их физико-химических и биологических свойств. Описанные в этой статье индексы основаны на симметрии окрестностей вершин в химическом графе. Подход, используемый при получении этих топологических индексов, состоит в разбиении вершин полного молекулярного графа на непересекающиеся подмножества на основе соотношения эквивалентности, определенного относительно различных степеней симметрии окрестностей, построении вероятностной схемы и окончательном расчете количества информации по формуле Шеннона. Полезность таких индексов была показана на примере ККСА-исследований растворимости спиртов, ингибирования спиртами микросомального лара-гидроксилирования анилина цитохромом P4JQ и токсичности барбитуратов. Показано, что топологические индексы, основанные на симметрии окрестностей, оказываются предпочтительнее других индексов, таких, как индекс Винера, индекс молекулярной связности и log Р. [c.206]

Число кинематических инвариантов связано с остальными индексами системы следующим образом. Поскольку + +. = V-iXv) n i ( )]- , из этого следует, что d m v ) + dim. /(fi ) - dim [. (i ) П /( )] = = dim[./(i ) n и поэтому n - i + q- 2 = p-- dim [. V v) n Пусть 6 = dim [.yf v) П тогда 6 = = p - q - n - iy + /2)) = p - q - s = p r ) - p(v . Таким образом, 6 является разностью между максимальным числом независимых реакций, полученным на основе структуры графа, и действительным числом независимых реакций. Это число, которое, понятно, неотрицательно, названо Фейнбергом [3] дефицитом. Когда 6 = 0, — однозначное отображение из в и, следова- [c.334]

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

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