Направленный цикл

Cтраница 1

Направленные циклы в примере Мильнера могут быть определены из фигуры ( 6) следующим образом: каждая прямая линия на диаграмме представляет множество механизмов, стадии которых могут образовывать один и только один возможный цикл. Кроме того, каждый направленный цикл определяется линией, показанной на фигуре ( 6), и любые две непараллельные линии на диаграмме определяют различные направленные циклы. [1]

Ясно, что S3 S5 - S6 является единственным направленным циклом из набора ( 10), содержащимся в ( 11), за исключением положительного кратного числа таких циклов. [2]

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

Модифицированные формы BTF и BNTF. [4]

Он особенно полезен в случаях, когда удаление небольшого числа дуг разбивает большие направленные циклы и соответствующие диагональные блоки в форме BTF становятся меньше ( см. разд. Этот метод практичен только для разрезания небольших блоков. Мы поясним его на примере. [5]

Так как вершины графа QD, лежащие на одном и том же направленном цикле, принадлежат одному и тому же диагональному блоку матрицы В, то можно использовать матрицу F для оп - ределения матрицы В по полученной матрице В следующим образом. [6]

Если граф G - сильно связный, то он должен содержать один или больше направленных циклов, и легко видеть, что в этом случае любой ориентированный цикл, не являющийся направленным, может быть записан как симметричная разность двух направленных циклов. [7]

Кроме того, в каждом графе Gn для упрощения их последующего анализа выделяются и свертываются имеющиеся направленные циклы. Каждая циклическая составляющая графа заменяется на один информационный элемент, от которого отходит дуга к следующему уровню обработки. Найденные циклические составляющие различных задач сравниваются между собой и, в случае совпадения, заменяются на одни и те же информационные элементы. [8]

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

Поскольку объединение ( как это понимается в теории множеств) направленной цепи из вершины V - t в Fy и направленной цепи из вершины Vj в Vj является направленным циклом, каждый сильно связный граф содержит по крайней мере один направленный цикл, и соответствующая матрица циклов содержит по меньшей мере одну строку, в которой все отличные от нуля элементы имеют одинаковый знак. [10]

Без потери общности мы предполагаем, что q, так как в противном случае мы применяем следующее доказательство для каждой компоненты в отдельности. Если представление ориентированного, но не направленного цикла, появляющееся в матрице & т, соответствует циклу, полностью лежащему внутри G, или G2, то этот цикл может быть представлен с помощью направленных циклов внутри относительно сильно связной компоненты. Следовательно, мы можем предположить, что матрица 3 т не содержит представления любого такого цикла. При этом остаются ориентированные циклы, проходящие как через С, так и G2, и ясно, что они не являются направленными. Представление каждого цикла этого типа содержит - 1 по крайней мере в одном положении, для которого в представлении в матрице 3т любого направленного цикла нет не обращающегося в нуль элемента. Кроме того, такие элементы не могут все аннулироваться другими ориентированными циклами, поскольку полный набор циклов, представляемый столбцами матрицы т, является независимым. Следовательно, поток Р ( с) не может быть неотрицательным, если только веса представлений всех циклов, проходящих через две или больше сильно связных компонент, не обращаются в нуль. [14]

Страницы: 1 2