Связанные с графами

Рассмотрим алгебраическую систему ₂= с двухместными операциями кольцевого сложения ⊕ и умножения ⊙, задаваемыми следующими правилами: 0⊕0=1⊕1=0, 1⊕0=0⊕1=1, 0⊙0=0⊙1=1⊙0=0, 1⊙1=1. Система ₂ является булевым кольцом (см.§2.6) и, более того, образует поле.

Пусть G= связный неорграф, имеющий n вершин и m ребер . Произвольному множеству ребер A R поставим в соответствие вектор = , положив

Каждому множеству ребер соответствует единственный вектор, состоящий из нулей и единиц, а для любого набора нулей и единиц найдется единственное множество ребер, соответствующее этому набору. Таким образом, существует биекция между булеаном множества ребер R и множеством всех наборов длины m, состоящих из нулей и единиц: P (R)↔ ^m. Пусть = и =( )- наборы (векторы) из ^m. Определим сложение векторов с помощью соотношения ⊕ =( ⊕ , … , ⊕ ) по правилам, определенным в поле ₂. Кроме этого, определим произведение векторов на элементы , положив λ ⊙ =(λ⊙ , … ,λ⊙ ). Множество векторов ^m с операциями сложения ⊕ и умножения ⊙ на элементы поля ₂ образует линейное пространство над полем ₂. Это пространство обозначим через ( ₂).

Отметим, что сложение ⊕ векторов и соответствует кольцевой сумме множеств ребер A и B, представляемых этими векторами. Действительно, равенство выполняется тогда и только тогда, когда =1, (т.е. или , (т.е. . Следовательно, сумме ⊕ соответствует множество (AB) (BA)=A⊕B.

Внутреннее произведение векторов = и =( определяется соотношением ( = Равенство ( =0 означает, что четное число произведений ⊙ равно 1. Для таких произведений =1, и, следовательно, соответствующие векторам и множества ребер A и B имеют четное число общих ребер.

Множество ребер A называется границей (кограницей), если A есть объединение множеств ребер некоторых циклов (коциклов), из которых любые два множества не имеют общих ребер. Нетрудно заметить, что кольцевая сумма A₁⊕ A₂ также является границей (кограницей). Следовательно, множества V_Г= соответствует некоторой и V_K = вектор соответствует некоторой образуют линейные подпространства пространства V_{m 2}).

Теорема 4.13.1.1. Если фундаментальное множество циклов графа G, то множество 𝔅_С = векторов, соответствующих фундаментальным циклам, образует базис подпространства границ V_Г.

2. Если фундаментальное множество коциклов графа G, то множество 𝔅_K= векторов, соответствующих фундаментальным разрезам, образует базис подпространства кограниц V_K.

Следствие 4.13.2. 1. Размерность dim V_Г подпространства границ V_Г равна цикломатическому числу , а размерность dim V_K подпространства кограниц V_K равна корангу .

2.Любой цикл ( коцикл ) в графе можно представить в виде кольцевой суммы некоторых фундаментальных циклов (разрезов).

Два подпространства V₁ и V₂ векторного пространства V_m ( ₂) называются ортогональными (V₁ V₂), если для любых векторов V₁ и V₂ их внутреннее произведение ( , ) равно 0.

Заметим, что по теореме 4.12.3 любой цикл C с любым разрезом K имеет четное число общих ребер, т.е. для соответствующих векторов и их внутреннее произведение ( , ) равно нулю. В частности, для любых векторов _C и _K справедливо ( , )=0. Так как множества _C и _K образуют базисы подпространств V_Г и V_K, то V_ГV_K.

Отметим также, что при умножении матрицы фундаментальных циклов C на транспортированную матрицу фундаментальных разрезов K^T в поле ₂ строка умножается на столбец по правилу произведения и ( , )=0. Это означает что C K^T=0, а также K C^T=0.

У п р а ж н е н и е. Проверить, что для матриц C и K из примеров 4.11.1 и 4.12.1 справедливо C K^T=0.