Учебное пособие 800365

2.8.Практические задания

1.С помощью алгоритма Краскала найти кратчайший остов графов, изображенных на рис. 2.15.

	4			5
		5	18	12		11
				6
	10	9	17
5				15
	11	6	13	14	9	10
	8
	3			3
	G1			G2

Рис. 2.15 2. Все площадки для отдыха, расположенные в горной лесопарковой зоне

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

		p2		7	p6
			6
	1				5		2
		4		p5
			3		4
p1	1	p3		1	p8	9	p9
		5			4
	1						6
				7
		p4
					p7

Рис. 2.16

2.9. Эйлеровы и гамильтоновы графы

Вернемся к задаче о кёнигсбергских мостах: можно ли, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту только один раз? Многие были убеждены, что это невозможно, но лишь в 1736 году швейцарский математик Л. Эйлер сумел доказать этот факт. Эйлер решил более общую задачу: когда в неорграфе можно найти такой цикл, в котором каждое ребро графа участвовало бы только один раз?

31

Такой цикл, если он существует, называется эйлеровым циклом, а граф, содержащий такой цикл, – эйлеровым графом. Ответ на поставленный вопрос дает теорема Эйлера, доказанная в 1736 г.

ТЕОРЕМА 2.4. [12, гл.7]. Связный неорграф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

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

Доказательство достаточности можно найти в [12, гл.7]

Доказано также (Р.Рейд, 1962 г.), что вероятность того, что случайно взятый граф является эйлеровым, равна нулю.

ПРИМЕР 2.12. На рис. 2.17, а изображен эйлеров граф, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 4, 2, 6, 1). На рис. 2.17, б изображен план города Кенигсберг, в котором ребрам соответствуют мосты, а вершинам – различные части города. Так как в нем есть вершины с нечетными степенями, то не существует цикла, проходящего по всем ребрам (мостам) только один раз. Следовательно, этот граф неэйлеров.

2

C

3

1

A D

4

6

B

5

а)

б)

Рис. 2.17

32

u1, u2 , u3, u4 , u5 , u6

ТЕОРЕМА

Понятие эйлеровости можно распространить и на орграфы. Имеет место следующая теорема.

2.5. Связный орграф G = ( X ,U ) содержит эйлеров контур (эйлеров путь) тогда и только тогда, когда полустепени захода d + (xi ) и полустепени исхода d − (xi ) всех вершин удовлетворяют условиям:

для случая контура d + (xi ) = d − (xi ) для всех xi X ;

для случая пути d + (xi ) = d − (xi ) для всех xi ≠ p или q , d + ( p) = d − ( p) −1, d − (q) = d + (q) +1, где p − начальная, а q −конечная вершина эйлерова пути.

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

Задача отыскания эйлерова цикла имеет много потенциальных приложений, связанных с проблемой инспектирования распределенных систем, когда требуется проверить все «компоненты». Например, проверка электрических, телефонных или железнодорожных линий. Другие приложения могут быть связаны с отысканием наилучшего метода работы автоматических вентиляционных устройств, составлением оптимального маршрута при уборке помещений и коридоров в больших учреждениях.

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

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

новым графом.

В орграфе рассматривают гамильтоновы пути и контуры.

ПРИМЕР 2.13. Граф, представленный на рис. 2.18, а, является гамильтоновым, так как последовательность его ребер образует гамильтонов цикл. Граф на рис. 2.18, б имеет гамильтонову цепь, состоящую из ребер u1,u2 ,u3,u4 , но не имеет гамильтонова цикла.

33

	u6	u5	u4	u5
			u6	u1
u1	u7		u4	u2
			u3
	u2	u3
	а)			б)
			Рис. 2.18

Слово «гамильтонов» в данных определениях связано с именем У.Гамильтона, который в 1859 году придумал игру, где использовался додекаэдр, всем вершинам которого были даны названия известных городов. Задача играющего состояла в том, чтобы определить замкнутый путь через все города, посетив каждый из них только один раз. Одной из практических задач, связанных с понятием гамильтонова пути, является задача о коммивояжере: коммивояжер должен посетить каждый из заданных n городов, выехав из некоторого города и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояние между каждой парой городов. С точки зрения теории графов, задача коммивояжера сводится к поиску гамильтонова цикла минимального веса в полном взвешенном графе, если под весом цикла понимается сумма весов составляющих его ребер. Задача о коммивояжере и ее варианты имеют большое число практических приложений в различных областях человеческой деятельности. Например, ее приложениями являются сбор почтовых отправлений из почтовых ящиков, составление расписания выполнения операций на машинах, проектирование электрических сетей, управление автоматическими линиями.

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

34

	ТЕОРЕМА 2.6. Если G – сильно связный орграф на n		вершинах без пе-
тель,	для любой вершины	x которого справедливо		неравенство
d +(x) + d −(x) ≥ n , то G имеет гамильтонов контур.
	ТЕОРЕМА 2.7. Простой орграф G , имеющий последовательность сте-
пеней	d1 ≤ d2 ≤... ≤ dn , является	гамильтоновым, если	из	того, что

dk ≤ k ≤ n / 2 , следует dn−k ≥ n − k , где n – количество вершин графа.

Отметим, что указанные критерии представляют теоретический интерес и не пригодны для произвольных графов, встречающихся на практике. С другой стороны, существующие алгебраические методы определения гамильтоновых циклов не могут быть применены к задачам с более чем несколькими десятками вершин, так как требуют слишком большого времени работы и большой памяти компьютера. Более приемлемыми являются методы перебора, например метод Робертса и Флореса [10], и мультицепной метод, которые не предъявляют чрезмерных требований к памяти компьютера.

2.10.Практические задания

