4. Матрицы циклов и разрезов
Пусть 
остов неориентированного графа. Матрицей фундаментальных циклов графа 
называется матрица 
состоящая из 
строк и 
столбцов, в которой 
равно 1, если ребро 
принадлежит циклу 
и равно 
в противном случае. Если ребра, не принадлежащие дереву 
пронумеровать последовательно от 1 до 
а ребра дерева 
пронумеровать от 
до 
то матрица циклов 
будет иметь вид
где I — единичная матрица. Это объясняется тем, что каждый цикл 
содержит одно, и только одно ребро, не принадлежащее остову 
и циклы всегда можно пронумеровать по числу принадлежащих им внеостовных ребер, вследствие чего все единицы в первой 
-подматрице матрицы 
лежат на диагонали.
Матрица фундаментальных разрезов 
определяется аналогично — как матрица 
строками и 
столбцами, где 
есть 1, если ребро 
принадлежит разрезу 
и 
в противном случае. При той же самой нумерации ребер, что и выше, матрица К имеет тзид
так как теперь каждый фундаментальный разрез содержит одно, и только одно ребро из ребер дерева 
В графе на рис. 9.7 возьмем остов, изображенный жирными линиями. Тогда матрица фундаментальных циклов равна
Рис. 9.7.
матрица фундаментальных разрезов равна
где разрезы 
соответствующие ребрам остова, имеют номера 
Существует несколько интересных соотношений между матрицами циклов, разрезов и инциденций. Ниже все арифметические операции являются операциями по модулю 2. Здесь мы будем рассматривать неориентированные графы без петель.
Теорема 2. Матрица инциденций В и транспонированная матрица фундаментальных циклов 
ортогональны, т. е. 
Теорема 3. Матрица фундаментальных циклов 
и транспонированная матрица фундаментальных разрезов К ортогональны, т. е. 
Эти две теоремы являются немедленным следствием двух очевидных фактов:
(1) Каждая вершина в цикле инцидентна четному числу ребер (а в случае простого цикла — двум ребрам) этого цикла.
(2) Каждый разрез цикла, индуцированный некоторым разрезом, имеет четное число ребер, общих с этим разрезом.
Теорема 2 следует из (1), а теорема 3 — из (2), если вспомнить, что все операции рассматриваются по модулю 2, так что, например, 
Кроме того, существуют доказательства этих теорем [21, 17, 6], не использующие предположения о фундаментальности циклов и разрезов. Следовательно, сформулированные теоремы справедливы для любых матриц циклов и разрезов. Последние определяются аналогичным образом.
По теореме 3 можно написать
Поэтому
так как 
Вследствие этого матрица фундаментальных разрезов может быть немедленно получена, как только известна матрица фундаментальных циклов, и наоборот. Справедливость соотношения (9.3) можно проверить на приведенных выше матрицах 
для графа, изображенного на рис. 9.7.
