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

Циклы графа рис. 5.3 (перенумерованные, как показано на рис. 5.4) можно характеризовать матрицей, каждая строка которой характеризует один из циклов:

(Принадлежность каждого ребра, за исключением в точности двум циклам является в данном случае совпадением.) Можно заметить, что матрица циклов также является блочно-диагональной.

Рис. 5.3.

Рис. 5.4.

Это является следствием того факта, что каждый цикл полностью содержится в

одной из компонент и ребра каждой компоненты перенумерованы последовательно во избежание необходимой в противном случае перестановки столбцов.

Теорема 5.2. Матрица инцидеиций А ортогональна транспонированной матрице циклов т. е. если обе матрицы получены при одном и том же порядке дуг.

Идея доказательства заключается в следующем: каждая вершина, принадлежащая некоторому циклу, инцидентна четному числу ребер, принадлежащих этому же циклу. Поэтому при умножении строки матрицы А на столбец С мы получаем либо сумму элементов, каждый из которых равен нулю (если вершина не принадлежит циклу), либо сумму, равную нулю по модулю 2.

Упражнение 5.3. Проверить теорему 5.2 для матрицы инцидеиций и матрицы циклов графа, показанного на рис. 5.3.

Замечание. Если граф не связен, то матрицы инцидеиций, циклов и разрезов могут исследоваться отдельно для каждой компоненты, так как ни одно из свойств, изучаемых ниже, не зависит от факта существования более одной компоненты. Ограничимся поэтому изучением связных графов (т. е. без петель с ребрами и вершинами.