Матрица циклов и ее связь с матрицей инцидентности

Циклы графов, пронумерованные определенным порядком, можно представить матрицей циклов С.

		е1	е2	е3	е4	е5
	С1
С=	С2
	С3

Матрица циклов имеет m столбцов(по числу ребер) и количество строк, равное числу циклов (m-n+1).

Матрицу циклов называют еще цикломатической матрицей.

Строку матрицы С: называют также циклическим вектором графа G. Как видно из матрицы циклов, вектор С₃ = С₁Å С₂ =11010 Å 01101 = 10111, является линейной комбинацией векторов С₁ и С₂.

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

Пусть это дерево состоит из ребер {e₁, e₂,e₃ }, тогда хордами будут ребра е₄ и е₅ . Вспомним, что базисный цикл состоит из одной хорды и ветвей остовного дерева. Переставим столбцы матрицы циклов так, чтобы первым строкам и столбцам соответствовали хорды остовного дерева:

		е4	е5	е1	е2	е3
Сf=	е4
	е5

I С_ft

Таким образом, базисная матрица циклов С_f является подматрицей матрицы циклов C и включает только циклы, определяемые хордами выбранного остовного дерева.

Эту матрицу можно записать в виде:С_f= [ I | C_ft ], где I – единичная матрица хорд, а элементами матрицы C_ft являются ветви выбранного остовного дерева, по отношению к которому определены базисные циклы.

Кроме того, матрицу С_f можно представить состоящей из двух блоков C_f = (С₁₁ С₁₂), где С₁₁= I, С₁₂= C_ft.

Запишем матрицу инцидентности графа G, переставив столбцы, как и у базисной матрицы циклов:

		е4	е5	е1	е2	е3
	V1
A=	V2
	V3
	V4

Так как ранг матрицы инцидентности равен n-1, где n- число вершин, то можно выделить неособенную матрицу в правом верхнем углу А₁₂ размерностью (n-1)х(n-1), состоящую из ветвей остовного дерева(так же ранга n-1) и представить матрицу инцидентности А в виде блочной матрицы:

А=	А11	А12	, где	А11=
				; А12=
А21	А22

А₂₁=| 0 1 | A₂₂= | 0 0 1 |

Матрица А₁₁ представляет кодерево, состоящее из хорд е₄ и е₅, матрица А₁₂ представляет дерево по отношению к которому определяются базисные циклы.

Матрицы А₂₁ и А₂₂ линейно зависят от А₁₁ и А₁₂ , выражаются через них в виде суммы элементов строк по модулю 2, что легко проверяется непосредственным сложением. Доказано, что А. С' = 0.

В наших новых обозначениях это выражение можно переписать следующим образом:

А₁₁ А₁₂ I

А₂₁ А₂₂ C₁₂ =0

Проверим его непосредственно для графа G:

0 0 1 1 1 1 0 00

А₁₁ А₁₂ I 1 0 1 0 1 0 1 00

А∙С = А₂₁ А₂₂ C₁₂ = 1 1 0 1 0 х 1 0 = 00 =0.

0 1 0 0 1 1 1 00

0 1 00

Из этого же выражения следует, что:

А₁₁.I + A₁₂. C^′₁₂ = 0

Поскольку матрица А₁₂ неособенная то:

С₁₂= А₁₂^-1. А_11, т.е матрицу циклов (транспонированную) можно получить из матрицы инцидентности представив ее в виде блоков, состоящих из подматрицы дерева и подматрицы кодерева, т.е. из ветвей остовного дерева и хорд кодерева.

Рассмотрим пример для нашего графа:

1 1 1 1 0

А₁₂ = 1 0 0 |A₁₂| =-1 х = -1 =1

0 1 0 0 1

Определитель А₁₂ вычислен путем разложения его по элементам третьего столбца, с учетом применения алгебры по модулю 2.

Для обращения матрицы существуют стандартные процедуры (напримерmathcad), но мы воспользуемся классическим методом.

а₁а₂ а₃ в₂с₃-в₃с₂ а₃с₂-а₂с₃ а₁в₃-а₃в₂

А= в₁ в₂ в₃; А^-1= 1/ |A|в₃с₁-в₁с₃ а₁с₃-а₃с₁ а₃в₁-а₁в₃

с₁ с₂ с₃ в₁с₂-в₂с₁ а₂с₁-а₁с₂ а₁в₂-а₂в₁

подставив в выражение элементы матрицы А₁₂, получим,

0 1 0 1 1 1

А₁₂^-1 = 0 0 1; проверим А₁₂. А₁₂^-1 = 1 0 0 х

1 1 1 0 1 0

0 1 0 1 0 0

х 0 0 1 = 0 1 0

1 1 1 0 0 1

найдем траспонированную матрицу С′₁₂

0 1 0 0 0 1 0

С′₁₂= А₁₂^-1. А₁₁= 0 0 1. 1 0 = 1 1

1 1 1 1 1 0 1

1 1 0

откудаС₁₂= 0 1 1.

Присоединив слева единичную матрицу, получим матрицу базисных циклов:

1 0 1 1 0

С_f= (I / C₁₂)=

0 1 0 1 1

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

Однако, проще это делать “ вручную”:

Пусть остовное дерево включает ветви е₁, е₂, е_3, а хорды кодеревы е₄ и е₅. Добавляя к дереву хорду е₄получаем цикл е₂е₃е₄, добавляя хорду е₅, получаем цикл е₁е₂е₅. Получив циклы, записываем их в матрицу циклов.

	e1	e2	e3	e4	e5
Сf =

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