Матрицы смежности и перечисления путей

Напомним, что матрицей смежности А=||a_ij|| помеченного графа G(V,E) с n вершинами называется (nxn)- матрица, в которой а_ij =1, если вершина v_iсмежна с вершиной v_j и а_ij=0 в противном случае.

Если граф не является связным, то путем соответствующей нумерации вершин матрицу смежности можно представить блочной матрицей диагонального вида, в которой каждый блок соответствует одной из компонент связности, например:

Рис.20. Граф с тремя компонентами и его блочная матрица смежности

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

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

Если использовать булеву алгебру, то элемент aⁿ_ij показывает, есть ли между вершинами v_i и v_j путь, длиной меньше или равной n ребер.

При этом о значении диагональных элементов матрицы договариваются заранее исходя из сущности решаемой задачи

А=					; А21=

А2=						; А22=

А32=						А42=

Графы G₁ и G₂, соответствующие матрицам смежности А₁ и А₂ приведены на рис.21;

Рис.21. Графы G_1, G₂ и G₃

Граф G₁ после возведения его матрицы смежности А₁ в квадрат становиться полносявзным, т.е. каждая его вершина связана со всеми остальными либо одним ребром в соответствии с матрицей А₁, либо путем, состоящим из двух ребер в соответствии с матрицей А²₁.

Появляющиеся петли при вершинах, соответствующие диагональным элементам, можно принимать или не принимать во внимание, в зависимости от решаемой задачи.

При возведении матрицы А₂ в квадрат в графе G₂ появляются дополнительные связи между вершинами v₁ иv₃ (v₃ и v₁), v₂ и v₄ (v₄и v₂), v₃ и v₅ (v₅ и v₃) и граф G₂ принимает вид, как показано на рис.22;

А) ; б) ; в) ; г) U U

Рис.22.Механизм появления новых связей при возведении в степень {2,3,4}матрицы А₂.

При возведении матрицы А³₂ = А²₂ х А₁ появляются новые пути из тех ребер, связывающие вершины v₁ иv₂; v₁ иv₄ и.т.д произведя сложение матриц по правилам булевой алгебры, получим:

А_Σ = А₂U А²₂U А³₂U А⁴₂

0 1 1 1 1

1 0 1 1 1

А_Σ = 1 1 0 1 1

1 1 1 0 1

1 1 1 1 0

Граф, соответствующий этой матрице, без учета петель является полносвязным и показан на рис.22.

В матрицах А₂ со степенью меньше 4 элементы а₁₅ = а₅₁ = 0. Поэтому m = 4 является минимальной степенью, при возведении в которую элементы матрицы А^m_S содержат только положительные элементы.

В этом случае все вершины являются достижимыми из любой вершины путем, состоящим из не более чем m ребер (дуг).

Граф G и соответствующая ему матрица смежности А называются примитивными, а m – индексом примитивности.

На рис.21 в граф G₃ не является примитивным, поскольку из его вершин 7 и 8 нет ребер, связывающих их с другими вершинами.

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

Так, при возведении в квадрат матрицы А₁, соответствующей графу G₁ на рис.21а получим:

А21

=А1

х А1=

х

=

На главной диагонали стоят степени вершин.

Из вершины v₁ в v₂ есть один путь из двух ребер е₂ е₄; в вершину v₃ – два пути е₁ е₄ и е₃ е₅; в вершину v₄- е₂ е₅.

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

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

Структурная матрица в определяется таким образом:

b_ij, если вершины v_i и v_j соединены ребрам и i < j

В = 1, если i = j

b_ij, если вершины v_i и v_j соединены ребром, но i>j

0 в остальных случаях

алгебра такова: 1 U 1 = 1; 1.0 = 0.1=0; 1 U 0 = 0 U 1=1

ā.а=0; а U а = а;а Uав = а; 1 U а =1

для графа G₁ рис 31а структурная матрица примет вид:

		а	в	С				aUb	bUadUcē	cUbe
	ā		d				ā U d		dUāb	ācU e
В=	b			ē	;	B2=	вUa Uce	Ua		eUbc
			ē				Uē	acU е	ēU c

Для удобства заполнения матрицы В² записываем i-ю строку, под ней j-й столбец и производим умножение строки на столбец по изложенным правилам.

1 а в с

В²₁₁= 1 ā = 1*1U а* ā U в* Uс * = 1

1 а в с

В²₁₂= а 1 0= 1*aU а 1U в U с 0 = aUв

1 а в с

В²₁₃= в d 1 ē = 1*вU а dU в Uс ē = вUаdU с ē

1 а в с

В²₁₄= с 0 е 1 = сU а 0UвеU с = сUве

Для того, чтобы перечислить одно, двух и трехзвенные пути, необходимо умножить матрицу В²хВ₁ т.е. В³= В²хВ.

Получим, например, первую стоку матрицы В³

В311=		аUb	bUadVc ē	cUbe
	ā

= 1U ā b U a d UbceUcb ē = 1

В312=		аUb	bUadUc ē	cUbe
a

=a U a b U b U c ē = a U b U c ē

В313=		аUb	bUadUc ē	cUbe
b	d		ē

= b U ad U b U ad U c ē U c ē = b U ad U c ē

В314=		аUb	bUadUc ē	cUbe
c		e

= c UbeUade

В323=	ā U d		b U ā b	c Ube
b	d

= ā b U d U ā e

В324=	ā U d		b U ā b	c Ube
c		e

= ā U c d U de U ā be

В334=	U ā	U a		e U c
c		e

