Элементы теории графов

1 äî x.

Пошаго ое описание алгоритма:

. Полагаем

= 0,

1

o

Составляем мно

ество S всех

a

ka = 0 и для каждой другой вершиныxгра а x = 1; kx

2

= 0.

Среди всех вершин множества S ищем вершину y с минимальным

y = min x:

3o

x2S

Если y = b, то переходим к п. 6o.

пересчитываем харак-

4

Исключаем вершину y из множества S

теристики остальных из множества S

вершин, смежных y:

5

x = minf x; y + l(y; x)g

(x 2 S; fy; xg 2 U):

Ïåð õ äèì ê ï. 2o.

6o

Конец:

длина кратчайшего марш ута, а сам маршрут нахо-

11

дится поbпометкам kx предыдущих вершин: [a; : : : ; kkb ; kb; b .

Пример

чи на нахождение кратчайшего

маршрутзадав гра е и ее решения

Пример 6. В списк

ребер с их длинами каждый элемент есть упо-

ядоченная пара: ребро как множество двух смежных вершин и длина

ðåáðà:

26

31 73

43

, ({4,51 }, 2),9 ({4,8},1 5

1),8

({5,92 3}, 7),1 ({6,72 5}, 2),

(

21

62

({7,8},

3), ({8,9},

2)

).

A. Â

Дейкстры для каждой вершины x вводятся 2 ха-

ðàññòалгоритмеяние от начальной вершины (в условиях задачи 1) до x и

рактери

èêè:

ршруте от 1 до x.

k

номер предыдущей вершины на

Вx таблице выполнения

длякратчайшемномерааждого

âåðø íû çà-

водим 2 колонки для

алгоритмаk. Дадим пошаговое

описание

алгорèòìà:

51

2	o	0; k1		= 0 и для каждой другой вершины x гра а x																			= 1; kx = 0.
	o	Среди всех вершин множества S ищем вершину j с минимальным
3		Åñëè j								j		= min2S				i:
	o						конечной (последней в условиях задачи) вершины,
4		то перехномердим к п. 6o.							j из множества S и пересчитываем харак-
		Исключаем
		теристики				вершинуиз множества S, смежных														:
							= f ; + l g; k = j;
		где lji длина ребра fminj; g.									i			j		ji		i
5								i
		Ïåð õ äèì ê ï. 2o.
6o		Конец:			длина кратчайшего маршрута, а сам маршрут нахо-
		äèòñÿ поjпометкаì k предыдущих вершин: j; kj																			; kk	; : : : .
B. Сведем выполнение алгîритма в следующую таблj																						èöó.
		N		1 k		2 k		3 k		4 k			5 k				6 k 7 k 8 k 9 k
		1	0	0	1 0		1 0		1 0			1 0				1 0		1 0			1 0			1 0
		2			6	1	3	1	9	1		8			1				7	3
		3			4	3						6			2		2
		4							8	5						6								13		5
		5															2		7	3
		6							8	5											10		7
		7
		8																			9		4		11	8
		9
 ýòîé			аблице каждый столбец соответствует вершине гра а и двум
его характеристикам									k, каждая строк									таблицы соответствует
определению1 4 алгоритма, выбор вершиныарактеристикминимальной характеристикой
o		o			новых значений х							52						при выполнении шагов

помечаетсякунаглядноÌûопредеполучилиòèенияертойïðèминимумаíåîáдлинуíàäодимостиåå11номеромкратчайшего), исключениеýòè. характеристикимаршрутвершиныèçсносятсяèçâìíîæршиныестваñòðî1 Sâ

вершину 9. Начиная

9, определяем последовательность но-

меров предшествующихвершины

в найденном маршруте:

9; 8; 4; 5; 2; 3; 1:

Таким образом, кратчайший маршрут, соединяющий вершины 1 и 9:

а его длина

