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

3.Отношение эквивалентности на множестве всех точек плоскости L разбивает данное множество на непересекающиеся классы, которые называются гранями графа G.

Например, граф G на рисунке имеет 4 грани f1, f2, f3, f4, причем грань f1 – бесконечная.

Теорема 24.1 (теорема Эйлера). Пусть G – плоский связный граф, имеющий n вершин, m ребер и f граней. Тогда n f m 2 .

Доказательство. Пусть G – плоский связный граф, имеющий n вершин, m ребер и f граней. Докажем равенство n f m 2 . Доказательство проведем методом математической индукции по параметру m.

	G связный граф
1. Пусть m 0		n 1, f 1		1 1 0 2 – верно.

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

3.Докажем утверждение для графа G с m ребрами. Пусть G – связный

граф, полученный из графа G удалением некоторого ребра u, т.е. G G u . (Если таких ребер нет в G, то всякое ребро графа G является мостом, и значит, по теореме 20.1, G – дерево с n вершинами, m=n–1 ребрами и 1 гранью. Тогда n+1=n–1+2 – верное равенство). Пусть n , m , f –

число	вершин, ребер и		граней графа G соответственно
n n, m m 1.		Согласно	предположению индукции,			n f m 2
(*).	Поскольку	ребро	u	не	является	мостом,	то
	(*)
f f 1 n f 1 m 1 2 , т.е. n f m 2 .
				101

n f m k 1.

Из 1-3 по методу математической индукции следует, что утверждение верно для любого m N {0}. Теорема доказана.

Следствие 24.1.1. Пусть G – плоский граф, имеющий n вершин, m ребер, f граней и k связных компонент. Тогда

Следствие 24.1.2. Пусть G – планарный связный неорграф без петель, имеющий n вершин, m ребер, причем n 3 . Тогда m 3n 6 .

Доказательство. Так как G – планарный связный граф, то G G , где G – некоторый плоский связный граф, имеющий n вершин и m ре-

бер. Пусть f – число граней G

и пусть mi

– число ребер, ограничиваю-

любое реброограничивает

не б о л едев у гх р а н е й

m m m

1

... m

щее i-ю грань,

i 1, f

2

f

1

2

3 3 ... 3

1

3 f

1

2 m 3 f

3 f 2 m 0 .

2

2

f раз

По

теореме

24.1

имеем

n f m 2 .

Тогда

f m n 2

3 3 f 3m 3n 6

3 f 2m m 3n 6

0

m 3n 6 0

m 3n 6 . Следствие доказано.

Следствие 24.1.3. Графы K5 и K3,3 не являются планарными.

Доказательство. 1.

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

планарный граф.

Тогда

10

5

10 9 – противоречие. Следовательно, K5 граф не явля-

m 3n 6 , т.е.

ется планарным.

2. Допустим, что K3,3 – планарный граф. Тогда K3.3 G , где G – плоский граф с 6-ю вершинами и 9-ю ребрами. Пусть f – число граней графа G, mi – число ребер, ограничивающее i-ю грань. Следовательно,

102

4

4

1

4 4 ... 4

1

m

2 f

m 4, i 1, f

m

... m

i

1

f

2

2

f раз

f

m

, f 4.

С

другой

стороны, по

теореме

24.1

2

n f m 2

f 5 .

Противоречие. Таким образом, граф K3,3 не

является планарным. Следствие доказано.

Следствие 24.1.4. Всякий планарный граф без петель имеет вершину, степень которой не больше 5.

Доказательство. Пусть G V , R и V n . Не теряя общности

рассуждений, можем считать, что G –	связный граф и n 3 . Допустим,
	m	deg a		6n
что a V : deg a 5, т.е. deg a 6		a V			3n , т.е.
	2			2

m 3n . С другой стороны, по следствию 24.1.2 m 3n 6 . Противоречие. Следствие доказано.

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

Определение 24.2. Наименьшее число ребер, удаление которых приводит к планарному графу, называется числом планарности или искаженностью графа G и обозначается sk(G).

Лемма 24.1. Пусть G=Kn – полный граф n-го порядка, n 3. Тогда sk(G)= Cn2 3n 6 .

Определение 24.3. Наименьшее число планарных подграфов графа G, объединение которых совпадает с графом G, называется толщиной графа G и обозначается t(G).

