Рассмотрим алгебраическую систему 2= с двухместными операциями кольцевого сложения ⊕ и умножения ⊙, задаваемыми следующими правилами: 0⊕0=1⊕1=0, 1⊕0=0⊕1=1, 0⊙0=0⊙1=1⊙0=0, 1⊙1=1. Система 2 является булевым кольцом (см.§2.6) и, более того, образует поле.
Пусть G= связный неорграф, имеющий n вершин и m ребер . Произвольному множеству ребер A R поставим в соответствие вектор = , положив
Каждому множеству ребер соответствует единственный вектор, состоящий из нулей и единиц, а для любого набора нулей и единиц найдется единственное множество ребер, соответствующее этому набору. Таким образом, существует биекция между булеаном множества ребер R и множеством всех наборов длины m, состоящих из нулей и единиц: P (R)↔ m. Пусть = и =( )- наборы (векторы) из m. Определим сложение векторов с помощью соотношения ⊕ =( ⊕ , … , ⊕ ) по правилам, определенным в поле 2. Кроме этого, определим произведение векторов на элементы , положив λ ⊙ =(λ⊙ , … ,λ⊙ ). Множество векторов m с операциями сложения ⊕ и умножения ⊙ на элементы поля 2 образует линейное пространство над полем 2. Это пространство обозначим через ( 2).
Отметим, что сложение ⊕ векторов и соответствует кольцевой сумме множеств ребер A и B, представляемых этими векторами. Действительно, равенство выполняется тогда и только тогда, когда =1, (т.е. или , (т.е. . Следовательно, сумме ⊕ соответствует множество (AB) (BA)=A⊕B.
Внутреннее произведение векторов = и =( определяется соотношением ( = Равенство ( =0 означает, что четное число произведений ⊙ равно 1. Для таких произведений =1, и, следовательно, соответствующие векторам и множества ребер A и B имеют четное число общих ребер.
Множество ребер A называется границей (кограницей), если A есть объединение множеств ребер некоторых циклов (коциклов), из которых любые два множества не имеют общих ребер. Нетрудно заметить, что кольцевая сумма A1⊕ A2 также является границей (кограницей). Следовательно, множества VГ= соответствует некоторой и VK = вектор соответствует некоторой образуют линейные подпространства пространства Vm 2).
Теорема 4.13.1.1. Если фундаментальное множество циклов графа G, то множество 𝔅С = векторов, соответствующих фундаментальным циклам, образует базис подпространства границ VГ.
2. Если фундаментальное множество коциклов графа G, то множество 𝔅K= векторов, соответствующих фундаментальным разрезам, образует базис подпространства кограниц VK.
Следствие 4.13.2. 1. Размерность dim VГ подпространства границ VГ равна цикломатическому числу , а размерность dim VK подпространства кограниц VK равна корангу .
2.Любой цикл ( коцикл ) в графе можно представить в виде кольцевой суммы некоторых фундаментальных циклов (разрезов).
Два подпространства V1 и V2 векторного пространства Vm ( 2) называются ортогональными (V1 V2), если для любых векторов V1 и V2 их внутреннее произведение ( , ) равно 0.
Заметим, что по теореме 4.12.3 любой цикл C с любым разрезом K имеет четное число общих ребер, т.е. для соответствующих векторов и их внутреннее произведение ( , ) равно нулю. В частности, для любых векторов C и K справедливо ( , )=0. Так как множества C и K образуют базисы подпространств VГ и VK, то VГVK.
Отметим также, что при умножении матрицы фундаментальных циклов C на транспортированную матрицу фундаментальных разрезов KT в поле 2 строка умножается на столбец по правилу произведения и ( , )=0. Это означает что C KT=0, а также K CT=0.
У п р а ж н е н и е. Проверить, что для матриц C и K из примеров 4.11.1 и 4.12.1 справедливо C KT=0.