= c Uc ā U e U c

матрица В³ имеет вид:

	a U b Uс е d	b UadU c ē	c UbeUade
ā U d		d U a U ā c ē	ā c U de U ā b c U d
b UadU e	UabUa e		e U c Uc a
U ē U ā ē	а c U d e Uа c U b ē	e U Ucad

Дальнейшее возведение в степень матрицы смежности не дает новых путей (только циклы), а алгоритм определения базисных циклов был рассмотрен ранее.

В каждой из клеток (n-1) степени структурной матрицы представлены все пути, ведущие из вершины v_i в вершину v_j. Каждую из клеток в связи с этим можно представить отдельной матрицей путей М_st строкам которой соответствуют пути, а столбцам –дуги, входящие в эти пути.

Например, для клетки 13 матрица путей примет вид:

		е1	е2	е3	е4	е5
		a	b	c	d	e
	m1
Мst=	m2
	m3

m^k₁₃ = m¹₁₃Um²₁₃Um³₁₃ = b U ad U c ē.

Перечисление путей М_st из произвольной вершины s в произвольную вершину t может быть получено из структурной матрицы В раскрытием определителя подматрицы В_ts, получаемого из структурной матрицы В вычергиванием s-го столбца и t –й строки:

М_st = detв_ts = | в_ts |

1 a b c a b c

в= a 1 d o;в₁₃= 1 d o

b d 1 e o e 1

c o e 1

a b c

m^k₁₃=|в₁₃| = 1 d O =а d OU b c UO = ad U b Ucе

o e 1 e 1 e 1

Для вершин v₁ и v₃ таких независимых путей 3 – это b(e₂) Uad(e₁e₄) Uce(e₃e₅), для вершин v₂ и v₃ таких пути два:d(e₄) U a b (e₁e₂). Это является следствием того, что степень вершины d(V₄) = 2, поэтому и число независимых путей в нее и из нее не может превышать этого числа.

И вообще число независимых путей из одной вершины в другую не может превышать минимальную степень одной из них.

В наших примерах:

d(v₁) = 3; d(v₂) = 2; d(v₃) = 3; поэтому между v₁ и v₃ может быть не более трех независимых путей, а между v₂ и v₃ не более двух.

В множестве путей М₂₃ пути ab и асе содержат общее ребро а, поэтому они не могут быть независимыми.

Множество путей между двумя произвольными вершинами связано с понятием “сечение”, которое является более общим случаем понятия “разрез”.

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

Сечением называется минимальное число ребер или вершин, удаление которых делает две вершины графа v_s и v_t несвязными.

Для того, чтобы сделать две вершины v_s и v_tнесвязными, нужно либо нарушить все пути М_st, связывающие эти вершины, либо хотя бы одно из сечений s_st ε S_st, где S_st – множество сечений между вершинами v_s и v_t.

Между множеством путей М_st и множеством сечений S_st, а также множеством базисных разрезов существуют однозначные взаимосвязи.

Множество сечений S_st можно получить из дизъюнктивно-нормальной формы записи множества путей М_st, заменив знаки конъюнкции на знаки дизъюнкции и наоборот, используя булеву алгебру. Поскольку в булевой алгебре 1 U 1 = 1, то а.а = а; а U а = а; 1.а = а;

1 U а = 1; а(а U в) = а; а Uав = а; а. ā = 0; а U ā =1.

Например,

М₁₃ = b U ad Uce → S₁₃ = b.(a U d).(c U e).

Здесь U и (.) –знаки дизъюнкции и конъюнкции. Скобки удобнее раскрывать последовательно.

b(a U d) = (b a U b d)

(b a U b d)(cU e) = a b c U b c d U a b e U b d e = S₁₃

Аналогично из перечисления сечений S_st можно получить выражение для перечисления множества путей М_st, произведя замену знаков дизъюнкций и конъюнкций. S₁₃ =a b c U b c d U a b e U b d e → М₁₃ = (a U b U c).(b U c U d).(a U b U c).(b U d U c).(a U b U c).(b U c U d)= abUadUacU b UcbUcdU c = (adU b U c) посколку a Uab = a такие пары скобок дает: (a U b U e)(b U d U e) = abUadUacU b UbdUbcUacUbcU e = adU b U e окончательно получим:

(adU b U c)(adU b U e) = ad UabdUabeUabdU b U be U cad Uce = b U ad Uce = М₁₃.Запишем полученное множество сечений в форме матрицы:

	a e1	b e2	с e3	d e4	е e5

Запишем также матрицу базисных разрезов относительно остовного дерева{e₁, e₂, e₃}, полученную ранее

	e1	e2	e3	e4	e5
s1
s2
s3

Из соотношения матриц сечений и базисных разрезов видно, что:

S¹₁₃ = S₁ S₂ S₃ = S₄

S²₁₃ = S₂ S₃ = S₅

S³₁₃ = S₁ S₂ = S₆

S⁴₁₃ = S₂ = S₂

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

	e1	e2	e3	e4	e5
s1
s2
s3
s4
s5
s6

Как видно из графа G₁ на рис.21а, матрица охватывает все возможные разрезы этого графа.

Множество сечений S_st является подмножеством всех возможных сечений.

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

На основе логическной формы записи множества путей рассмотрен способ получения сечений и установлена взаимосвязь между множеством сечений и базисным множеством разрезов.

Как видно из графа G₁ на рис.1.21а, матрица охватывает все возможные разрезы этого графа.

Множество сечений S_st является подмножеством всех возможных сечений.

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