dln001

2. Связность в орграфах

2.1. Основные понятия

Говорят, что вершина w достижима из вершины v; если существует путь (v; : : :; w): Åñëè ïðè ýòîì v достижима из w; то о вершинах говорят, что они взаимно достижимы.

Орграф называется сильно связным или сильным, если любые две вершины в нем взаимно достижимы. Пример сильного орграфа приведен на рис. 2.1,a. Поскольку в графе имеется орцикл (v1; v4; v2; v3; v5; v1); включающий все вершины, то любые две из них взаимно достижимы.

	v1					v1
>s}ZZ-Z
				v5 sB	>sBZZZ~
v5 sQkQ		3sv2				BB -sv2
				B		BBN
	Q			BN	+
			Qsv3			-sv3
v4 s				v4 s

à	á
	Ðèñ. 2.1

	v1
v5 sB	>sZBMB ZZ~
	BB	-sv2
BBN	+	Bsv3
v4 s â

Орграф называется односторонне связным или односторонним, если в любой паре его вершин хотя бы одна достижима из другой. Пример одностороннего графа дан на рис. 2.1,б. В этом графе есть орцикл (v1; v3; v4; v1; v2; v1); включающий четыре вершины. Все они взаимно достижимы. В отличие от этих вершин v5 имеет нулевую полустепень захода, а это зна- чит, что не существует путей, ведущих в v5: Вместе с тем из v5 достижима любая из четырех остальных вершин.

Орграф называется слабо связным или слабым, если в нем любые две вершины соединены полупутем. В отличие от пути, когда все дуги одинаково ориентированы (от начальной вершины пути к конечной) в полупути могут быть и противоположно направленные дуги. Пример слабо связного орграфа приведен на рис. 2.1,в. Очевидно, что в графе нет пути между вершинами v3 è v5; но существует полупуть, состоящий из двух противоположно направленных дуг (v3; v4) è (v5; v4):

31

2.2. Компоненты связности

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

Понятие сильной компоненты иллюстрирует рис. 2.2. Граф

G1 vs1 -vs2

6

G s ?s v4 v3

vs1 -vs2

6

s v4

G01

						G
v1			-	v2			v6
	s6				sHYHH			s@@R v7
					? vs5@I@			? s
	s4		vs3				vs8
v
v1			v2				v6
	s6		-		s	v	s@R@ v
					?	5	s@I@ s		7
vs4			vs3				vs8
			G100				G20

G2 vs6

@

v5 s @Rsv7

I@ @?s v8

vs6

v5 s

I@ ? @vs8

G002

Ðèñ. 2.2

G , который является односторонне связным, содержит шесть

сильных подграфов G1; G01; G001; G2; G02; G002; из которых только два G1 è G2 являются сильными компонентами.

Аналогично иллюстрируется понятие односторонней компоненты. В рассматриваемом случае оносторонняя компонента совпадает с самим графом. Если же сменить, например, ориентацию дуги (v4; v1) на противоположную, то получим слабосвязный граф с двумя односторонними компонентами, одна из которых образована вершинами v1 v4; а другая вершинами v2 v8: Как показывает этот пример, односторонние компоненты графа в отличие от сильных могут иметь общие вершины.

Слабая компонента эквивалентна компоненте связности. Подобно сильным компонентам слабые компоненты не могут иметь общих вершин.

32

2(v)

не может содержать цик-

2.3. Конденсация орграфа

На основе сильных компонент определяется еще один вид

графов граф конденсации. Пусть S1; S2; : : : ; Sk сильные

компоненты графа G(V; E): Конденсацией графа G называ-

åòñÿ ãðàô G¤(V ¤; E¤); каждая вершина которого vi¤

представ-

ляет множество вершин соответствующей сильной компонен-

òû Si графа G; à äóãà (vi¤; vj¤) является элементом множества

E¤; если в графе G есть по крайней мере одна дуга, идущая

от некоторой вершины компоненты Si к одной из вершин ком-