103

Толщина графа G равна минимальному числу плоскостей k, при котором граф G разбивается на плоские части G1, G2, …, Gk.

Лемма 24.2. Пусть G – планарный граф. Тогда t(G)=1.

Рассмотрим обозначения: пусть x – целая часть числа x;

x x 1 .

Лемма 24.3. Пусть G – связный граф с n вершинами и m ребрами.

Тогда

(t G )		m		и (t G ) m 3n 7 .
					3n 6
	3n 6

§ 25. Раскраска графов

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

понятие вершинной и реберной раскраски графа;

правильная раскраска графа;

хроматическое число графа и его оценки;

хроматический многочлен графа и его свойства;

теорема Кенига о бихроматическом графе;

теорема о пяти красках;

гипотеза четырех красок.

Определение 25.1. Пусть G (V , R)		– неорграф, k N,
Nk 1, , k . Отображение	f :V Nk называется вершинной k-

раскраской или, коротко, k-раскраской графа G.

Замечание 25.1. k-раскраску графа можно трактовать как окрашивание каждой вершины графа в один из k имеющихся цветов.

Замечание 25.2. Функция f из определения 25.1 не обязана быть инъективной (то есть разные вершины могут быть окрашены в один цвет) и не обязана быть сюръективной (то есть для окрашивания вершин можно использовать не все цвета из имеющихся).

104

Определение 25.2.

1. k-раскраска f графа G (V , R) называется правильной, если

[a, b] R : f (a) f (b) .

2.Граф называется k-раскрашенным, если для него существует правильная k-раскраска.

Определение 25.3.

1.Пусть CG(k) – количество способов правильной k-раскраски графа G.

Функция fG(k)=CG(k) называется хроматическим многочленом графа

G.

2.Хроматическим числом графа G называется наименьшее натуральное число k, для которого существует правильная k-раскраска G, и обозначается (G) .

3.Если (G) k , то граф G называется k-хроматическим графом.

4.Правильная k-раскраска графа G при k = (G) называется минималь-

ной раскраской графа G.

Хроматическое число для некоторых графов найти достаточно про-

сто. Например, (Km,n ) 2 , (Kn ) n .

Лемма 25.1.

1.Граф G является 1-хроматическим тогда и только тогда, когда G – пустой граф.

2.Граф G является 2-хроматическим (бихроматическим) тогда и только тогда, когда G – непустой двудольный граф.

Теорема	25.1. Пусть	G – непустой неорграф. Тогда
(G) deg G 1.
Теорема	25.2. Пусть G –	непустой связный неорграф, не являю-

щийся полным, deg G 3. Тогда (G) deg G .

Теорема 25.3. Пусть G – планарный граф с n вершинами. Тогда хроматический многочлен графа G является многочленом n-й степени.

105

Теорема 25.4 (теорема Кёнига). Непустой неорграф является бихроматическим тогда и только тогда, когда он не имеет циклов нечетной длины.

Доказательство. 1. Необходимость. Пусть G (V , R) – бихроматический граф. Тогда по лемме 25.1 G – двудольный граф. Пусть V1 ,V2 – доли графа G. Допустим, что в G существует цикл нечетной длины, например, P : (a1, a2 , , a2l 1, a1) . Пусть, например, a1 V1 . Тогда

a2 V2 , a3 V1, a4 V2 , , a2l 1 V1, a1 V2 – противоречие. Таким образом, в G не существует циклов нечетной длины.

2. Достаточность. Пусть граф G не имеет циклов нечетной длины. Покажем, что G – двудольный граф. Можем считать, что G – связный граф с числом вершин большим 1. Пусть G (V , R), a V . Пусть V1 –

множество всех вершин b графа G, таких что d (a,b) – четное число, V2 –

множество всех вершин b графа G, таких что d (a, b)			– нечетное число
V1 V2 V , V1 V2		. Это означает, что V1 ,V2	– разбиение мно-
жества V.
Покажем, что в V1		и V2 нет смежных вершин. Допустим, что суще-
ствуют вершины	b1, b2 V1 :[b1, b2 ] R1 . Если			a b1 , то
d(a,b2 ) d(b1 ,b2 ) 1	–	нечетное число. Тогда b2 V2		a b1 . Если

