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

В матрице разрезов S столбцы соответствуют ребрам, строки разрезам. Если ребро входит в разрез, то элемент матрицы равен 1, если нет, то 0.

Для рассматриваемого графа разрезы сведены матрицу.

	siej	е1	е2	е3	е4	е5
	s1
	s2
S=	s3
	s4
	s5
	s6

Разрезы S₁, S₂, S₃ являются базисными, остальные их- линейными комбинациями:

S₄ = S₁Å S₂Å S₃

S₅ = S₁Å S₂

S₆ = S₂Å S₃

Строки матрицы S называются векторами разрезов. Ранг матрицы разрезов равен n-1, в нашем случае r=n-1= 4-1=3.

Представим матрицу базисных разрезающих множеств относительно остовного дерева, им соответствующего. Остовное дерево, как и для базисных циклов, состоит из ребер е₁, е₂, е₃.

e₁ e₂ e₃ e₄ e₅

s₁1 0 0 1 0

S_f =s₂ 0 1 0 1 1 или S_f = (I | S_fc)

s₃ 0 0 1 0 1

где I- единичная матрица, включающая ветви дерева, относительно которого определяются базовые разрезающие множества, а S_fc – матрица, включающая хорды, которые входят в разрез, они же являются основой базисных циклов, полученных по отношению к этому же остовному дереву.

Рассмотрим, как из матрицы разрезов получить матрицу циклов.

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

	е4	е5	е1	е2	е3
S=

S₁₁ I

Представим S в виде двух блочных матриц т.е. S= S₁₁| I. Из соотношения ортогональности, которое, существует между матрицей циклов и транспонированной матрицей разрезов, имеем (I | C₁₂)(S′₁₁ | I) = 0 для нашего случая:

10110 011 000

(I | C₁₂) (S′₁₁ | I) = 01011 100 = 000 = 0.

Следовательно,IS′₁₁ + C₁₂I =0, откудаS′₁₁= C₁₂, т.к.-1Ξ 1 мод 2.

S′₁₁= 011 = C₁₂

присоединив слева матрицу: I = 10,

получим матрицу базисных циклов

С_f =I|C₁₂ = 01011, которую ранее мы получили другим путем.

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

Все действия по построению матрицы базисных циклов и матрицы базисных разрезов относительно остовного дерева вытекают из равенства I S′₁₁ + C₁₂ I =0 и сводятся к следующему.

-выбирают остовное дерево Т, например е₁е₂е₃ (11100).

-добавляя к остовному дереву по одной хорде кодерева (е₄,е₅), получают базисные циклы, число которых равно числу хорд:

е₁е₂е₄ (11010) и е₂е₃е₅ (01101).

-составляют матрицу базисных циклов так, чтобы хорды (е₄ и е₅) образовалии единичную матрицу:

е₄е₅ е₁ е₂ е₃

1 0 1 1 0

С_f = (I / C₁₂)= 0 1 0 1 1 =I|C_ft|=(C₁₁C₁₂)

Матрицу I=C₁₁ отбрасывают, матрицу С₁₂ транспонируют и присоединяют к ней справа единичную матрицу, соответствующую остовному дереву (е₁е₂е₃), получая матрицу базисных разрезов, число которых равно числу ребер в остовном дереве (n-1)

S = [ S₁₁ |I], где S₁₁ = C₁₂

е₄е₅е₁е₂е₃

1 0 1 0 0

S = 1 1 0 1 0

0 1 0 0 1

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

Рассмотренные матрицы являются удобной и практически исчерпывающей формой представления структурных свойств графов.

Определение базисных матриц для циклов и разрезов основано на понятиях остовного дерева, ветвей дерева и хорд.

Задавая или вычисляя матрицы разрезов и циклов, мы всегда фиксируем по отношению к какому остовному дереву они определялись.

Число независимых остовных деревьев определяется достаточно просто. Каждое остовное дерево содержит n-1 ветви. Ребер в графе m, поэтому |Т|= m/(n-1); максимальное число ребер для полносвязного графа m = n(n-1)/2, отсюда |Т|_мах= n(n-1)/2(n-1)=n/2.

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

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

Для определения общего числа остовных деревьев воспользуемся матрицей степеней вершн графа К=|| k_ij || размерности n x n, которая определяется следующим образом:

-ρ, если i ≠ j и вершины v_iи v_j связывают ρ

К_ij = паралельных ребер;

d(v_i), если i=j

для рассматриваемого графа G(4,5) матрица ||k_ij || имеет вид:

3 -1 -1 -1

K_ij = -1 2 -1 0

-1 -1 3 -1

-1 0 -1 2

Доказано, что все алгебраические дополнения матрицы степеней связного неориентированного графа имеют одинаковое значение, равное числу остовных деревьев графа.

Рассмотрим алгебраическое дополнение к элементу К₄₁:

-1 -1 -1 2 -1 -1 -1

Т_Σ = - 2 -1 0 = - + =5+3= 8

-1 3 -1 -1 3 2 -1

аналогичный результат получим, если определим алгебраическое дополнение к элементу К₂₃

3 -1 -1 -1 -1 3 -1 3 -1

Т_Σ = - -1 -1 -1 = +0* -2* = 8

-1 0 2 -1 -1 -1 -1 -1 -1

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

Эти остовы были определены ранее и сведены в таблицу 1.