учебное пособие - теория графов

Пример 12.3. Граф G не имеет эйлерова цикла:

Замечание 12.3. Напомним, что простой цикл графа G – это такой маршрут G, который удовлетворяет двум условиям:

1)первая и последняя вершины маршрута совпадают (циклический мар-

шрут);

2)все остальные вершины маршрута попарно различны (простая цепь).

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

Доказательство. Пусть G (V , R) – непустой конечный связный неорграф и a V : deg a – четное число. Если граф G содержит пет-

лю, то данная петли и будет искомым простым циклом. Пусть G – граф без петель. Так как G – непустой граф, то он имеет ребра. Это означает,

что a1 V :	dega1 0		a2 V : (a1, a2 ) R				dega2 0 . Так
как deg a2 – четное число,			то a3 V :	(a2 , a3 ) R				dega3 0 .
Продолжая	аналогичные		рассуждения,	получим		маршрут вида:

(a1, a2 ,a3 , ) (1). Поскольку G – конечный граф, то найдется такое на-

туральное число k, что a1, a2 ,a3 , , ak – попарно различные вершины, а

61

ak 1 al	для	некоторого l, 1 l k , т.е. маршрут (1) имеет	вид:
(a1, , al	, ak	, ak 1 al , ) . Отсюда следует, что (2) – искомый про-
		(2)
стой цикл. Лемма доказана.
Теорема		12.1 (критерий эйлеровости графа). Непустой конеч-
ный связный неорграф G является эйлеровым тогда и только тогда, ко-
гда степень каждой вершины графа G является четным числом.
Доказательство. Пусть G (V , R) – непустой конечный связный
неорграф.
1.	Необходимость. Пусть G – эйлеров граф. Покажем,		что
a V :	deg a – четное число. Так как G – эйлеров граф, то в G сущест-
вует эйлеров цикл Р: (a1,u1,a2 ,u2 ,...,an ,un ,an 1 a1). Это означает,			что
u1,u2 ,...,un R . Покажем, что V a1, a2 ,..., an . Допустим, что			V

a1, a2 ,..., an . Тогда a V \ a1, a2 ,..., an . Это означает, что a – изолированная вершина графа G, и значит, граф G не является связным. Противоречие. Следовательно, V a1, a2 ,..., an . Поэтому достаточно показать,

что deg ai – четное число, i 1, n .

Пусть ai a1 и аi встречается в Р k раз. Так как каждому вхожде-

нию вершины аi соответствует в Р два ребра ui 1,ui , то degai 2k – чет-

ное число. Пусть аi=a1 и вершина аi встречается в Р, помимо начала и конца, t раз. Тогда deg ai =2t+2 – четное число.

2. Достаточность. Пусть степень каждой вершины графа G является чётным числом. Докажем, что G – эйлеров граф. Доказательство прове-

дём методом математической индукции по числу m рёбер графа G .
1) Пусть m =1. Тогда, ввиду условия, граф G имеет вид:	.
Следовательно, G – эйлеров граф.
62

2)Пусть m >1. Предположим, что утверждение верно для любого непустого конечного связного неорграфа с числом рёбер, меньшим m.

3)Докажем, что утверждение верно для графа G c m ребрами. Согласно лемме 1, в G существует простой цикл Р. Пусть G – граф, полу-

ченный из	G удалением				всех рёбер, входящих в цикл		Р.		Пусть
H1, H2 ,..., Hk	– непустые				связные компоненты графа	G .			Тогда
H1, H2 ,..., Hk	– непустые конечные связные неорграфы с числом ребер,
меньшим m.	По предположению индукции графы H1, H2 ,..., Hk						являются
эйлеровыми.	Пусть			P , P ,..., P – эйлеровы циклы графов		H , H		2	,..., H	k
				1 2	k	1
соответственно. Так как G – связный граф, то цикл Р имеет по крайней
мере по одной общей вершине с каждым из циклов P , P ,..., P .									Пусть
					1 2		k
ai P Pi , i 1, k.				Построим цикл графа G по следующему правилу:

возьмём произвольную точку из Р и будем двигаться от неё по циклу Р до тех пор, пока не встретим первую вершину, принадлежащую множествуa1, a2 ,..., ak , пусть, например, вершину аl. Тогда, начиная с вершины аl ,

будем двигаться по эйлерову циклу Рl до тех пор, пока не вернёмся в исходную точку (пока не обойдём весь цикл Рl). Затем от вершины аl будем двигаться по циклу Р до тех пор, пока не встретим следующую вершину, принадлежащую множеству a1, a2 ,..., ak , и т.д., через конечное

число шагов, вернёмся в исходную вершину цикла Р. Построенный цикл является искомым эйлеровым циклом графа G. Следовательно, G – эйлеров граф.

Из 1)–3) по методу математической индукции утверждение верно для любого натурального числа m. Теорема доказана.

Замечание 12.4. Из теоремы 11.1 следует, что задача о кёнигсбергских мостах имеет отрицательное решение (см. введение), так как, например, deg D 3.

63

