dln001

Множеством фундаментальных разрезов графа относительно некоторого остова T этого графа называют множество простых разрезов, каждый из которых содержит только одно ребро, принадлежащее T:

Из определения следует, что мощность множества фундаментальных разрезов не зависит от выбранного остова и равна ½=n¡1: Это коцикломатическое число графа. Такое название объясняется тем, что наряду с термином "фундаментальный разрез" используют и термин "коцикл", подчеркивая этим связь фундаментальных циклов и разрезов.

Описание фундаментальных разрезов удобно выполнять в виде матрицы S=[sij]; строки которой соответствуют разрезам, а столбцы ребрам, причем sij равно 1, если ej принад- лежит разрезу Si; или 0, если не принадлежит. Каноническая форма записи матрицы получается, если пронумеровать сна- чала все неостовные ребра, а затем остовные. Тогда матрица фундаментальных разрезов графа на рис. 5.5,а выглядит как

								S1					Js											e e e			e e e e e e
																						S1	2	11	02	03	04		15	06	07	08	09	3
						e1-										Je5					S =
		S2 -- -e6													ªJ							S3		0	1	1	1		0	0	1	0	0
										©												S2		1	1	1	0		0	1	0	0	0
	S3							J									J
			s s																			S4	6	0	1	0	0		0	0	0	1	0	7
	e2		- e3J e7															Je4
S4		--	-ª																JJ		S5	S5	6	0	0	0	1		0	0	0	0	1	7
										JJ													4											5
			·															º
					e8											e9
		s										às							s		Ðèñ. 5.5									á
íà ðèñ. 5.5,á,															или сокращенно							S=(S0jI½);					ãäå			I½		единич-

ная матрица порядка ½; определяющая, какое ребро остова принадлежит разрезу, а S0 матрица размера ½£º:

Установим связь матриц Φ è S: Число общих ребер любого цикла и любого разреза может быть только четным (в том числе и нулевым), а это значит, что количество единиц, стоящих на одинаковых позициях в строке i матрицы Φ è â ñòðî-

êå j матрицы S; четно. Следовательно, ΦST ´ 0	(mod 2):
С другой стороны, если принять во внимание	блочную

101

полуэйле-

структуру Φ è S; то, по правилам умножения блочных мат-
риц, можно записать					S T
ΦST =(IºjΦ0)(S0jI½)T =(IºjΦ0) Ã					0	!=IºS0T +Φ0I½=S0T +Φ0;
					I½T
ãäå Iº		è I½		единичные матрицы порядка º è ½ соответ-
ственно, а операции выполняются по модулю 2. Учитывая,
÷òî ΦST			´	0 (mod 2); имеем S0T +Φ0=0; откуда следует,
÷òî S0	T			так как сложение ведется по модулю 2.
		=Φ0;

5.2. Эйлеровы циклы

5.2.1. Определение и условия существования

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

	v1	v2		v1	v2
v6	@r	@r@	v5	r@ @r@		v5
	r@@@@ r			@@ r
	vr4	G1 vr3		vr4	G2 vr3

v1	v2
r@		r
@@
vr4	G3 vr3

Ðèñ. 5.6

Среди графов, представленных на рис. 5.6, граф G1 ÿâ- ляется эйлеровым, так как в нем есть цикл, содержащий все ребра, например, (v1; v2; v3; v4; v1; v3; v5; v2; v4; v6; v1); в графе G2 подобный цикл отсутствует, но есть эйлерова цепь, напри-

ìåð (v1; v2; v3; v4; v1; v3; v5; v2; v4); поэтому граф G2

ров; наконец, граф G3 не эйлеров и не полуэйлеров: в нем нет соответствующего цикла или цепи.

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

102

соединяли берега реки Прегель, а также два острова на ней, в соответствии со схемой, изображенной на рис. 5.6,a. Спрашивается, можно ли, выйдя из некоторого пункта в городе, вернуться обратно, пройдя один раз по каждому мосту?

				A r	PPPPPP
