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

Матрица инциденций

Другой матрицей, связанной с графом G, в котором помечены и вершины и ребра, является матрица инциденций B=||bij||. В этой (p´q)-матрице bij=1, если vi и xj инцидентны, и bij=0 в противном случае. Как и матрица смежностей, матрица инциденций определяет граф G с точностью до изоморфизма. На самом деле уже любые р-1 строки матрицы В определяют G, поскольку каждая строка равна сумме по модулю 2 всех остальных строк.

Следующая теорема связывает матрицу смежностей реберного графа графа G и матрицу инциденций графа G. Обозначим через ВТ матрицу, транспонированную к матрице В.

Теорема. Для любого (р, q)-графа G с матрицей инциденций В

A(L(G))=BTB-2Iq,

где Iq— единичная матрица порядка q.

Пусть М — матрица, полученная из матрицы -А заменой i-ro элемента главной диагонали на deg ui. В классической работе Кирхгофа приведена

Теорема (матричная теорема о деревьях). Пусть G - связный помеченный граф с матрицей смежностей А. Тогда все алгебраические дополнения матрицы М равны между собой и их общее значение есть число остовов графа G.

Лемма (а). Если Р и Q — соответственно (m´n)-матрица и (n´m)-матрица (m<n), то определитель матрицы PQ равен сумме произведений соответствующих главных определителей матриц Р и Q.

Пусть 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.