§ 13. Гамильтоновы графы

Содержание параграфа

гамильтонов граф, гамильтонов цикл;

гамильтонова цепь;

задача о кругосветном путешествии;

признаки гамильтоновости графа (теорема Дирака, теорема Оре, теорема Хватала).

Определение 13.1. Связный неорграф G называется гамильтоновым, если он имеет гамильтонов цикл, т.е. простой цикл, содержащий все вершины графа G.

Замечание 13.1. Другими словами, гамильтонов цикл графа G – это такой маршрут G, который удовлетворяет трем условиям:

1)первая и последняя вершины маршрута совпадают (циклический мар-

шрут);

2)все остальные вершины маршрута попарно различны (простая цепь);

3)маршрут содержит все вершины графа G (условие гамильтоновости).

Замечание 13.2. Простая цепь связного неорграфа G называется гамильтоновой, если она содержит все вершины графа.

Замечание 13.3. Гамильтоновы цепь, цикл и граф названы в честь ирландского математика Ульяма Гамильтона (1805–1856 гг.), который впервые определил эти объекты, предложив в 1859 году задачу «Кругосветное путешествие»: 20 вершин додекаэдра символизировали крупнейшие города мира, а рёбра – соединяющие их дороги; требовалось, переходя по ребрам додекаэдра, посетить каждый город в точности один раз и вернуться в исходную вершину.

64

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

Теорема 13.1 (теорема Дирака). Пусть G – связный неорграф,

G=(V,R),

V

n ,

n 3 . Если

a V : deg a

n

, то G – гамильтонов

граф.

2

Доказательство. Пусть G=(V,R) – связный неорграф,

V

n , n 3 ,

и a V : deg a n . Покажем, что G – гамильтонов граф. Будем добав-
	2
лять к графу G вершины, и соединять их с каждой вершиной графа до тех
пор, пока из	графа G не получится гамильтонов граф G . Пусть
G (V , R )	и k – наименьшее число вершин, которые необходимо до-

бавить. Покажем, что k = 0. Допустим, что k >0. Рассмотрим гамильтонов цикл графа G : P a1, b, a2 , , an a1 , где a1, a2 V , b V .

1) Покажем, что a1, a2 – несмежные вершины графа G. Допустим, что a1, a2 R . Тогда из цикла P получим цикл: a1, a2 , , an a1 . Это означает, что b – лишняя вершина, и значит, число добавляемых вершин меньше k. Противоречие. Следовательно, допущение неверно, и поэтому a1, a2 – несмежные вершины.

		2) Допустим, что в цикле P		существуют соседние вершины a		и
					1
a	,	такие что a	– смежная	с a1, a	– смежная с a2, т.е.
2		1		2
				65

P : a , b, a			2	, , a ,a		, , a	n	a		. Так как G – неорграф, то записав вер-
	1				1 2			1
					(1)
шины в (1) в обратном порядке, из цикла P получим гамильтонов цикл
графа G		вида a ,b, a , , a , a , , a									a . Это означает, что b – лиш-
					1	1		2	2	n	1
няя вершина. Противоречие. Следовательно,
	если в				P некоторая вершина смежна с a1, то за ней стоящая вер-
шина не смежна с a2;						(2)
	если в				P некоторая вершина смежна с a2, то перед ней стоящая
вершина не смежна с a1.
	3) Пусть X – множество всех вершин графа G , смежных с a1, Y –

множество всех вершин графа G , не смежных с a2. Тогда, согласно (2),

X

Y

. Ввиду условия,

X

deg a k

n

k . Поэтому

Y

n

k .

1

2

2

Пусть Z – множество всех вершин графа G , смежных с a2. Тогда

по условию

Z

deg a

2

k

n

k , то есть

Z

n

k . Тогда с одной

2

2

стороны,

V

V

k n k .

С другой стороны,

V

Y

Z

n 2k .

Противоречие. Следовательно,

k 0 G – гамильтонов граф. Теорема

доказана.

	Теорема 13.2 (теорема Оре). Пусть G (V , R) – неорграф,							V		3,
и a,b V : deg a deg b n . Тогда G – гамильтонов граф.
	Теорема 13.3 (теорема Хватала). Пусть G (V , R) – неорграф,
V a1, a2 ,..., an , deg ai				di , i		, d1 d2 dn , n 3 и для любого k
					1, n
из dk	k	n	следует	dn k n k . Тогда G – гамильтонов граф.
	2
				66

§14. Вершинно непересекающиеся

иреберно непересекающиеся цепи

Содержание параграфа

вершинно непересекающиеся цепи;

разделяющее множество для вершин;

реберно непересекающиеся цепи;

теорема Менгера о разделяющем множестве вершин;

реберно непересекающиеся цепи, покрывающие граф;

теорема о минимальном числе реберно непересекающихся цепей, покрывающих граф.

Определение 14.1. Пусть G=(V,R) – связный граф, a и b – несмежные вершины графа G. Две цепи, соединяющие вершины a и b, называются вершинно непересекающимися, если они не имеют общих вершин, отличных от a и b. Множество вершинно непересекающихся (a,b)-цепей обозначается P(a,b).