®	A	©®D	©	P		G
	B			B r		³³³³³rD
-	C à	ª-	ª	C ³³
				r		á
			Ðèñ. 5.7

Дадим графовое представление схемы на рис. 5.7,а, отобразив четыре участка суши A,B,C,D, разделенные рекой, че- тырьмя вершинами A; B; C; D; а семь мостов, связывающих

эти участки, семью ребрами мультиграфа G; как показано на рис. 5.7,б. При таком представлении задачу о кенигсбергских мостах можно сформулировать иначе: есть ли в графе G цикл, содержащий все его ребра? В данном случае ответ отрицателен в соответствии со следующей теоремой, носящей также имя Эйлера.

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

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

Достаточность. Пусть степени всех вершин графа G(V;E) четны. Такой граф является, по крайней мере, двусвязным и, следовательно, содержит цикл. Для построения цикла произвольно выберем одну из вершин. Пусть это будет v1: Перейдем по некоторому ребру в смежную вершину, пометив ребро как

103

использованное. Будем повторять эту операцию, каждый раз выбирая новое ребро, пока не окажемся в исходной вершине v1: Обозначим найденный цикл как C1: Åñëè C1 включает все ребра графа G; то это и будет требуемый эйлеров цикл.

В противном случае рассмотрим граф G1(V; E¡EC1); полу- чающийся при удалении из G всех ребер, относящихся к C1: Этот граф может быть как связным, так и несвязным, но любая его компонента в силу связности G имеет хотя бы одну

общую вершину с графом C1: Так как каждая вершина в G

è C1

имеет четную степень, то и в

G1 степени всех вершин

должны быть четными. Пусть v2

общая вершина G1

è C1; íå

являющаяся изолированной в графе G1: Найдем в G1

öèêë,

содержащий эту вершину, и обозначим его как

C2: Объеди-

ним циклы C1 è C2; как показано

íà

ðèñ. 5.8. Åñëè

öèêë

v1

s6

-

s@R@v2

s@R@

C1 = v1! : : : !v2! : : : !v1

C

C

C2 = v2

: : : v2

C2

1

2

s@I@ s

! !

v

: : :

v

: : :

v

s

s

s

C1[C2 = v

1! :C:10: !z

2

! }| !

