Изоморфизм графов

Особый интерес для химиков представляют изоморфизм и кодирование графов [10]. Говорят, что два графа G и 02 изоморфны (зто записывается как С, = О2), если существует такое взаимно однозначное отображение вершин графа О на вершины графа О , при котором сохраняется смежность, т. е. две вершины являются смежными в графе О,, если и только если соответствующие вершины в графе О2 также являются смежными [12]. По сути, изоморфные графы — это идентичные графы, но изображенные по-разному. В случае небольших графов для определения изоморфных графов достаточным оказывается визуальное рассмотрение двумерных диаграмм этот метод непригоден для практического применения в случае графов с большим числом вершин. Альтернативно графы могут быть представлены матрицами, такими, как матрица смежности, матрица расстояний, матрица инцидентности и т. д. Но в этом случае возможно столько же матриц, сколько существует возможных способов нумерации вершин графа. Следовательно, для того чтобы установить, являются ли два графа О а С с п вер- шинами изоморфными или же нет, необходимо осуществить х я операций. Молекулярные структуры являются графами особого вида, и основная проблема химической документации состоит в присвоении каждой вершине кода, такого, что два графа О, и О2 имеют одинаковый код, если и только если О = О. . Очевидно, что элегантное решение проблемы кодирования явится в равной мере и хорошим решением проблемы изоморфизма. В настоящее время приемлемое решение неизвестно, хотя предложены различные системы номенклатуры химических соединений . Был проведен де- [c.207]

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

Граф содержит информацию о структуре системы и определяет связь между переменными (отклонениями параметров), т. е. дает основу для записи уравнений, отражающих структурные особенности системы. Однозначное соответствие графа и системы доказано и носит название изоморфизма графа и физической системы. [c.231]

Подробное изображение химических структур, участвующих в каталитическом процессе, их однозначное кодирование тесно связано с проблемой изоморфизма, с теоретико-графовыми и топологическими представлениями. К первичной кодировке химической структуры будем относить ее представление в виде графа. Граф G (X, U) состоит из конечного множества X, элементы которого являются вершинами, и множества U двухэлементных подмножеств X (элементы множества U называются ребрами). Множества вер-вершин и ребер обозначаются соответственно X (G) и U (G). Две вершины в графе — смежные, если они соединены ребром [78]. Более точно под графом общего вида понимается упорядоченная тройка [80] [c.94]

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

В качестве другого примера мы покажем, как таким путем получить реакционный граф Г (см. рис. 14). Используем в качестве а граф Е, показанный на рис. 1, и пусть G будет группой Sj, действующей на класс изоморфизма ii = П .. Тогда ii . содержит граф F (рис. 23), изоморфный Е при перестановке g = (12)(35) е Sj (среди других) или, что эквивалентно, при 1,2-сдвиге. При стабилизаторе точки G = aut Е четырехэлементная группа F отображается в графы, показанные на рис. 24. Таким образом, F лежит на G -орбите размерности 4, поэтому, если Г — соответствующий суборбитальный граф [с орбитой множества ребер Д группы S , содержащей Е, F)], Г имеет внешнюю валентность 4. Теперь перестановка [c.300]

В более общем случае мы можем принять G = S . Эта группа действует на класс изоморфизма данного графа Е с п вершинами. Выбирая перегруппированный граф F = Е, мы получаем суборбитальный граф Г (направленный или ненаправленный) с множеством вершин это реакционный граф, соответствующий преобразованию Е F, VI, согласно общим свойствам суборбитальных графов, описанных выше, aut Г содержит группу S , так что Г транзитивен по верщинам и ребрам. [c.301]

Изучение мол. структур типа неорг. кластеров нли лент Мёбиуса сводится к установлению изоморфизма соответствующих мол. графов путем их укладки (вложения) в сложные многогранники (напр., полиэдры в случае кластеров) нли спец. многомерные пов-сти (напр., римановые). Анализ мол. графов полимеров, вершины к-рых отвечают мономерным звеньям, а ребра-хнм. связям между ними, [c.611]

Наименьшая двоичная запись 8ВЫ, введенная Рандичем [34], является результатом преобразования матрицы А (С) в двоичную запись. Строки и столбцы А (С) переставляются до достижения наименьшего возможного двоичного числа, при котором строки читаются последовательно. Этот индекс был предложен с целью решения проблемы изоморфизма графов, но он слишком громоздок, чтобы использоваться на практике в качестве топологического индекса. [c.191]

