Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
реакции. Кроме того, легко видеть, что все нуль-комплексы могут
коллапсировать в один комплекс без изменения динамики системы. Таким
образом, без потери общности можно предположить, что имеется самое
большее один нуль-комплекс, который мы обозначим как 0. В результате
любая реакция, комплексы реагентов и продуктов которой являются нуль-
комплексами, может быть исключена полностью.
2.2. НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
Направленное ребро в графе G характеризуется своей начальной и конечной
вершинами, и в дальнейшем упорядоченная пара (/, j) обозначает
направленное ребро от вершины Vt к вершине V . Ненаправленный граф G0
получается из графа G при пренебрежении ориентацией ребер.
Последовательность ребер длины к - 1 является конечной
последовательностью вида (г,, /2)(/2, /3)...(/^_ ,, ik), к ^ 2. Когда все
ребра 6 последовательности ребер ориентированы в одном и
328
X. Отмер
том же направлении, последовательность является последовательностью
направленных ребер в графе G. Когда = ik, последовательность замкнутая, в
противном случае - она открытая. Начальная вершина - У,х, конечная - У,к>
все остальные вершины - внутренние вершины. Цепь в графе G0 - открытая
последовательность ребер, в которой все вершины различны; цикл в графе G°
- замкнутая цепь, в которой все внутренние вершины различны. Направленные
цепи и направленные циклы в графе G определяются аналогично их
эквивалентам в графе G0, и вершина К; называется достижимой из вершины
Vt, если существует направленная цепь из V, в Vj. Граф G°(G) называется
ациклическим, если он не содержит циклов (направленных циклов).
Полустепень захода (полустепень исхода) вершины V е G является числом
ребер, входящих в (исходящих из) вершины Vj, и они обозначаются
соответственно как df и d~. Степень df вершины VJ - сумма полустепеней
захода и полу-степеней исхода.
Ориентированный цикл в графе G - это цикл в графе G0 с ориентацией,
определяемой порядком вершин в цикле. Матрица цикла соответствующая графу
G, имеет элементы, определенные следующим образом:
( +1, если Ej - это г-й ориентированный цикл и ориента-
\ ции цикла и ребра одинаковы,
д&У - < - 1, если Ej - это /-й ориентированный цикл и
ориента-
/ ции цикла и ребра противоположны,
V 0 в остальных случаях.
ЗВ - матрица г' х г, где г' - число независимых циклов в графе G °. Она
содержит строку, в которой все отличные от нуля элементы имеют одинаковый
знак для. каждого направленного цикла в графе G.
Граф является связным, если каждая пара вершин связана цепью. Компонентой
является связный подграф G, с G, который максимален относительно
включения ребер, т. е. если G2 - связный подграф и Gj с G2 с G, то G, =
G2. Изолированная вершина является компонентой, и каждая вершина
содержится в одной и только в одной компоненте. Направленный граф -
сильно связный, если для каждой пары (Vt, Vf) вершина Vt достижима из и
наоборот. Сильно связной компонентой графа G (для краткости - сильной
компонентой) является сильно связный подграф графа G, максимальный
относительно включения ребер. Как и в случае направленного графа,
изолированная вершина является сильной компонентой, и каждая вершина
принадлежит к одной и*только одной
Глобальная динамика реакционных систем
329
сильной компоненте. Можно показать, что направленный граф - сильно
связный, если и только если существует замкнутая направленная цепь ребер,
содержащая все имеющиеся в графе ребра [2]. Поскольку объединение (как
это понимается в теории множеств) направленной *непи из вершины К, в и
направленной цепи из вершины Vj в Vt является направленным циклом, каждый
сильно связный граф содержит по крайней мере один направленный цикл, и
соответствующая матрица циклов содержит по меньшей мере одну строку, в
которой все отличные от нуля элементы имеют одинаковый знак.
Оказалось удобным связать с графом G или с G0 два векторных пространства,
определяемые следующим образом. Пусть V = ( Vx, ... , V ) - множество
вершин графа G яЕ = { Ех, ... , Ег\ - множество ребер графа G; обозначим
через С0(С,) множество всех функций, принимающих действительные значения,
на V(E). Функции в С0 называются 0-цепями, а функции в С, - 1-цепями,
хотя обычно скаляры берутся из абелевой группы, а не из поля; в таком
случае С0 и С, называются группами цепей [4] *. В рамках этой схемы
матрица инцидентности является представлением, связанным с каноническими
базами "граничного" оператора Сх - ?0 **. Если граф G имеет р вершин и q
компонент, легко показать, что p(d) = = р - q [2] ***.
Любой е е Л(гЕ) называется 1-циклом, и все они связаны с ориентированными
циклами и замкнутыми последовательностями направленных ребер графа G
следующим образом. Для любого ориентированного цикла G, e G пусть g е С,
будет таким, что
< + 1, если ?, е С, и ориентации цикла и ребра одинаковы,
g(?,) = - 1, если ?, € С, и ориентации цикла и ребра
противоположны,
Ч. О в остальных случаях.
Из этого определения следует, что если е G, т. е. не принадлежит G,,