a b2 , то	d(a,b1 ) d(b2 ,b1 ) 1 b1 V2 – противоречие. Таким обра-
зом, a b1	и a b2 .
Пусть		Pi – кратчайший (a,bi ) -маршрут, i 1,2 , d (Pi ) – длина
маршрута	Pi	. Тогда d(Pi ) d(a,bi )		– четное число, i 1,2 . Пусть a –
общая точка маршрутов P и			P ,	наиболее удаленная от a (возможно,
		1	2

что a a ).

106

Пусть P	– часть маршрута		P	, соединяющего a	с b , i 1,2 .
i			i		i
Тогда
d (P ) d (P ) d (P ) d (P ) 2d (a, a ) d (P ) d (P ) –
1	2	1	2	1	2

четное число, и значит, в G существует цикл С вида (a , ,b1 ,b2 , , a )

– цикл нечетной длины. Противоречие. Таким образом, во множестве V1 нет смежных вершин.

Аналогично доказывается, что множество V2 не содержит смежных вершин. Тем самым доказано, что G – двудольный граф. Тогда по лемме 25.1 G – бихроматический граф. Теорема доказана.

Теорема 25.5 (о пяти красках). Пусть G – планарный граф. Тогда(G) 5 . Другими словами, всякий планарный граф правильно раскрашивается, по крайней мере, пятью красками.

Доказательство. Пусть G V , R ,		V		n . Так как при правиль-

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

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

1.Пусть n=1 (G) 1 5 – верно.

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

107

3.	Докажем утверждение для графа G с n вершинами. По следст-
вию 24.1.4 существует вершина a V : deg a 5 . Пусть		G G a .
	2)
Тогда G	– плоский граф с (n–1) вершиной (G ) 5 .

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

Поскольку (G ) 5 , то вершины графа G раскрашиваются, по крайней мере, 5 цветами. Покажем, что (G) 5 . Достаточно показать, что удаленная вершина a раскрашивается одним из данных 5 цветов. Возможны 2 случая.

а) Пусть deg a<5. В этом случае смежные с а вершины могут быть окрашены четырьмя цветами, и значит, оставшийся цвет можно использовать для вершины а.

b) Пусть deg a=5. Если хотя бы две из смежных с а вершин окрашены в один цвет, то оставшийся неиспользованным цвет используем для вершины а. Пусть все вершины, смежные с а, окрашены в разные цвета.

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

108

Пусть G13 – подграф графа G, состоящий из всех ребер графа G,

соединяющих «красные» вершины с «желтыми». Если a1 G13 , то верши-

ну a1 можно перекрасить в желтый цвет и высвободить красный цвет для вершины а. Если a3 G13 , то вершину a3 можно перекрасить в красный цвет и высвободить желтый цвет для вершины а.

Пусть вершины a1 и a3 принадлежат различным компонентам связности графа G13 . В этом случае в компоненте связности, содержащей вершину a1 , перекрасим все «желтые» вершины в красный цвет, а «крас-

ные» – в желтый. Тогда вершина a1 будет окрашена в желтый цвет, и значит, красный цвет можно использовать для вершины a. Пусть вершины a1 и a3 принадлежат одной компоненте связности графа G13 . Тогда в графе G существует цепь, соединяющая вершины a1 и a3 в графе G

существует цикл С вида a , a1 , , a3 , a .

Рассматривая аналогично граф G24 , придем к случаю, когда в графе

G существует цикл C1, соединяющий вершины a2 и a4 . Так как вершина a2 находится внутри цикла С, а вершина a4 – снаружи, то цикл C1 пере-

сечет цикл С. Это означает, граф G не является плоским, что противоречит условию.

109

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

Возникает естественный вопрос: можно ли получить более сильный результат по сравнению с теоремой 5. Этот вопрос приводит к одной из наиболее известных нерешенных проблем теории графов – гипотезе четырех красок. Гипотеза четырех красок формулируется следующим образом.

Гипотеза (гипотеза четырех красок). Верно ли, что всякий планар-

ный граф раскрашивается с помощью четырех красок?

Более 100 лет математики пытаются доказать или опровергнуть эту гипотезу. Окончательное решение до сих пор так и не найдено. (Известно, например, что всякий планарный граф порядка меньшего 52 раскрашивается с помощью четырех красок).

110