Матрица циклов

Пусть G - граф, у которого помечены ребра и простые циклы. Матрицей цикловC=||cij|| графа G называется матрица, в которой, для каждого простого цикла графа G есть строка и для каждого

ребра — столбец, причем cij=1, если i-й цикл содержит реброxj, сij=0 в противном случае. В отличие от матриц смежностей и инциденций матрица циклов не определяет граф с точностью до изоморфизма. Очевидно, что если ребро не принадлежит ни одному циклу, то по матрице циклов нельзя узнать, принадлежит оно графу или нет. Даже если исключить такие ребра, то все равно матрица С не определяет однозначно граф G, как показано на примере двух графов, изображенных на рисунке Оба графа имеют циклы

Z1={X1, X2, Х3}, Z4={Х1,Х3, Х4, Х5,Х6},

Z2={Х2, X4, Х5, X6}, Z5={Х2, Х4, Х5, X7, X8},

Z3={X6,X7,X8}, Z6={X1,X3,X4,X5,X7,X8},

и, следовательно, одну и ту же матрицу циклов

В теореме устанавливается связь между матрицей циклов и матрицей инциденций. В комбинаторной топологии этот результат можно выразить так: «граница границы любой цепи является нулевой».

Теорема.Если граф G имеет матрицу инциденций В и матрицу циклов С, то

СBT=0 mod 2.