Матрицы расстояний

ВЗАИМОСВЯЗЬ МЕЖДУ МАТРИЦЕЙ СМЕЖНОСТИ И МАТРИЦЕЙ РАССТОЯНИЙ [c.260]

То есть индекс Винера определяется как полусумма всех элементов матрицы расстояний в молекулярном графе. — Прим. перев. [c.188]

Источником топологических индексов является МГ. Наиболее распространены два способа построения топологических индексов. Один из них основан непосредственно на матрице смежности, а другой — на матрице расстО Яний на графе. В матрице расстояний [c.39]

Индекс Винера. = ( 1 ) — квадратная матрица расстояний графа Э. Порядок ее равен числу вершин, а элемент йу совпадает с расстоянием между вершинами Vi и Так как с1ц = йц, то матрица симметрична. Обозначим через сумму всех элементов матрицы расположенных выше главной диагонали. Тогда [c.40]

ИНДЕКСЫ МАТРИЦЫ РАССТОЯНИЙ [c.187]

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

РИС, 3. Матрица расстояний и матрица смежности для молекулы н-бутана. [c.187]

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

Приведенные выражения могут не соответствовать строгой стехиометрии МСС, так как их состав сильно зависит от внешней среды и дефектов структуры углеродной матрицы. Расстояние между внедренными слоями обозначается а между углеродными слоями — < 0. Для графита о равно примерно 0,335 нм. [c.255]

МАТРИЦА РАССТОЯНИЙ ДЛЯ МОЛЕКУЛ, СОДЕРЖАЩИХ ГЕТЕРОАТОМЫ [c.259]

Общеизвестно, что молекулярные графы (молекулы) можно удобно представить с помощью топологических матриц [2, 21, 24]. В связи с этим особенно важны две матрицы [2, 24] матрица смежности А = /1(С) графа С и матрица расстояний О = О (С ) графа С. [c.260]

В этой работе мы предлагаем следующий метод. Мы определяем диагональные элементы матрицы расстояний для вершинно- и реберно-взвешенных (мульти)графов следующим образом [c.262]

Матрица расстояний для гетероатомных молекул 261 [c.261]

Матрица смежности — наиболее широко используемая матрица для характеристики графа [2, 21, 22, 24—26]. Ее элементы (А)-- = О и (А ) J = А )J = 1. Единица появляется всегда, если вершины / и ] связаны между собой. Матрица расстояний также является симметричней матрицей с элементами = О и D) J = = d J, где ё- — число ребер (связей) в наикратчайшей цепи между вершинами (атомами) I и у. [c.261]

МАТРИЦА РАССТОЯНИЙ ДЛЯ ГЕТЕРОСИСТЕМ [c.261]

Наличие в весовых коэффициентов влияет на элементы соответствующей матрицы расстояний. Так, например, диагональные элементы соответствующие вершинам с петлей, больше [c.262]

Недиагональные элементы матрицы расстояний для вершинно-и реберно-взвешенных (мульти)графов определяются как [c.262]

Обычно исходными данными в задачах кластерного анализа бывают меры близости между всеми объектами, которые образуют симметричную матрицу расстояний (или близостей). Часто процедуры кластерного анализа используют функции критериев (например, сумма квадратов расстояний от центров кластеров) и ищут группировку, которая придает функции критерия экстремальные значения. Теоретически задача группировки всегда может быть решена трудоемким перебором. Однако на практике такой подход годится лишь для самых простых задач. Наиболее часто используемым подходом для поиска оптимального разделения является итеративная оптимизация. Основная идея ее заключается в нахождении некоторого разумного начального разделения и в передвижении объектов из одной группы в другую, если это передвижение улучшает функцию критерия. Несмотря на некоторые ограничения, вы- [c.116]

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

Используя построенную таким образом матрицу расстояний, можно непосредственно рассчитать число Винера для гетероатом-ного графа [c.263]

Получим сокращенную матрицу расстояний [c.532]

