Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.2. Морфология графа

Разложение графа на базисные составляющие

Разложение графа на его базисные составляющие проведем на конкретном примере. Пусть будет задан простой связанный планарный граф Г, в котором пронумерованы все его ребра (рис. 3.23). Сплошными линиями выделен остов графа. Остовом (или покрывающим деревом) называется любое дерево графа Г, покрывающее все его вершины. Ребра, не вошедшие в остов, называются хордами. Символическим представлением остова является следующая последовательность весовых характеристик: Т(9, 1, 2, 1, 5, 1, 3, 1, 1).

Рис. 3.23

Прежде всего, найдем ранг (k) и цикломатическое число (l) нашего графа Г. Ранг определяется числом ребер покрывающего дерева, а цикломатическое число — не вошедшими в дерево ребрами; следовательно: m = k + l = 8 + 7 = 15 — общее число ребер в графе Г.

Выделим в графе Г базисные циклы и разрезы. Во всякий базисный цикл должна входить только одна хорда. Так, цикл c = (1, 3, 7) является базисным, а другой цикл c' = (1, 3, 5, 10, 9) уже не будет таковым. Разрезом (или сечением) графа Г в общем случае называется минимальное множество ребер, удаление которых делает граф несвязанным. Множество разрезов, отвечающих остову графа Т(Г), называется базисной системой разрезов. Каждый базисный разрез содержит одно ребро остова Т(Г); остальные ребра будут хордами. Для нашего случая базисным является, например, разрез s = (2, 5, 10), но не s' = (2, 4, 6, 8). Базисные разрезы и циклы удобно представлять матрицами. Число строк в матрице разрезов (S) равно числу базисных разрезов (k), а число столбцов — общему числу ребер (m); если ребро участвует в разрезе, то в соответствующей позиции выставляется 1, в противном случае — 0.

S = .

Размерность матрицы циклов (C) равна l · m; нули и единицы в ней выставляются так же, как и в матрице S.

C = .

Путем перегруппировки столбцов матрицы S и C можно привести к систематическому виду S' = , C' = :

S' = ,

C' = .

При перемножении матриц убеждаемся, что

S' · C'* = 0,   G_lk = H*_kl ,    H_kl = G*_lk .

здесь звездочка означает транспонирование, а умножение производится по mod (2). Матрицы разрезов (S') и циклов (C') взаимно ортогональны. Матрица инцидентности В(Г) путем линейной комбинации только строк может быть сведена к матрице разрезов S, при этом высвобождается одна нулевая строка. Строки матрицы В(Г) пронумерованы в соответствии с вершинами графа Г (рис. 3.23). Справа от матрицы S показана линейная комбинация строк (суммирование производится по mod (2)).

В(Г) =

S =

Графу Г отвечает 15-компонентный вектор:

a = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1).

Всякий вектор может быть представлен линейной комбинацией базисных векторов. Следовательно, и наш вектор a может быть представлен базисными разрезами и циклами. Чтобы определить, через какие именно разрезы и циклы выражается наш вектор a, необходимо вычислить некоторую совокупность определителей Грама. Сначала запишем исходные определители Грама для разрезов (g) и циклов (h) в общем виде:

g = , h = .

Элементы определителей Грама g и h симметричны ( s_ij = s_ji , c_ij = c_ji ) и представляют собой скалярные произведения по mod (2) базисных векторов соответствующих индексов. Базисные векторы разрезов берутся как строки матрицы S, а базисными векторами циклов являются строки матрицы C. Для нашего примера имеем:

g = ,     h = ,

где скалярные произведения принимают следующие значения:

s₁₁ = s₁s₁ = (0 1 0 0 1 0 0 0 0 1 0 0 0 0 0) · (0 1 0 0 1 0 0 0 0 1 0 0 0 0 0) =

= 0 + 1 + 0 + 0 + 1 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 0 + 0 = 1,

s₁₂ = s₁s₂ = (0 1 0 0 1 0 0 0 0 1 0 0 0 0 0) · (0 0 1 0 1 1 1 0 0 0 0 0 0 0 0) =

= 0 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 1, ...

c₄₅ = c₄c₅ = (1 0 0 1 0 0 0 1 0 0 0 0 0 0 0) · (1 1 0 1 0 0 0 0 1 1 0 0 0 0 0) =

= 1 + 0 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 0, ...

Далее алгоритм вычислений строится следующим образом. Диагональ определителя g поочередно ставят на место первой его строки, получая таким образом производный определитель g₁, затем на место второй, получая g₂, и т.д. до тех пор, пока не получат g₈. Аналогично находят все семь производных определителей для циклов:

g₁ = 1, g₂ = 1, g₃ = 0, g₄ = 0, g₅ = 1, g₆ = 1, g₇ = 1, g₈ = 0;

h₁ = 0, h₂ = 1, h₃ = 1, h₄ = 1, h₅ = 0, h₆ = 0, h₇ = 1.

В частности:

g₁ = = 1,     g₂ = = 1,

h₁ = = 0,    ... ,    h₇ = = 1.

Значения производных определителей играют роль коэффициентов разложения вектора a по базисным векторам разрезов и циклов:

a_s = g₁s₁ + g₂s₂ + ... + g₈s₈, 

a_c = h₁c₁ + h₂c₂ + ... + h₇c₇, 

a = a_s + a_c.

Базисные компоненты с отличным от нуля коэффициентом участвуют в образовании вектора a.

		s1 = 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0
		s2 = 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0
		s5 = 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
		s6 = 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0
		s7 = 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0
		c2 = 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0
		c3 = 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0
		c4 = 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0
		c7 = 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
		a =  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Ниже приведены результаты разложения по базисным разрезам и циклам (a₁ и a₂) графов (Г₁ и Г₂), показанных на рис. 3.24.

s1 = 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1	s1 = 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0
s2 = 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0	s2 = 0 1 1 0 1 0 0 1 0 0 1 0 0 1 0
s3 = 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0	s3 = 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
s4 = 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0	s4 = 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
s5 = 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1	s5 = 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0
s6 = 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1	s6 = 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
s7 = 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0	s7 = 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0
s8 = 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1	s8 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
c1 = 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0	c1 = 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
c2 = 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0	c2 = 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0
c3 = 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0	c3 = 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0
c4 = 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0	a2 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
c5 = 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1	
a1 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	

Рис. 3.24

Рис. 3.25

На рис. 3.25 изображены еще два простых связанных планарных графа Г₃ и Г₄ на 15 ребрах, внешне ничем не отличающихся от своих предшественников, но которые, однако, уже не могут быть разложены в поле чисел по mod (2) по своим базисным разрезам и циклам. Все их определители Грама, вычисленные по изложенной выше методике, оказываются равными нулю. С точки зрения традиционной линейной алгебры, это свидетельствует о наличии линейной зависимости между векторами.

Еще один вопрос, который здесь возникает: каково общее число возможных остовов? Количество деревьев рассчитывается с помощью определителя размерности (n – 1) · (n – 1), на диагонали которого выставляются степени n – 1 вершин (отсутствовать может любая из n вершин), а недиагональные элементы ij могут быть вида: 0 (если вершины i и j между собой не связаны), –1 (если i и j связаны одной связью), –2 (если i и j связаны двумя связями) и т.д.