[1; 3; 2; 5; 4; 8; 9 ;

12

l( ) = l(1; 3) + l(3; 2) + l(2; 5) + l(5; 4) + l(4; 8) + l(8; 9) = 11:

Эйлеровы

Эйле овым маршрутомаршрутыгра е называется маршрут (цепь, цикл

том в оргра е называется ориентированный маршрут (путь, контур),

содержащий

все ребра

. Эйле овым ориентированным маршру-

âñå äóãè

. Критерий существования эйлеровой

цепи или цикла дает следующоргра ая тео ема.

Теорема об эйлеровом маршруте. Для того чтобы гра со

ä ðæàë ýé

ó öåïü,

статочно, чтобы он был свя-

ãðà ñîä ðæàë

ýéë

îâ öèêë,

обходимостепенидостаточно,

îí

Доказательство. Íåîáнеобходимо. Если

цепь есть,чтобыгра

çåí è èìå

ðîâно 2 вершины

÷åòí

. Для того чтобы

áûë ñâÿ åí

è íå

держал

вершин нечетной степени.

íîй степенью облаäàþò

ëüêдимостьначальнаяэйлероваи к ечная вершины цепи.

связен (любые его вершины связаны этой цепью или ее частью). Нечет-

÷èñ î

с нечетной степенью

равно 2. Если мультиг а

Поэтомудержит эйле вершинцикл,

то он связен и все его вершины имеют четн

ñòåïåíü (ïðè ï

õождении

скольк раз мы войдем в некоторóþ

его вершину,

ðîëüê

раз мыциклавыйдем из нее).

Достаточность. Доказательство проведем по индукции по числу ре-

áåð ãðà à.

53

åáåð m(G) =

меется ровно 2 вершины a и b, каждая из которых

ровымимеетВ случае,степень. когда2,

ãðà

имеетG связенцикл (имеетa; b; aровно), который2

являетсянечетнойýéëå

a è b,

ïðè

числе ребер m(G) = 1 утвержденвершинысправедли-

степениво, ак как это ребро fa; bg и эйлеров путь [a; b , а

ïðè

числе ребер

m(G) = 2 утверждение такж

справедливо,

ак как есть эйлеров путь

[a; ; b , где вершина, имåющая степень 2.

Таким

индукции имеет место.

Пусть теперь утверждеоснование

т оремы справедливо для любого связ-

m(G) kобразом,где имеющегоk > 1, докажем, что оно справедливо при m(G) =

íîãî ãðà à G

íå

более двух вершин нечетной степени, и

k + 1. Пусть сначала гра G имеет

овно две вершины

ñòå-

åíè.

èç

вершины a

слови мнечетнойпрох дить

ïî

Отправимодному путешественникдваждыж ребру

. Åñëè

путешеств

ïðèø ë â

x =6

томуb, при x = a количество пройденных ребер, инцид нт-

пройденных ребер,

õ

x, нечетно (число

путешественниквх дов верши

ных a, четно ( исло вых дов из вершины a равно числу входов

âûéòè

èç a ïî åùå

непройден

ому ребру, а если x =6 a, то оличество

åðø íó)

è íå÷етная степень вершины a позволяет

ïî

ýòó

в ршины x

инцидентнакж выйти

из этойвершины)

еще непрой

ну x на 1 больше числа вых дов

ýòîé

четная степень

д нному

бру. Если невозможноиздти дальше (все ребра, инцидент-

íûå вершине,позволяетуж пр йдены), то это в ршина b. Цепь, пройденную

утешественн ком,

значим через [a; : : :; b .

Однако прè

этом могут быть еще 0непройденные ребра гра а. В

подгра е G0 ,

образованíîì ó

пройденных ребер, все верши-

ны имеют уже четную степеньдалениемчисло его ребер m(G

) < k. Пусть

C ; : : : ; C

0

p

компоненты связности G0 , содержащие хотя бы 1 реб о.

åñòü

i

циклы ; : : :; . Так как G связен, то це

ü

встре-

1

Так как m(C ) < k (i 2 1; k, то по предположению индукции для них

÷àåò

ее прох ждении все подгра ы C ; : : : ; C .

Допустим, что

это проэйлеровыприсх дит в верш

1

íàõ x

p

2 C ; : : : ; x

2 C . Обозначим через

0[x; : : :; y отрезок

0

цепи 0 от вершины x до вершины y. ассмотрим

1

1

1

p

p

54

p

[a; : : : ; x

+

1

+

[x

; : : : ; x

+

2

+ +

p

+

[x

; : : :; b :

0

1

0

1

2

0

p

Это и есть эйлерова цепь гра а G, которую необх димо было постро-

Пусть теперь

G не имеет вершин

нечетной степени. Тогда,

èòü.

мы тольк чтсо доказали,

ровно 2 вершины н четной с епениполучимa b.

удалив любое его грабро fa; bg,

û

связный гра ,

держащий

он имеет

эйлерову öåïü, à ïîòому, добавивКакэтой цепи удаленное ребро

fa; bg, мы получим эйлеров цикл гра а, что

требовалось. Теорема

Замеч ние. Теорема очевидным образом

переносится на мульти-

доказана.

орого может быть более одного

ãðà

(ãðà , между вершинами к

äâóõ, ïî

исхода былаориентированнавна полустепени захода, для одной

ребра).

м маршруте.

Теорема об эйлер вом

1. Для того чтобы îргра содержал эйлерîв путь, необходимо и

остаточно, чтобы он был слабо связен

для всех вершин, кроме

лустепеньпо

ь исхода была на 1 больше полустепени захода

вершиныдля другой вершиíы полустепень исхода была на 1 меньше полу-

захода.

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

степенидостаточно,

чтобы îí áûë

2. Äëÿ òîãî

ргра содержал эйлеров контур, необходимо

степень исхода была авна полустепени

.

Äîê

ýòîé òå ðåìû

казательству предыду

щей для неориентированн го гра а. авенствзаходаполустепеней исх да и

çàõ äà äëÿ åõ

двух,аналогичноарантирует,

выйдя из вер

øèíû

епенью исхкромеда большей

захода, мы можем

остановитьсазательствоя ольквершин,вершине

полустепенью захчто,да большей полу-

степени полуисх да,

àê

ак полустепени исхполустепенида захода всех остальных

алгоритмаотысканияэйлерова

маршрутака,

àê îíî ñîäå æèò

вершин

àâíû.

эйлерова

.

äî

Алгоритм

Введем понятие перешейка гра индукцииа, оторое необхКонструкциюдимо для описа-

казате ьства теорем нельзя использовать для построения э ктив-

íогоек

нструктивное

предположение

.

55

ребраäèò , а другойдругую(в

называется ребро, удаление которого

ãðàäнугойà:компонентуíåòконецмаршрутребра)связности.из дногопопадаетконца уäèíаленногоконец

дитПерешейко

оргра е называется дуга, у аление которой приво

гра а: из вершины конца äуги нет ориентирован-

ного маршрутнесвязностиее начало.

маршрута.

1

0Опишем алгоритм

построения

: Вых дим из начальной в ршиныэйлерова

от вида маршру-

та: при цикле или контуре из

çвольнойависимостиршины, при

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

больше

полустецепиутиен

èç

вершины нечетной степени, при ори нтированном

20:

захлюбойда. Все ребра (дуги)

аем непомеченными.

аемся из вершины п

ñ÷èò

маршруте по лю

ðиентированном маршрутенеориентированномпомечаемлюбой исх дящей из вершины

áîìó

îìó

ðó

являющемуся перешейком

ïîä-

Двига енепомеченных ðåáåð,

пройденное ребро,

ïðè

îé

не являющейся перешейком в подгра е из

непомеченных

ге, помечаем ее.

30: Повторя м пре ыдущий

пункт до тех пор, пока не придем в вер

шину, все инциде тные

ðåá à

хо ящие дуги) которой уже по-

мечены.

íûé ìàðøðут(исбудет

.

Для обосновПолученя алгоритма нужно показать, что при

à 2

èç äîñòèгнутой вершины вс да естьэйлеровымнеп меченное исх дя-

щее ребро (дуга),

íå

ÿ

перешейком, если эта выполнениивершина

0

30

алгоритма. Действительно, гра

пунктдовлетворяет

р вом маршруте,словиямэйлерявляющеесшру

этого гра а как раз вых дит из

из непомеченных ребер (дуг)пунктедовле воряет условиям теорем об эйле

äîстигнутой вершины. Поэтому

существуåò âûõ

дящее

èç ýòîé âåð

шины ребро (дуга) этого маршрута,

оторое не

перешейком.

Приведем теперь п

ребостой

алгоритм, позволяющий опред лить, яв

ляется ли выбранное

. Для этогоявляетсгра е из непо

меченных ребер будем определятьперешейкомпоненту свя ности другой вер-

шины ребра (дуги), включая в нее эту вершину, затем

смежные ей

56

äîíûåòåõèìïîð,вершиныïîê ëèáîïî непомеченнымбудет включенаребрамдругая(исх дящимвершинадугам)выбранного. ä.

остановитсяребра (дуги),

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

(дуги). В первом

случае выбранное ребро не является перешейком,ребра

во втором случае

является.

13

Примеры з дач на нахо

эйлерова мàршрута в граждениее их решений

Пример 7.

2

1

101

3

4

10

5

011

00

6

100

100

7

поэтому гра не

Ма рица смежности вершин гра а

орие тированный. ра содержит 6 вершин

7 ребер. Для анализа

вязности гра а образу

компоненту симметрична,связности C содержащую вер-

øèíó 1,

включим

íåе эту вершину: C = f1g. Вершина 1 смеж

ñ вершинами

3, 4, 6.

эти вершины: C = f1; 3; 4; 6g. Вершиíà

3 смежна с вершинамиДобавим1, 2 5. Доб вим их: C

= f1; 2; 3; 4; 5; 6g. Òàê

1

1

1

1связен.

к C содержит все вершины гра , то гра

аждоймо

строксодåðжать эйлеров цикл (все вершины для этого долж ы

1

ê

Определяем степени вершин ãðà à по матрице (число единиц в

å): d

1

= 3; d

2

= 2; d

3

= 3;

d

4

= 2;

d

5

= 2; d

6

= 2.

содер

èò 4 â

øèíû

степени и 2

. Поэтому гðà

иметь четную степень),четнойсодержит эйлеровунечетнойцепь, ак как выполíå

ны условия

эйлеровой цепи:

Опишем алгоритмсуществованиянах ждения эйлеровой цепи. Для этого все ребра

Для того чтобы гра сод ржал эйлерову цепь, необходимо и доста-

точно, чтобы он был связ

содержал ровно две вершины нечетной

степени.

57

â 1маршрутниВыбираем(длябудемопределв делачественностиь пометкиначальнойберемсоответствующихвершинулюбую вершинус меньшимребернечетной.номером)степеи-

2

o

делаем ее

текущей.

o

Åñëè èç

вершины нет н п ойденных (непомеченных) ре-

ребро, ведущтекущей

в ршину с

.

o

бер, то алгоритм закончен: все рåáðа пройдены и цепь составляем

3

в порядк

их прохождения.

Из текущей ршины выбираем любое ребро (для определенности

4

Åñëè îíî

является перешейконаименьшим(из екущ й

åñòü

еще непрой енные ребра, а при временнойномером)пом тквершиныд нного реб

ра гра непомеченных

ребер не со

жит маршрут из т кущей

вершины в другую вершину данногодеребра), то

выбираем го, по-

мечаем и делаем текущей вершину смежную

о этому

ребру ñ

5o

предыдущей смежной вершиной. Перех дим к

ï. 2o.

Åñëè

íà предыдущем шаге

ребро является пер шей

íû,

выбранïåð õ äèìíîå ê ï. 4 .

ком, то выбира м следующее ребро, ведущее из текущей верши-

o

Выполнение алгоритмà ñâîäèì â ñëедующуþ òàáëèöó.

N

f1; 3g

f1; 4g

f1; 6g

f2; 3g

f2; 5g

f3; 5g

f4; 6g

I

0

1

1

+

+

4

2

+

6

3

+

1

4

+

3

5

+

2

6

+

5

7

столб ц

(кроме

первого

3

Каждый

отвечает ребру

ãðà à.

номер шага

выполнения алгоритма,последнего)а в рвомдне номер

текущей

Для пометки р бра ставим над

ним черту. В

столбце о меча м

58

ставимïåðå å÷åíìèí

текущейс. В противномстроки выполненияслучае ставималгоритмаплюс, помечаемстолбцареброребраè

заносим новую

вершину.

По окончании ал оритма столбец текущей верши ы определит эй

ë îâó öåïü. Íà øàã

1 выполнения алгоритма ребро {1,3} является

ïåðешейком, тактекущуюак после его временного

íå ñóùå

âó-

ет маршрута, связ вающего вершины 1

3:исключенияомпонента связнос

è â

ãðà å

ïîì ÷åí ûõ

ребер, содержащ я вершину 1, содержит акже

межны

ñ íåй вершины 4

6, но никаких

других вершин (в частно-

ñòè, вершины 3)

не содержит.

В результате выполнения алгоритма получена следующая эйлерова

öåïü:

(1; 4; 6; 1; 3; 2; 5; 3):

0 3

Пример 8. 2

1

1

0

6

1

0

0

1

1

1

7

0

1

0

0

4

0

0

0

5

Матрица смеж

1

0

1 1

1

и вершин кососимметрична, поэтому это оргра .

Определяем

ь гра а как неориентированного. Включаем в

компоненту

C

1

вершину 1: C

1

= f1g. Вершине 1 смеж-

вершинысвязности3 5, добавляем их: C

1

= f1; 3; 5g. Вершинам 3 и 5

=

смежны вершины 6, 7, 8. Добавляем их в компоненту связности: C

f1; 3; 5; 6; 7; 8g. Вершинам 6 и 8 смежны вершины 2 и 4.

1èõ

компоне ту связности: C

1

= f1; 2; 3; 4; 5; 6; 7; 8g. ПоскДобавляемк по

гра а, он связенолькуак неори

нент связности содержит все

	.
ентированныйНах дим полустепени исходавершинызахода для каждой вершины и срав-
ниваем их:		59

32			2		2	2		2	2		2
4			3		1	3		1	3		3
5			4		2	4		2	4		4
6			5			5			5		5
7			6	=	1	6		1	6		6
8. d					2; d+ =			2 ! d = d+
			7			7			7		7
Èç			8			8			8		8			è
				что о гра слабо связен (связен как неори
ля каждой веðшины полустепень исх да и полустепеíьтированный)зах да совпа
äаюттого,следует, что												жит эйлеров		так как выпол
Äëÿ òîãî							оргроргра					эйлеров контур,необходимо и до
									хсодержалждения эйлерова к					. Для этого все
нены условия существования эйлерова контура:
	аточно,чтобы он был										ëàáî		для каждой вершины полу-
ñòепени исхода										были бысвязенрав .
дуги в началеалгоритмзахода считаем непомеченными,онтурапо мере их вклю-
			íè (äëÿ			определенности берем вершину вершину1)								ее текущей.
ченОпишемя в маршрут бу									ì делать пометки соответствующих дуг.
1		o	Выбираем в кач стве начальной любую											неч тной степе-
2o					из текущей						ны нет непройденных делаем(непо ченных) вы-
3o			х дящих дуг,						алгор тм зак нчен: все дуги пройдены и контур
			Из текущей					вершины			выбираем любую непомеченную выходя
			Åñëèîставляем в пто						ÿäê		èõ ïðîõîждения.
		o	ùóþ äóãó (äëÿ						пределенности дугу, ведущую в вершину с наи-
4			меньшим номерîì).							пер шейком (из текущей вершины есть еще
			Åñëè îíà				являетс
			непройденные вых дящие дуги, а при временной пометке
			дуги из ее конечной							вершины не существует пути до текущеданной
												60