Каноническая нумерация химического графа может быть осуществлена с помощью нескольких известных методов и обычно представляет собой первый шаг при разработке буквенно-цифровых обозначений или кодов для обработки или поиска информации о химических структурах. Желательно иметь однозначный код для любой данной структуры, и это требование связано с проблемами изоморфизма графа, для которых было предложено много реще-ний. Однозначная нумерация графа дает решение проблемы однозначного кодирования. Следуя работам некоторых предшествующих исследователей, нами недавно предложен метод однозначной нумерации полиядерных кластерных соединений. Метод берет начало с алгоритма канонической нумерации химического графа, и затем эта нумерация превращается в компактную линейную форму полностью помеченной матрицы смежности. Для нумерации графа алгоритм использует понятие расширенной связности и методы теориц возмущений. Явное упорядочивание окончательного кода полностью определяет структуру. Процедура легко осуществляется без использования вычислительных средств и устанавливает изоморфизм, если две структуры имеют идентичные нумерации. Процедура канонической нумерации распространена на некоторые графы, с трудом поддающиеся другим методам канонической нумерации. [c.266]

Вторым применением теории графов для описания химических графов является получение численных данных о химической структуре, которые могут быть использованы для корреляции с биологическими, физическими или химическими свойствами. В книге Кайера и Холла [26], в статьях Уилкинса и др. [27, 28] суммированы результаты ряда систематических исследований такого типа, которые можно с успехом применять для корреляции свойств. В некоторых недавних работах [29—33] было высказано предположение, что теоретико-графовые индексы могут также оказаться пригодными для решения проблем изоморфизма графов и различения изомеров. Тем не менее, даже когда десять индексов структуры графа комбинируются в один супериндекс для различения изомеров [27] f все же нельзя показать, что он достаточен для установления изоморфизма, и представляется, что процедура канонической нумерации является более полезным подходом к решению подобных проблем. [c.276]

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

Из приведенного примера видно, что вид матрицы зависит от порядка нумерации вершин и определяет граф G (если отвлечься от конкретной природы его элементов) с точностью до перестановок параллельных ребер между собой, т. е. гораздо жестче , чем с точностью до изоморфизма. Для установления изоморфизма двух графов Gil Н с iV-вершииами необходимо осуш,ествить у. Л" операций [66] G ъН изоморфны тогда и только тогда, когда их вершины можно занумеровать так, что соответствующие матрицы смежности будут равны. [c.98]

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

Канонический способ нумерации вершин используется во многих работах по перечислению МГ, так как устраняет необходи-дюсть решать сложную проблему проверки графов на изоморфизм. Можно показать, что двум различным каноническим топологическим матрицам соответствуют неизоморфные графы. Алгоритмы генерирования используемых в химических исследованиях графов, основанные на канонической нумерации, начали разрабатываться около 15 лет назад [31, 32]. Анализ некоторых из таких алгоритмов проведен в работе [29], в которой содержится также обширная библиография по методам генерирования графов на ЭВМ, полезным при автоматизации молекулярного спектрального анализа. Опубликован ряд работ, непосредственно относящихся к разработке конструктивных алгоритмов перечисления графов и анализу их свойств симметрии [33—36, 163]. Различные способы кодирования химических соединений обсуждаются также в [37, 168]. [c.23]

В этой статье предложена схема однозначногв обозначения для графов, которая, по-видимому, широко применима. Предполагается, что алгоритм нумерации будет применим ко всем химическим графам и трудности возникнут лишь для очень больших высокорегулярных графов, подобных предложенным Матоном [24]. Если получена однозначная нумерация графа, то решение проблемы однозначного кодирования или номенклатуры достигается использованием линейной компактной формы матрицы смежности для представления графа. Также показано, что метод однозначных обозначений позволяет решить многие проблемы распознавания симметрии графов и их изоморфизма, и в частности может быть использован для [c.275]

Теорема. Пусть А — связный граф по крайней мрре с тремя верщинами, тогда aut L A) = aut А, если только граф А не является одним из графов, показанных на рис. 6 (где = означает изоморфизм). [c.290]

S , если и только если некоторая перестановка g множества вершин N переводит множество ребер Е з множество ребер Е такие перестановки g являются как раз изоморфизмами Е F, поэтому орбита flf, содержащая является классом изоморфизма , состоящим из всех графов F = Е. (Другими словами, F = Е, если FuE становятся идечтичнь[ми, когда метки вершин не учитываются.) Приняв F = Е, видим, что стабилизатор Е в является как раз группой автоморфизмов aut Е, состоящей из всех изоморфизмов Е с самим собой. Применяя теорему об орбитальном стабилизаторе, мы в таком случае получаем, что 1/1 aut fl = /laut fl. [c.299]

В стереохимии орг. в-в иаиб. часто используют мол. деревья-остовные деревья мол. графов, к-рьге содержат только все вершины, соответствующие атомам С (рис. 2, а и б). Составление наборов мол. деревьев и установление их изоморфизма позволяют определять мол. структуры и находить полное число изомеров алкаиов, алкенов и алкинов (рис. 2, в). [c.611]

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

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