{2!

C100

!

1

5.8

{z

}

|

{z

}

C1[C2

Ðèñ.

|

эйлеров, то процесс завершен. В противном случае

следует перейти к рассмотрению графа G2(V; E¡EC1¡EC2);

отыскать в нем цикл C3; который следует объединить с C1 è

C2 и т. д. Так как каждый раз количество неиспользованных

ребер уменьшается, то описанный процесс конечен и должен

закончиться построением эйлерова цикла. ¢

Аналогичная теорема для орграфов формулируется так:

Теорема 5.2

Связный ориентированный граф содержит

эйлеров орцикл (орцепь) тогда и только тогда, когда полу-

степени исхода и полустепени захода всех вершин удовле-

творяют условиям:

deg+ v = deg¡ v

8v 2 V в случае орцикла;

deg+ v = deg¡ v

8v 6= (u èëè w) è

deg+ u = deg¡ u+1;

deg¡ w = deg+ w+1 в случае орцепи,

ãäå u начальная, w конечная вершины цепи.

104

5.2.2. Алгоритм поиска эйлерова цикла

Существует очень простая и наглядная процедура отыскания эйлерова цикла, известная как алгоритм Флери, которая заключается в следующем. Начиная с некоторой вершины, произвольным образом "идем" по смежным ребрам графа, удаляя пройденное ребро и вершину, ставшую после удаления ребра изолированной. Не проходим по ребру, если после его удаления граф становится несвязным. Нетрудно показать, что процесс завершается после обхода (удаления) всех ребер, а значит, и вершин графа, и обязательно в исходной вершине, степень которой к этому моменту становится нулевой. Отметим, что каждая вершина (в отличие от ребер, проходимых однократно), вообще говоря, может быть пройдена неоднократно, точнее deg vi=2 раз. Порядок, в котором были пройдены ребра, определяет конфигурацию найденного цикла.

Пусть, например, требуется найти эйлеров цикл в графе, представленном на рис. 5.9,а. Непосредственной проверкой

v1

v2

v1 1-

v2

v1 -v2

r @

r

@

r6@R ¡ª

r @

¡

r6R@ ª¡

r

@

r

@

@

r

@5 2¡

@

¡µ

@

¡

@I

r

v3

@ r

@ r

v5

v3

@

¡ª r6R@

r

v5

v3

r @

¡ª¾ r

R@

¡?

v5

v4

@

4

3 v4

v4

@ @

¡@

@I

¡@

¡µ

vr6 a

vr7

vr6 á

vr7

vr

vr

6 â

7

Ðèñ. 5.9

убеждаемся, что степени всех вершин четны, т. е. граф эйлеров. В качестве начальной вершины выберем v1: На первой итерации перейдем в вершину v2 и удалим ребро fv1; v2g 18. На второй итерации перейдем в вершину v4 и удалим реб- ðî fv2; v4g; на третьей в v6; удалив fv4; v6g; затем вновь попадаем в v1; потом еще раз в v4 и, наконец, в v7 . Òî, что получится после этого, представлено на рис. 5.9,б. Вершина v4 оказалась изолированной и может быть удалена. Ребро fv7; v6g стало мостом. Поэтому допустим переход только в v2 èëè â v5: Перейдем в вершину v5; удалив ребро fv7; v5g;

18Удаленные ребра пронумерованы и отоображены тонкими линиями со стрелками, показывающими направление обхода.

105

v6; v1; v4; v7; v5; v2; v7; v6; v3; v1)

(v1; v2; v4;

как показано на рис.5.9,в. Теперь "остаток" графа простая цепь (v5; v2; v7; v6; v3; v1); следовательно, дальнейшие переходы определены однозначно. Окончательно получаем

эйлеров цикл.

Вышеописанная процедура поиска эйлерова цикла ориентирована главным образом на работу с изображением графа и идеально подходит для решения задач-головоломок типа "нарисовать граф (картинку), не отрывая карандаш от бумаги и не повторяя линий". Если же граф задан иначе, например в матричной форме, или в виде списка, то, чтобы установить, не является ли очередное выбираемое ребро мостом (не прибегая к изображению), требуются дополнительные операции. Поэтому для компьютерной реализации лучше подходит алгоритм, основанный на процедуре, использованной при доказательстве теоремы 5.1, в соответствии с которым первоначально найденный цикл последовательно расширяется за счет объединения с другими циклами, пока не будут задействованы все ребра. Формализованная запись алгоритма имеет вид:

begin	{ Ý É Ë Å Ð }
select v2V ;	{ Выбрать произвольную вершину }
v!S;	{ и занести в стек. }

while S6;= do { Пока стек не пуст, выполнять действия: }
8	6;{ находящейся в верхушке стека, не пусто, }
>	if (s1)=		select				{ если окружение вершины s1, }
							{ òî{}выбрать одну из ее }
>	8					2	{ "соседок" и занести в стек, }
>
>
>	>
>		8	!						{ а затем удалить }
>	> then		(s1) := (s1) u ;
>	>					u (s1);
>	>
>	>	>
>							¡f g{ пройденное ребро; }
>	>	<	(u) := (u) s1
<	>		u	S;
>	>
	>						¡f g
	>						{ иначе }
	<	>						{ получить из стека }
>		:
>				!
>	>		output(v) { и вывести очередную }
>
>	> else
>	>	(
>	>								{ вершину цикла. }
>	>		S		v;
>	>
>
>	>
>	>		{ Ý É Ë Å Ð }
end.	>
>	>
:	:

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

106

Рассмотрим работу алгоритма на примере. Пусть требуется найти эйлеров цикл для графа, изображенного на рис. 5.10 и заданного списками смежности. Фактически мы имеем муль-

	v2 s	v21	: v12		; v12	; v3; v4
v1 s	v3	v	:	v ; v
		v3	: v2		; v4
	s@
	@sv4	v4	:	v2	; v3

Ðèñ. 5.10

тиграф, поэтому списки для вершин

v1 è v2 содержат по-

вторяющиеся элементы, отражая наличие параллельных ре-

бер. Выберем в качестве начальной вершину v1

и занесем ее

в стек. Дальнейшие действия отражены в табл.

5.1 è 5.2.

Таблица 5.1

Èòå-

Ñòåê

SÃ

Удаляемоеребро

S!

Èòå-

Ñòåê

S!

ðà-

ðà-

öèÿ

öèÿ

1

v1

v2

fv1; v2g

¡

7

v1v2v3v4v2

v2

2

v1v2

v1

fv2; v1g

¡

8

v1v2v3v4

v4

3

v1v2v1

¡

¡

v1

9

v1v2v3

v3

4

v1v2

v3

fv2; v3g

¡

10

v1v2

v2

5

v1v2v3

v4

fv3; v4g

¡

11

v1

v1

6

v1v2v3v4

v2

fv4; v2g

¡

;

¡

Таблица 5.2

Èòå-

1

2

3

4

5

6

7

ðà-

öèÿ

v1 :

6v2; v2

6v2

;

;

;

;

;

v2 :

6v1; v1; v3; v4

6v1; v3; v4

v3; v4

6v3; v4

v4

6v4

;

v3 :

v2; v4

v2; v4

v2; v4

6v2; v4

6v4

;

;

v4 :

v2; v3

v2; v3

v2; v3

v2; v3

v2; 6v3

6v2

;

В табл. 5.1 представлены операции со стеком, а в табл. 5.2 показано, как изменяются списки вершин от итерации к итерации (столбцы) по мере удаления ребер.

Сначала в вершине стека находится v1: Поэтому в списке смежности для v1 произвольно выбираем некоторую верши-

107

Пусть это будет вершина

го списка смежности для

v2 v1:

ну (в данном случае это может быть только v2 ) и заносим ее в стек. Удаляем пройденное ребро fv1; v2g: Для этого из списка смежности для v1 исключаем вершину v2; а из списка смежности для v2 вершину v1: Теперь состояние стека соответствует второй строке табл. 5.1, а вид списка смежностивторому столбцу табл. 5.2. На второй итерации в вершине стека содержится v2: Теперь выбираем вершину из текуще-

(см. второй столбец табл. 5.2). Занесем ее в стек и удалим реб-

ðî fv2; v1g: В результате новое состояние стека соответствует третьей строке табл. 5.1, а вид списка смежности третьему столбцу табл. 5.2. На третьей итерации список смежности для вершины v1; находящейся в верхушке стека, оказался пустым. Выталкиваем ее из стека. Это означает, что в графе найден цикл, содержащий все ребра, инцидентные v1; но не являющийся эйлеровым.

На трех последующих итерациях в стек заносятся вершины v3; v4; v2; а из списков смежности удаляются все оставшиеся элементы. Таким образом, к началу седьмой итерации содержимое стека выглядит так: v1; v2; v3; v4; v2; причем вершине соответствует самый правый элемент v2: Так как все списки смежности теперь пусты, в течение последних пяти итераций (7 11) выполняется только выталкивание вершин из стека. Список всех вершин, выданных из стека (в порядке выдачи), имеет вид (v1;v2;v4;v3;v2;v1) и, как нетрудно заметить, соответствует эйлерову циклу данного графа.

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

5.2.3. О количестве эйлеровых графов

Задача определения числа эйлеровых графов является достаточно сложной. Рассмотрению этой, а также других задач пересчета и перечисления графов посвящена работа [4]. Здесь ограничимся теоремой, характеризующей долю эйлеровых графов в общем числе простых помеченных графов.

108

Теорема 5.3 Почти все графы не являются эйлеровыми.

¤ Пусть G(n) множество всех простых помеченных гра-

фов порядка n , à G÷(n) множество всех графов из G(n) , не имеющих вершин нечетной степени.

Любой граф из G÷(n) можно получить, добавляя к неко-

торому графу из G(n¡1) еще одну вершину и соединяя ее со всеми вершинами нечетной степени (если таковые имеются), поэтому jG÷(n)j<jG(n¡1)j . Так как множество эйлеро-

вых графов Gý(n) является подмножеством G÷(n) , запишем jGý(n)j<jG(n¡1)j . Разделив обе части неравенства на jG(n)j

и учитывая, что jG(n)j=2C(n;2) è jG(n¡1)j=2C(n¡1;2) , получим

jG

ý(n) =

(n)

j

< 2C(n¡1;2)¡C(n;2) . Упростив показатель степени

j jG

(n¡1)!

n!

(n¡1)(n¡2)

n(n¡1)

C(n¡1; 2)

¡ C(n; 2) =

¡

=

¡

=

2!(n¡3)!

2!(n¡2)!

2

2

=

¡

(n 1) , окочательно имеем, что

ý(n) =

(n)

j

< 2¡(n¡1) ,

¡

jG

j jG

а переходя к пределу при n!1 ,

nlim jGý(n)j=jG(n)j=0 . Ýòî

!1

значит, что при неограниченном увеличении числа вершин, в общем числе графов доля эйлеровых становится исчезающе малой, т. е. jGý(n)j = ojG(n)j . ¢

5.2.4. Задача почтальона

Пусть G связный граф, имеющий k вершин нечетной степени и заданный матрицей весов ребер. Требуется найти кратчайший замкнутый маршрут, проходящий по всем ребрам графа. В качестве приложений, где может потребоваться решение этой или сходной задачи, можно указать контроль различных коммуникационных сетей (дорожных, электрических, газовых и т. п.), когда необходимо проверять все протяженные компоненты сети. В литературе по теории графов сформулированная выше задача называется задачей почтальона. Последнему далеко не безразлично знание наиболее короткого замкнутого маршрута обхода всех улиц своего участка (или некоторого их подмножества). Аналогичная задача стоит и перед курьером большого учреждения, доставляющим документы от одного "источника" к различным получателям.

109

Покажем, как можно решить рассматриваемую задачу. Ясно, что в графе существуют k(k¡1)=2 кратчайших простых цепей, связывающих все пары вершин нечетной степени. Выберем из них k=2 цепей, таких, что

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

как на рис. 5.11, что противоречило бы пункту б. Действительно, если цепь (v1; : : : ; v2) имеет общее ребро e с цепью (v3; : : : ; v4); то, удалив это ребро, получим две цепи, связыва-

þùèõ v1 ñ v3					è v2		ñ v4;		суммарная длина которых меньше,
									чем у двух первых, на величину,
v1	s	s@				sHH v2
				e					равную удвоенному весу ребра
		@						s	e: Продублируем ребра всех вы-
v3	H	s				s H			бранных цепей в графе G: Â ðå-
	s H						s H v4		зультате получим эйлеров муль-
		s				s		s	тиграф G0; в котором нетрудно

Ðèñ. 5.11	найти эйлеров цикл. Этот цикл
и определяет искомый маршрут, отличаясь от него тем, что
вместо обхода двух параллельных ребер в графе G0 дважды

проходит по соответствующему ребру в графе G: Очевидно, что длина маршрута равна сумме длин ребер G0:

v1		v2					v3	v1	v2		v3
s@4 7 s				7		s		s@ s			s
6	@	1					3	@
	@				9			@
3 @ v5				5		sv6		@ v5			sv6
v4 s	2 @s				2			v4 s	@s
9	6	3	@				6			@
			@				vs9			@
					4@						@
vs7	4	vs8		3				vs7	vs8		vs9
		G							G0

Ðèñ. 5.12

Рассмотрим пример. Пусть требуется найти "маршрут по- чтальона" в графе G; изображенном на рис. 5.12 (веса ребер проставлены на рисунке). Имеются четыре вершины нечетной степени v1; v3; v7 è v9; из которых можно составить C42=6

110