Матрицы инцидентности

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

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

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

Отношение К приводит к направленному графу С следующим образом. Отождествим каждый комплекс с вершиной е С и введем ребро направленное из вершины V- к вершине если и только если имеется реакция С(/) — С(/). Чтобы кодировать выражение для скорости реакции в графе, припишем каждому ребру неотрицательный вес РДс), определяемый внутренней скоростью соответствующей реакции. Если РДс) = О для се/ / и некоторой величины /, то соответствующее ребро может быть исключено следовательно, мы предполагаем, что РДс) Ф 0. Топология графа С в свою очередь кодируется в его матрице инцидентности вершин и ребер которая определяется так [c.326]

Ур — множество вершин графа С мЕ = [Е ,. .., Е — множество ребер графа С обозначим через Со(С,) множество всех функций, принимающих действительные значения, на У(Е). Функции в Со называются 0-цепями, а функции в С, — 1-цепями, хотя обычно скаляры берутся из абелевой группы, а не из поля в таком случае Сц и С, называются группами цепей [4] . В рамках этой схемы матрица инцидентности является представлением, связанным с каноническими базами граничного оператора с . Су С . Если граф С имеет р вершин и д компонент, легко показать, что р(< = = р - д 2] . [c.329]

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

Матрица инцидентности М1(С) графа С. Матрица М1(< ) — это матрица, строки которой соответствуют вершинам, а столбцы — ребрам и элементами которой являются числа 1, —1 или О в зависимости от того, является ли вершина для данного ребра соответственно начальной, конечной или она не инцидентна [c.101]

В случае двудольных графов в работе [100] для оценки была использована формула = 8р((В В) В В), в которой матрица В описывает отношение инцидентности для вершин подмножеств V и Уг. Матрица раскладывалась в степенной ряд по сте- [c.55]

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

В первую строку массива МРВ записывается общее число потоков, инцидентных каждому из блоков, во вторую — число различных компонентов, находящихся в потоках каждого из блоков. При формировании МРВ используются массивы МР и М8Р. В массиве приводится перечень номеров потоков, инцидентных каждому из блоков, а в массиве МКВ—перечень кодов компонентов каждого из блоков. Для улучшения процедуры поиска адресов переменных при формировании уплотненной матрицы смежности 81] в первой строке массива WA записываются начальные адреса параметров -го потока в об щем векторе переменных, во второй строке — начальный адрес перечня кодов компонентов в массиве компонентного состава М8Р. [c.11]

Общее число уравнений балансов для потоков Общее число уравнений балансов для блоков Общее число уравнений балансов в ХТС Число потоков, инцидентных блоку Длина вектора типов переменных ХТС Размерность массива покомпонентного состава в уравнениях блоков Общее число нен левых элементов в матрице смежности 5 Размерность массива покомпонентного состава потоков [c.13]

Представление структур через матрицы совпадения. Из топологического учения о графах вытекает возможность четвертого представления структур — в виде так называемых матриц совпадения (инцидентности), в которых по строкам расположены 0-мерные элементы, а по столбцам 1-мерные элементы. Там, где 1-мерный элемент имеет оконечностью 0-мерный элемент, ставится 1, а где нет, то 0. Тогда (8.74) — (8.77) изобразятся как (8.82) [c.405]

Рис, 1.25. Варианты технологической структуры хнмико-технологнческой системы 11 соогнетствующие им матрицы инцидентности [c.64]

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

Для решения задач Г. т. и ее приложений графы представляют с помощью матриц (смежности, инцидентности, дву-строчиых и др.Х а также спец. числовых характеристик. Напр., в матрице смежности (рис. , в) строки и столбцы отвечают номерам вершин графа, а се элементы принимают значения О и 1 (соотв. отсутствие и наличие дуги между данной парой вершин) в матрице инцидентности (рис. 1,г) строки отвечают номерам вершин, столбцы-номерам дуг, а элементы принимают значения О, -ь 1 и - 1 (соотв. отсутствие, наличие дуги, входящей в вершину и выходящей из нее). Наиб, употребительные числовые характеристики число вершин (ш), число дуг или ребер (и), цикломатич, число, нли ранг графа (п — т + к, где к - число связных подграфов в несвязном графе иапр., для графа на рис. 1,6 ранг будет 10-6-1- 1 =5). [c.610]

Умножим любую строку 5 логически на строку х - Если результат логического умножения не равен нулю, на место строки s запишем результат логического сложения 5, и Хц а строку вычеркнем из матрицы. Это соответствует замене узлов 5,- и обобш енным узлом, имеющим все связи, инцидентные 5 и Если логическое произведение 5,- Л равно нулю, логического сложения строк х,- и и вычеркивания строки 51 не производим. [c.270]

Каждому графу для которого выполнены свойства 1—5, можно сопоставить периодическую матрицу смежности А1, которая может быть записана в блочном виде с элементами (А,)у, причем (А,) = А, (А,)(,,+1 = В, (А,) -1,,-= В , (А1) . = 0 при I/ —г >1. Здесь А — матрица смежности подграфа , В — матрица, описывающая отношение инцидентности для графов и 4.1, В — транспонированная матрица. А и В не зависят от номера I (г = О, 1, 2,. ..). Граф удовлетворяющий свойствам 1—5, назовем периодическим графом. Аналогичным образом может быть определен и полунериодический граф (в этом случае = 1, 2,. ..). В отличие от конечных графов, спектры которых состоят из конечного числа изолированных собственных значений конечной кратности, спектры периодического и полупериодического графов, вообще говоря, состоят 1ИЗ отрезков вещественной прямой. Спектр полупериодического графа может иметь, кроме того, и дискретную компоненту. [c.60]

Помимо графического изображения в виде точек (вершпн), соединенных линиями (ребрами), существуют также матричные представления графов. Это означает, что произвольному графу ставится в соответствие по определенному правилу некоторая матрица, по которой он может быть однозначно восстановлен. Существуют различные правила построения таких топологических матриц, два из которых наиболее известны. Согласно первому, нужно произвольным образом пронумеровать все п вершин графа различными числами от 1 до , а затем построить квадратную матрицу, у которой все диагональные элементы равны нулю. Остальными элементами ац этой матрицы смежности служат единицы или нули в зависимости от того, соединены или нет ребром -я и /-я вершины. Для орграфа учитывается иаправление дуг (ау = 1, только если дуга Vi,Vj) принадлежат графу), поэтому матрица смежности может быть несимметричной. Для мультиграфа значение элемента ац равно кратности соединяющего вершины v и v ребра, а для псевдографа диагональный элемент ац равен числу петель, инцидентных вершине [c.304]

Второе правило, позволяющее построить матрицу инциденций графа, предполагает, кроме нумерации п вершии, независимую нумерацию т его ребер. Тогда элементы Ъц этой матрицы, имеющей п строк и т столбцов, будут равны единице, если вершина У и ребро инцидентны и равны нулю в противном случае. Для орграфа 5,3 = 1, если дуга Xi выходит из вершины у,-, и Ьц = —, если она входит в Vi. [c.304]

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

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