Определение 14.2. Пусть G=(V,R) – связный граф, a и b – вершины графа G. Множество вершин S граф G=(V,R) называется разделяющим множеством вершин для a и b, если a и b принадлежат различным связным компонентам графа G–S, и обозначается S(a,b).

Определение 14.3. Две цепи, соединяющие вершины a и b графа G, называются реберно непересекающимися, если они не имеют общих ребер.

Теорема 14.1 (теорема Менгера). Пусть a и b – несмежные вершины графа G. Тогда наименьшее число вершин в множестве, разделяющем вершины a и b, равно наибольшему числу вершинно непересекающих-

ся простых (a,b)-цепей, т.е. max|P(a,b)|=min|S(a,b)|.

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

67

Теорема 14.2. Пусть G – связный граф. Если G содержит k вершин нечетной степени, то минимальное число покрывающих его реберно неппересекающихся цепей равно k/2.

Доказательство. Пусть G – связный граф, содержащий k вершин нечетной степени. Тогда по следствию 2.1.1 число k является четным. Рассмотрим граф G , полученный из графа G добавлением новой вершины х и ребер, соединяющих вершину х со всеми вершинами графа G нечетной степени. Тогда в графе G степень каждой вершины является четным числом. Согласно теореме 12.1, граф G является эйлеровым. Пусть Р – эйлеров цикл графа G. При удалении из Р всех ребер, инцидентных вершине х получается не более k/2 цепей, содержащих все ребра графа G, т.е. покрывающих G. С другой стороны, граф, являющийся объединением m реберно непересекающихся цепей, имеет не более 2m вершин нечетной степени. Таким образом, граф G нельзя покрыть цепями, число которых мньше k/2. Теорема доказана.

§ 15. Метрические характеристики связных графов

Содержание параграфа

расстояние между вершинами графа;

эксцентриситет вершины;

радиус и диаметр графа;

центральные и периферийные вершины;

матрица расстояний графа.

Определение 15.1. Пусть G (V , R) – связный неорграф, a,b V . Расстоянием между вершинами a и b называется длина кратчайшего (a,b) -маршрута, и обозначается d (a,b) . Кратчайшая (a,b) -цепь называется геодезической (a,b) -цепью. Полагают, что d(a, a) 0 .

Понятие расстояния между вершинами удовлетворяет следующим

4 аксиомам:

68

А1: d (a,b) 0 (неотрицательность). А2: d(a,b) d(b, a) (симметричность).

А3: d(a,b) 0 a b .

А4: d(a,b) d(a, c) d(c,b) (неравенство треугольника).

Определение 15.2. Пусть G (V , R) – связный неорграф, V {a1 , a2 ,..., an }. Матрицей расстояний графа G называется матрица P n-го порядка вида P ( pij ) , где pij d (ai , a j ),i, j 1, n .

Замечание 15.1. Из аксиомы А2 следует, что pij p ji , i, j 1, n . Это означает, что матрица P симметрична относительно главной диагонали.

Определение 15.3. Пусть G (V , R) – связный неорграф, a V . Эксцентриситетом вершины a называется число, обозначаемое e(a) и определяемое равенством e(a) max{ d(a,b) b V }.

Замечание 15.2. Эксцентриситет вершины равен наибольшему из

расстояний от вершины a до остальных вершин.
	Замечание 15.3. Эксцентриситет вершины ai равен наибольшему
из чисел в i-й строке матрицы расстояний.
	Определение 15.4.
1.	Диаметром связного неорграфа G (V , R)								называется наибольший из
	эксцентриситетов				всех	его	вершин	и	обозначается	d (G) ,	т.е.
	d(G) max{ e(a)				a V }.
2.	Радиусом связного неорграфа G (V , R)								называется наименьший из
	эксцентриситетов				всех	его	вершин	и	обозначается	r(G) ,	т.е.
	r(G) min{ e(a)				a V } .
	Определение 15.5.
1.	Вершина a графа G называется периферийной, если e(a) d (G) .
							69

2.Вершина a графа G называется центральной, если e(a) r(G) .

3.Центром графа G называется множество всех центральных вершин графа G.

§ 16. Взвешенные связные неорграфы

Содержание параграфа

взвешенный связный неорграф;

матрица весов графа;

вес маршрута;

взвешенное расстояние между вершинами;

взвешенный эксцентриситет вершины;

взвешенные радиус и диаметр графа.

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

Определение 16.1. Пусть G (V , R) – связный неорграф, SV , SR

– некоторые множества, называемые множествами меток вершин и меток ребер графа G соответственно. Пусть fV :V SV , f R : R SR –

функции. Пара функций fV , f R называется распределением меток графа G. Граф с заданным на нем распределением меток называется взвешенным графом (или помеченным графом). При этом, элемент fV (a) называ-

ется весом (меткой) вершины a, а элемент f R (u) называется весом (меткой) ребра u.

В графе могут быть помечены только вершины или только ребра.

70