поненты Sj: Пример орграфа G; имеющего четыре сильных

компоненты S1 S4; и его конденсации G¤

äàí íà ðèñ. 2.3.

v1

sI

v2

v3

v ;v

v

=S

-

s@ s@

S1=vf1¤

1 2g

f

3vg2¤

2

@

@

s@

s

?

@ v6

@ v7

@

G v

?

@R

s6

@R

G¤

-

-

@@

4

s6@ vs5

s

v¤

@

?

@R?v¤

@@Rv

Rv

3

4

v

S3=fv4;v5s;v8;v9g fv6;vs7;v10g=S4

8 s

s9

s10

Ðèñ. 2.3

Ясно, что граф конденсации G¤

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

2.4. Отыскание сильных компонент

Пусть R(v) множество вершин (n; m) -графа, достижимых из вершины v: Тогда, поскольку (v) является множеством вершин, достижимых из v с использованием путей длины 1, множеством вершин, достижимых из v с использованием путей длины 2, 3(v) с использованием путей длины 3 и т. д., то R(v) можно представить в виде

R(v) = fvg [ (v) [ 2(v) [ : : : [ p(v) :

33

В том случае, когда

Операции объединения выполняются последовательно слева направо до тех пор, пока множество R(v) не перестанет увеличиваться. Количество операций зависит от графа, но, очевидно, что p<n .

Обобщая, можно говорить о множестве вершин R(X); достижимых (в совокупности) не из единственной вершины, а из целой группы вершин X½V;[и определять R(X) êàê

R(X) = R(v) :

v2X

Пусть Q(v) множество вершин (n; m)-графа, из которых достигается вершина v: Тогда, поскольку ¡1(v) ìíî-

жество вершин, из которых v достигается с использованием путей длины 1, ¡2(v) множество вершин, из которых v

достигается с использованием путей длины 2, ¡3(v) ñ èñ-

пользованием путей длины 3 и т. д., то Q(v) можно представить в виде

Q(v) = fvg [ ¡1(v) [ ¡2(v) [ : : : [ ¡p(v) :

Здесь операции объединения выполняются, как и в предыдущем случае, последовательно слева направо до тех пор, пока множество Q(v) не перестанет увеличиваться, а число этих

операций p<n .

В качестве объекта, достижимого из других вершин, можно рассматривать не единственную вершину, а целую группу вершин X½V: Тогда получаем множество

[

Q(X) = Q(v) :

v2X

Åñëè R(v) это множество вершин, достижимых из v; à Q(w) множество вершин, из которых достижима w; òî R(v) \ Q(w) является множеством вершин, принадлежащих всем путям, идущим из v â w: v=w; ïå-

ресечение R(v)\Q(v) определяет множество (включая v ) взаимно достижимых вершин и, следовательно, некоторую сильную компоненту графа.

34

множество вершин первой

С учетом изложенного, можно предложить следующую процедуру отыскания всех сильных компонент графа G(V; ) :

1.Формируем описание графа в виде +(vi) è ¡(vi) äëÿ âñåõ vi 2 V:

2.Выбираем некоторую вершину v и находим R(v) è Q(v):

3.Получаем V S = R(v) \ Q(v): Вершинно-порожденный

на множестве вершин V S подграф графа G представляет сильную компоненту.

4.Если множество V ¡VS пусто, то все сильные компо-

ненты найдены, в противном случае строим вершиннопорожденный подграф на V ¡VS и переходим к п. 1.

Разберем пример на использование описанного подхода. Найдем сильные компоненты графа, изображенного на рис. 2.4.

v1		-v2		-Rv3
	r6JJ r			r
	J			?
		J^
		vr		-vr
	vr6		5		4

Ðèñ 2.4

Описания графа с использованием прямого и обратного отображений выглядят так:

(v1) = fv2; v3; v5g,						(v2) = fv3g,
(v4) = fv3g,						(v5) = fv4; v6g,
¡1(v	) =	f	v	6g	,	¡1(v		) = v	; v	6g	,
1 1						1	2	f 1
¡ (v4) = fv3; v5g,						¡	(v5) = fv1g,

(v3) = fv4g,(v6) = fv1; v2g;

¡1(v3) = fv1; v2; v4g,

¡1(v6) = fv5g.

Находим множества R(v); Q(v) è R(v) \ Q(v) для произвольно выбранной вершины, например для v1 :

R(v1) = fv1g [ fv2; v3; v5g [ fv3; v4; v6g = fv1; v2; v3; v4; v5; v6g; Q(v1) = fv1g [ fv6g [ fv5g = fv1; v5; v6g;

VS1 = R(v1)\Q(v1) = fv1; v5; v6g

сильной компоненты графа.

35

вершины третьей и последней

Множество вершин, не относящихся к найденной сильной компоненте, равно разности V ¡VS1=fv2; v3; v4g: Описание соответствующего вершинно-порожденного подграфа имеет вид:

(v

) =

f

v

3g

,

(

v

) = v

,

(v

) =

f

v

3g

;

12

13

f 4g

14

¡ (v2) = ;,

¡ (v3) = fv2g,

¡ (v4) = fv3g,

Для поиска следующей сильной компоненты возьмем одну из его вершин, например v2 . В результате получим:

R(v2) = fv2g [ fv3g [ fv4g = fv2; v3; v4g; Q(v2) = fv2g;

VS2 = R(v2) \ Q(v2) = fv2g единственная вершина, входящая во вторую сильную компоненту.

Далее ведем поиск на множестве V ¡VS1¡VS2=fv3; v4g: В результате получаем:

R(v3) = fv3g [ fv4g = fv3; v4g; Q(v3) = fv3g [ fv4g = fv3; v4g; VS3 = R(v3)\Q(v3) = fv3; v4g

сильной компоненты графа.

2.5. Матрицы достижимостей

Определим матрицу (прямых) достижимостей R = [rij]

как квадратную (0,1)-матрицу порядка jGj; в которой rij=1; если вершина vj достижима из vi; è rij=0 в противном случае. Поскольку каждая вершина достижима из самой себя, диагональные элементы в R равны 1.

Матрица достижимостей может быть получена следующим способом. Отыскиваем множества R(vi) для всех вершин гра-

фа и полагаем rij=1; åñëè vj2R(vi); è rij=0 в противном
случае. Для примера из предыдущего раздела имеем:															0
R(v2) = fv2			; v3		;	4g			; v6g;		9			0 1 1 1 0
R(v1) = fv1			; v2	; v3			; v4	; v5			>	= R = 2		1 1 1 1 1	1	3 .
3	f 3		4g		;									0 0 1 1 0	0
R(v4) = v3; v4											>	)		10 10 11 11 10	10
R(v ) = v ; v ; v ;											>
R(v ) = v ; v ; v ; v ; v ; v ;											=		6			7
	f			g							>		6			7
	f							; v5		g	>		6	1 1 1 1 1	1	7
R(v6) = fv1; v2; v3; v4									; v6g;				4			5
											>		6			7
											>
											>
5		1	2			3	4	5	6		;

36

Матрицу обратных достижимостей Q=[qij] определим

как квадратную (0,1)-матрицу порядка jGj , в которой qij=1; если вершина vi достижима из vj; è qij=0 в противном случае. Диагональные элементы в Q; êàê è â R; равны 1.

Матрица Q может быть получена тем же способом, что и

матрица R: Ищем множества Q(vi) для всех вершин графа и полагаем qij=1; åñëè vj2Q(vi); è qij=0 в противном случае:

Q(v2) = fv1				; v2		; v5		; v6;gv ; v ;			9			1	1	0	0	1	1
Q(v1) = fv1				; v5		; v6g;					>	= Q = 2		1	0	0	0	1	1	3 .
	3	f 1 2 3 4 5 6g												1	1	1	1	1	1
Q(v4) = v1				; v2; v3; v4; v5; v6 ;							>	)		11	01	01	01	11	11
Q(v ) = v ; v ; v ; v ;											>
											>		6							7
		f								g
Q(v	5	) = v	1	; v	5	; v	6		;		=		6							7
		f						g					6	1	0	0	0	1	1	7
											>		6							7
Q(v6) = fv1				; v5; v6g;							>		4							5
											>
Однако из определений										ÿñíî,>		что столбец			в матрице					Q
											;			vi
совпадает со строкой vi в матрице R; поэтому Q = RT .

Процедура отыскания сильных компонент может быть сделана более наглядной и эффективной, если использовать введенные выше матрицы и операцию их поэлементного умножения - . Матрица R-Q несет информацию обо всех сильных компонентах графа:

v3		v1 v2 v3 v4 v5 v6						3		v6 2			v1 v5 v6 v2 v3 v4						3
	2 0		1	0	0	0	0						1	1	1	0	0	0
v1		1	0	0	0	1	1			v1			1	1	1	0	0	0
v2	6							7		v5	6								7
R-Q = v4									»	v2										:
		10	00	01	01	10	10						0	0	0	1	0	0
										v3			0	0	0	0
v5	6	0	0	1	1	0	0	7			6						0	0	7
v6	6	1	0	0	0	1	1	7		v4	6		0	0	0	0	1	1	7
	6							7			6						1 1		7
	4							5			4								5

Действительно, строка vi содержит единицы в тех столбцах vj , для которых выполняется условие взаимной достижимости с vi и которые наряду с vi входят в состав одной и той же сильной компоненты. Ясно, что строки (и столбцы) матрицы, соответствующие вершинам одной и той же сильной компоненты, должны быть идентичны. Поэтому путем перестановки строк и столбцов матрицу R-Q можно привести к блочно-диагональному виду, когда каждая диагональная под-

37

R1=A+I;

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

2.6. Получение матрицы достижимостей

Естественными количественными характеристиками достижимости являются длины путей между вершинами При этом матрицу смежности A можно трактовать как матрицу дости-

жимости при длине путей 1, а матрицу A2=A£A=[a(2)ij ]; ãäå a(2)ij =Wn aikakj; как матрицу достижимости при длине путей 2

k=1

(здесь и далее матрица A рассматривается как булевская).

Соответственно матрицы A3; A4; A5 и т. д. можно рассматри- вать как матрицы достижимости при длине путей 3, 4, 5 и т. д.

Определим ограниченную достижимость как достижимость при длине путей не более чем q: Соответствующая мат-

рица называется матрицей ограниченной достижимости Rq: Очевидно, что где ”+” булевское сложение,

I единичная матрица, аналогично R2=R1+A2=I+A+A2=

=(I+A)2=R21 и вообще Rq=I+A+A2+ : : : +Aq=(I+A)q=Rq1:

Вместо последовательного вычисления R2; R3; : : : ; Rq эконо-

мичнее получать R2; R4; R8 и т. д., используя соотношение:

R21l =R21(l¡1) R21(l¡1) ;

ãäå l=1; 2; 3; : : : Возведение в квадрат повторяется, пока не

будет получено Rq: Åñëè q не является степенью двойки, потребуется ряд дополнительных умножений. Например, матрица R7 может быть получена так: R7 = R4£R2£R1 = = R41£R21£R1: В том случае, когда требуется отыскать матрицу достижимости, возведение в квадрат следует выполнять, пока результат операции не перестанет изменяться.

Более эффективное решение задачи основано на использовании транзитивного замыкания. Граф называется транзитивным, если при наличии дуг вида (vi; vk) è (vk; vj) â íåì

обязательно есть и дуга вида (vi; vj): Пример транзитивного графа дан на рис. 2.5. Транзитивным замыканием графа G

38

называют транзитивный граф Gtc, полученный путем добав-
ления к G минимального количества дуг, необходимого для
обеспечения транзитивности. Из опре-								v1
деления следует, что если в транзитив-						>sBZ}Z
ном графе имеется цепь, связывающая							B		Z
вершину v с вершиной w , то существу-					v5 sBQQ			B sv2
ет также и дуга	(v; w):		Поэтому, ес-		B	Q B
							Q
ëè Gtc является графом транзитивно-					BN + QsBN
					v4	k		- v3
го замыкания графа		G;	то его матри-		¶³ ¶³
					- s				s-
ца смежности практически совпадает				ñ	µ´ µ´
матрицей достижимости графа G; îò-					Ðèñ. 2.5
личаясь только элементами главной диагонали, соответству-
ющими одновершинным сильным компонентам6								G: Следова-
тельно, для нахождения			R можно использовать алгоритмы
отыскания транзитивного замыкания. Рассмотрим один из та-
ких алгоритмов.

2.7. Алгоритм Уоршолла

Пусть G0 орграф с множеством вершин v1; v2; : : : ; vn: Алгоритм Уоршолла позволяет получить последовательность графов Gi , i=1; 2; : : :; n , таких, что Gi¡1 является подгра- ôîì Gi , причем Gn это граф транзитивного замыкания G0 .

Ãðàô Gi			получается из Gi¡1					после обработки вершины vi â
соответствии со схемой, представленной на рис. 2.6.
vj1				-		vk1	Пусть,			например, в графе Gi¡1
							существуют дуги (v 1; vi) è (vj2; vi);
	sZZZ			>s
							входящие			в вершинуj	vi; è äóãè
			Z~				(v ; v 1)		è	(vi; vk2); выходящие из
		>vsZi ZZ					íåå.i	kТогда при обработке вершины
				Z~W
				-		svk2	v каждая пара дуг (одна входящая,
vj2 s							другаяi		исходящая) "порождает" тре-
			Ðèñ. 2.6				тью дугу, которая соединяет начало
							первой дуги пары с концом второй
дуги. В представленный на рисунке граф добавляются четы-
ðå äóãè (vj1; vk1) , (vj1; vk2) , (vj2; vk1)										è (vj2; vk2);	изображеные

6В матрице смежности графа Gtc эти элементы равны нулю.

39

пунктиром. Граф, полученный в результате подобной обработки вершины vi; обозначается Gi:

Дадим формальное описание алгоритма. Пусть A ìàò-

рица смежности графа, A¤ = [aji] матрица смежности транзитивного замыкания. Тогда запись алгоритма выглядит так:

begin		{ Ó Î Ð Ø Î Ë Ë }
A¤ := A			{ Инициализация A¤
for i := 1 to n do			{ Перебор столбцов в A¤
	for j := 1 to n do		{ Перебор строк в A¤
	if aji¤ = 1 then		{ Åñëè åñòü äóãà (vj; vi), òî
		for k := 1 to n do	{ "прибавить" в A¤
end		ajk¤ := ajk¤ _ aik¤	{ строку i к строке j
		{ Ó Î Ð Ø Î Ë Ë }

}

}

}

}

}

}

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

Как следует из приведенного описания, алгоритм обеспе- чивает получение транзитивного замыкания всего за один проход (просмотр) вершин графа. Существенным достоинством является и то, что результат формируется путем преобразо- вания элементов матрицы A¤ без использования вспомогательных данных, т. е. алгоритм "работает на месте".

v1		-	v2		v1 v2 v3 v4						v1 v2 v3 v4
G	s		s	A= v22	0	0	0	1	3	R= v22	0	1	1	1	3
				v1	0	1	0	0		v1	1	1	1	1
	-			v46	0	0	1	0	7	v46	0	0	1	1	7
v4			v3	4	0	0	0	0	5	4	0	0	1	0	5
	s		s	v3						v3

Ðèñ. 2.7

В качестве примера найдем транзитивное замыкание для графа G с матрицей смежности A и матрицей достижи-

мости7 R; представленных на рис 2.7. Применяя алгоритм

7Матрица достижимости легко получается непосредственно по графу.

40