Нумерация каноническая

КАНОНИЧЕСКАЯ НУМЕРАЦИЯ И СИСТЕМА ЛИНЕЙНЫХ ОБОЗНАЧЕНИЙ ХИМИЧЕСКИХ ГРАФОВ [c.266]

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

КАНОНИЧЕСКАЯ НУМЕРАЦИЯ РЕГУЛЯРНЫХ ГРАФОВ [c.273]

Из сравнения этих чисел следует, что А> Б. Нет необходимости читать всю цепочку цифр, чтобы сделать выбор между формулами А к Б, так как ясно, что максимальное значение имеет то число, в котором единица противостоит нулю второго числа в наибольшем разряде (отмечен стрелкой). Таким образом, суть метода, предложенного автором, состоит в том, что в качестве стартового (№ 1) атома выбирается атом с наибольшей связностью или валентностью, а дальнейшая нумерация атомов осуществляется таким образом, чтобы записанная в строку матрица смежности данного соединения получила максимальное значение. При этом способе приведения к каноническому виду функциональность оказывается фактором второстепенным, определяющим ранг атома только тогда, когда соображений связности оказывается недостаточно. В одной из своих последних работ автор [127] отмечает, что для графов ациклических соединений полная связность однозначно представляется Г-списком в максимальной матрице смежности, что требует лишь 2п бит (при п атомах углерода в молекуле). Если к этому добавить специальный список для полициклических структур [127], такой способ оказывается конкурентоспособным с системой ЛФВ для быстрого поиска структур с помощью вычислительной техники. [c.30]

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

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

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

Существует большое число методов для упорядочивания и распознавания структурно родственных атомов или групп, которые могут быть использованы в системе канонической нумерации [8—18]. Одним из наиболее удобных методов является итерационная процедура [уравнение (1)], описание которой может быть найдено, например, в обычном справочнике Маргенау и Мэрфи [20] [c.268]

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

Автоматическая нумерация некоторых структур по правилам иерархии Моргана сталкивается с затруднениями. Недавно Моро предложил некоторые усовершенствования программы, которые разрешают эти проблемы [295]. Можно предложить другие правила старшинства и получить при этом другой вид молекулы для некоторых структур это полезно. В самом деле, в рамках принятой теории некоторые объекты требуют нескольких упрощенных представлений, в то время как для других объектов в этом нет необходимости [296]. Возможность использования нескольких канонических нумераций внутри одной программы является, однако, очень невыгодной с точки зрения расхода машинного времени Берзон [135] сообщает, что в некоторых случаях на приведение молекулярных структур к каноническому виду уходит до 40 % необходимого для выполнения программы машинного времени. Этот же недостаток сохраняется даже после некоторого совершенствования программы [137]. [c.26]

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

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

Если имеется в виду обширный расчет по методу валентных связей, необходимо иметь определенный систематический и обоснованный метод составления набора канонических структур. Одна из возможностей — написать все те структуры, которые представлены максимальным числом связей, включая и длинные (дьюаровы) связи. В таком случае мы вынуждены задать вопрос, является ли такой набор полным или может быть он даже излишне полон. Румер (1932), показал, что в действительности набор, построенный таким образом, содержит много лишних структур. Румер предложил метод построения необходимого полного набора. Атомы, образующие молекулу, располагаются по кругу. Для нафталина такое расположение показано на рис. 23. Порядок нумерации атомов не существен для метода. [c.86]

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

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