1.Существует ли эйлеров цикл в графах, изображенных на рис 2.19?

Рис. 2.19

2. Задача Эйлера о шахматном коне [9]. Найдите такую последователь-

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

35

* 4 * " ( 6 / ) *

? 5

@ 3 J / / 5 3 / / G / / / # #/ @

3/ / 3 3 /

3 / 5

# *

/ 3 5

@ @ 3 # F 3 /

G 3 3 3

/ 4 3 5

3 / 3 6/ G

! J G G # F

3 /

G / 3

/ 3 3 3/ # 9

& - 0

0 & -

& & 0# 3 5 3 # F 3 & 5 &

6 -&

#

!

F 4

3 G 3 3 6 /

@ / 3 #

) & & S

7 r& a, b -

S :5;&<6#

- 7 r 0 5

6=

V,6 r(a, b) = r(b, a)3

V&6 r(a, b) 0 r(a, b) = 0 & a = b3

VO6 0 a, b, c S r(a, b) r(a, c) + r(c, b)#

V,6 / a b

b a# V&6 / 3 3 3 3

/ G # F !/

VO6 / @ 3/

a b 3 3 a b 3

c# H 3 3/ r(a, b) 3

a b# ? G 3 (S, r) 4

3 S/ 3 r6 3 G

#

? 3 3 3 3 5

/ 3 3 3 5

/ @ G 3 3 @

3 / 3 / 3 # 3 V,6/ V&6/ VO6 # ? 5 3 3 3 7 33

3 #

3 3 3 5

3 4 6# R 3

3 A B / 5

@ G @ 7# R / 5

G A, B ! O

# / 5

@ A B/ 3 G #

H r(A, B) G /

# R / -

7 & 0 A B# R /

G 3 ! G

/ # H 3

4 3 6/ @ 3 #

) 3/ / @ ! /

/ 3 #

2 3 / 3 3 5

3 # % 3 / r(A, B) 3

3 3 A B/ 3 / 3 3 5

# @ G @ 5

3 #

(S, r) ! Q S ! # 9 7 r& &

Q (Q, r)#

) 3 V,6 5 VO6#

E 3 3 / 3

J # ? 3

3 3 3 3 / 5

# ) G 3 Q J 3 #

* / 0 0 0 0 &

.& #

3 3 3 @ 3 3 R 5

3 # ? G 3 3 3 3

/ 3 3 R # 3 5

3 # * 3 r(x, y) 3

r1(x, y) = |x − y| =			(x − y)2	.	(1)
F 3 3/
		z R
z / z 0;
|z| = −z	/ z < 0.

R / |z| = |z − 0| 3

3 O 4 36 z# G 3

# " 3 @ 3 3 3 5

@ #

4 0 a, b R 5

6

|a + b| |a| + |b|.

(2)

H 3 3 3 /

3 4,6# ? 3 / / # ? 5

@ ! 3 4&67

r1(x, y) = |y − x| = |y − z + z − x| |y − z| + |z − x| = r(x, z) + r(z, y).

? 3 3 3 5

@ x/ @ r(x, a) = = |x − a| < ε# % 3 / G 3 x/ 5

a

ε#

ε > 0 ! # . 0

ε 5-06 a

(S, r) U(a, ε) s S& 0

r(s, a) < ε#

R ε5 3 3 U(a, ε)# F 3 / ε = 0, 3/

U(a; 0, 3) a '/O# / 3 r1/

3 4,6 3 / G 5 5

/ a / 3 3 ε/

3 3 (a − ε, a + ε)#

F 3 3/ 3 XOY 5

OX, OY 3 3 3 /

@ G / 3 4

3 3 36 3 @ @ O# ) 5

3 /

3 J G / /

(a, b), a, b S 3 5

3 (a, b)# " 3 @ 3 / 5

/ 3 3 5

3 3 @ (x, y) J 3

# 3 3 / @

(x, y), x, y R/ 3 G 3 3 3 R2# H 3 5

3/ 3 @ 3 3

3 3 3 3 R2#

? M, N XOY /

3 3 / (u, v), (x, y) J #

$ / 3

r2(M, N) =

(x − u)2 + (y − v)2

(3)

3 XOY #

1 3 XOY 3 3 OXOY / 3 ? r2(M, N) 3 5

3 3 M, N / 3 3 3 MN 5 3 @ 3 # ε5 P G 3

ε ! 3 G #

% / 3 @ 3 3

XOY Z / 3 3

(x, y, z)# H 3

r3(M, N) =			(x − u)2	+ (y − v)2 + (z − w)2			(4)
				M(u, v, w)		N(x, y, z) #
	3 3

? G 3 ε5 P G 3

ε#

? 3 Rn 5

n# % 3 / M(x1, x2, ..., xn), N(y1, y2, ..., yn) 5

/

rn(M, N) = (y1 − x1)2 + (y2 − x2)2 + ... + (yn − xn)2

3 (Rn, rn), n = 1, 2, 3..., 3 5

3 3# ) / M, N J

Rn/ 5 OM, ON 5

(OM, ON) = x1y1 + x2y2 + ... + xnyn.

H 3 @ G

3

rn(M, N) = (MN, MN) = MN .

* 3 / 3 @ 3

Rn ϕ 3 3 7

cos ϕ = (OM, ON) ,

OM ON

· 3 3 / 3 /

@ ! # ? Rn 3

3 3 3 4

3 3 1 6#

Q S

(S, r)& x Q

ε > 0 5 x6& ε U(x, ε) - Q#

2 3 3 / 3 5

3 ε5 / ! 3 @ G 3 3 #

. / 0

#

# 4)

3 #6

. 0 x S 0

V S&

& x#