Представление графов с помощью матриц

ПРЕДСТАВЛЕНИЕ ГРАФОВ С ПОМОЩЬЮ МАТРИЦ [c.122]

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

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

Доказательство. Без потери общности мы предполагаем, что <7=1, так как в противном случае мы применяем следующее доказательство для каждой компоненты в отдельности. Если граф С — сильно связный, то для каждого подпространства циклов группы цепей С, имеется базис, состоящий из представлений направленных циклов, и в этом случае выполняется (19). Если граф С не является сильно связным, то разбиваем его на сильно связные компоненты /3 = 1,, q . Без потери общности полагаем, что = 2 и что все ребра между компонентами О, и Сз направлены от С , к Если представление ориентированного, но не направленного цикла, появляющееся в матрице соответствует циклу, полностью лежащему внутри С, или С2, то этот цикл может быть представлен с помощью направленных циклов внутри относительно сильно связной компоненты. Следовательно, мы можем предположить, что матрица не содержит представления любого такого цикла. При этом остаются ориентированные циклы, проходящие как через С,, так и 02, и ясно, что они не являются направленными. Представление каждого цикла этого типа содержит - 1 по крайней мере в одном положении, для которого в представлении в матрице любого направленного цикла нет не обращающегося в нуль элемента. Кроме того, такие элементы не могут все аннулироваться другими ориентированными циклами, поскольку полный набор циклов, представляемый столбцами матрицы является независимым. [c.340]

В течение последующего столетия предпринимались попытки охарактеризовать соединение, в частности, с помощью алгебраических символов [6], математических матриц [7] и химических графов [8]. Хотя мы не можем обсуждать их здесь, развитие математизации структуры соединений позволяет получать достаточно наглядное представление о ранних эволюционных процессах химии. Эта область была частично рассмотрена в обзоре автора [9]. Один из существенных результатов видится в увеличивающемся повсеместном использовании химических графов [10] — тенденция, приобретающая в последние годы все возрастающее значение. [c.184]

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

С этой целью рассмотрим интенсивности 1 и u ) связей между вершинами графа и с учетом того, что объектом анализа является устойчивость агрегата и анализ носит качественный характер, примем следующие допущения процессы, распространяющиеся по графу, являются возмущениями, вносимыми в него через соответствующие вершины и влияющие на значения других вершин в зависимости от знаков соединяющих их дуг каждая вершина графа имеет лишь один ненулевой вход в момент времени I = 0 интенсивности всех связей являются единичными, т. е. процессы в агрегате оказывают друг на друга равнозначное влияние. Соответствующая этим допущениям ситуация на графе будет называться простым процессом распространения возмущения. Критерий устойчивости зададим исходя из условия возможности с его помощью количественно оценить способности контуров графа поддерживать или, наоборот, препятствовать распространению возмущений, усиливая или ослабляя тем самым тенденцию к отклонению от состояний равновесия в его вершинах. Тогда в основу критерия положим представление о характеристических значениях графа, вычисляемых по матрице взаимосвязи А между его вершинами. Элементы этой матрицы могут быть заданы как [1] [c.41]

Наиболее удобный и перспективный метод представления технологической и информационной топологии ХТС состоит в применении информационно-потоковых мультиграфов. Информацию о топологических характеристиках параметрического потокового графа или информационно-потокового мультиграфа представляют с помощью матрицы ветвей графа [Ь]. [c.326]

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

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

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