Для расчета исполнительных размеров рычагов необходимо задаться раскрытием В формы, высотой Ь полу-матрицы, расстоянием Ь[ от плоскости разъема до оси крепления рычага, ходом 5 выталкивания и углом а (оптимальное значение а = 10. 15 ) [c.185]

Рассмотрим схему последовательной кластеризации. Пусть на п-и шаге мы получили К кластеров. Если выбрана мера сходства (функция 2), то можно построить матрицу расстояний между кластерами, в которой элемент определяет расстояние между i -ы и /нм кластерами. [c.26]

В этом и последуюищх трех разделах мы перечислим все существенные топологические индексы, предложенные до настоящего времени. Поскольку мы можем дать здесь не более чем краткое (в общих чертах) описание этих индексов, для заинтересованного читателя с целью более детального ознакомления приводятся ссылки на два последних обзора Балабана и сотр. [18, 19]. Мы начнем этот раздел с обсуждения индексов, основанных на матрице расстояний 0(0). [c.187]

Определение Балабаном матрицы расстояний не является достаточно общим, поскольку не включает молекул с гетероатомами. Ввиду этого в настоящей работе мы предлагаем довольно общее определение для элементов матрицы расстояний, которое охватывает вершинно- и реберно-вэвешенные мультиграфы т.е. молекулы с кратными связями и гетероатомами. [c.262]

После нормирования переменных получили матрицу расстояний и на основе ее построили дендрит, в котором смвЕНне элементы имели наименьшие значения признаков. [c.145]

В последние годы было также предложено несколько других топологических индексов, основанных на молекулярной матрице расстояний [2, 6, 11] . Вероятно, среди индексов, применяемых при ККСС- и ККСА-исследованиях [2, 6, 11, 13—18], наиболее широко используется число Винера (число цепей) [12]. Однако всякое применение индекса Винера к гетеросистемам оказьшается затруднительным [18]. Это побудило нас сообщить о построении матрицы расстояний для графов, представляющих любую молекулярную систему, с целью сделать возможным применение индекса Балабана, числа Винера или любого другого индекса, основанного на топологических расстояниях, подобно информационному содержанию числа Винера [13] или информационному содержанию расстояний [13], непосредственно к любому ряду молекул, представляющих интерес для потенциальных пользователей этих индексов. [c.260]

Этот метод предложен для применения при расчете молекулярной матрицы расстояний, важной для соответствия на субструктурном уровне обычных планов синтеза, основанных первоначально на экспериментальных данных. [c.106]

Большинство современных индексов основаны на двух специальных матрицах матрице расстояний и матрице смежности. Каждый элемент в матрице pa toяний 0(0) представляет собой число ребер, срединяюших вершину / с вершиной у наикратчайшим путем, и обозначается как d J, Элементы матрицы смежности А (С), обозначаемые как а--, равны либо единице, либо нулю в зависимости от того, связана ли ребром вершина / графа С с вершиной у или же нет. Соответствуюшие матрицы для молекулы н-бутана приведены на рис. 3. Две матрицы связаны друг с другом общим уравнением [c.187]

Обе матрицы — матрица расстояний и матрица смежности — в их обычных формулировках [2, 21, 24] ограничены в том смысле, что не могут быть использованы для молекул с кратными связями и/или гетероатомами. Однако определение матрицы смежности может быть расширено [2, 23, 27—32] для того, чтобы охватить все возможные (химические) структуры. Попытки осуществить это для матрицы расстояний до сих пор были довольно редкими [18, 33]. Важный шаг в зтом направлении был предпринят Балабаном [1] для мультиграфов. Он предложил ввести в матрицу расстояний дробное число а/Ь для связи /—] с порядком связи Ь. Поскольку Балабан рассматривал только ненасыщенные и ароматические углеводороды, для первых из них константа а имела значение 1, а для последних — соответственно 2. Таким образом, величина а/Ь принимает значения 1/2 для атомов углерода, соединенных двойной связью, 1/3 для атомов углерода, соединенных тройной связью, и 2/3 для ароматических связей. [c.261]

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

Мы признательны проф. Р. Сейболду (Дейтон, шт. Огайо) за многочисленные полезные обсуждения и переписку, посвященные индексу 5, и за предоставление нам препринтов его статей о применениях этого индекса при исследованиях химической канцерогенности замещенных ароматических углеводородов. Мы благодарны проф. А. Балабану (Бухарест) за обсуждение его индекса в ходе переписки. Н. Тринайстич хотел бы поблагодарить проф. Б. Джимарка (шт. Колумбия) за возможность пребывания и радушный прием в Университете шт. Южная Каролина и за многочисленные плодотворные обсуждения свойств молекулярной матрицы расстояний. [c.264]

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

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

В методе КБС образ классифицируется согласно правилу большинства голосов по К ближайшим соседям в л-мерном пространстве. Если классифицируемый образ неизвестен, в качестве ближайших соседей берут только объекты о5учаюш ей выборки. Расчеты сводятся к вычислению и просмотру матрицы расстояний. В качестве расстояния можно взять расстояние в л-мерном евклидовом пространстве между -й и /-й точками [c.102]

Важное значение и практическое применение получают также статистические методы решения дискретных и смешанных задач, представляемых в виде эквивалентных перечислительных задач на графах [156—161]. В [156] предлагается рассматривать задачу коммивояжера иа полном графе, в которой элементы (пХп) матрицы расстояний суть независимые равномерно распределенные случайные величины на (О, 1). Предлагаемый алгоритм состоит в решении задачи о назначениях с матрицей и последующем сшивании подциклов ее решения до получения замкнутого маршрута. Алгоритм [156], имея трудоемкость порядка п , дает маршрут, отношение длины которого к длине оптимального не превосходит (l-fe(n)), где е(м)->0 при п- оо. В [157] предлагается алгоритм )решения ТОЙ же задачи коммивояжера, основанный иа разбиении данных п городов на группы по t городов, нахождении оитималь-ного пути в каждой группе и последующем определении пути между группами. Этот алгоритм дает отклонение от оптимума [c.91]

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

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