Теорема 4. Для плоского связного графа существует правильная раскраска вершин в 5 цветов.

Доказательство. Для p£5 теорема верна. Пусть для p – 1 вершин теорема доказана. Рассмотрим граф с p вершинами. Найдем в нем вершину v с d(v) £5. Обозначим через G[v] подграф, полученный удалением вершины v и инцидентных ей ребер. Существует правильная раскраска графа G[v]. Наша задача – раскрасить вершину v. Если d(v) < 5, то вершину v раскрасим цветом, которого нет у смежных с v вершин. Пусть d(v)=5 и пусть все смежные с v вершины раскрашены в различные цвета. Обозначим через G₁₃ подграф (рис. 4.10) графа G[v], состоящий из вершин цвета 1 и 3. Если в нем

Рис. 4.10. К доказательству теоремы 4

нет путей между вершинами 1 и 3 из смежных с v, то компоненту связности вершины 3 перекрасим следующим образом: все вершины компоненты цвета 3 перекрасим в цвет

1, а все вершины компоненты цвета 1 – в цвет 3. Затем v покрасим в цвет 3. Если в графе G₁₃ существует путь, соединяющий вершины 1 и 3 и состоящий из вершин цвета 1 или 3, то в подграфе G₂₄ нет пути между вершинами, смежными с v. В этом случае перекрасим вершины компоненты содержащей 4, аналогично тому, как это делалось выше: цвета 2 – в 4, а цвета 4 – в 2. Таким образом, если граф имеет p вершин, то для него существует правильная раскраска пятью красками. Теорема доказана.

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

 

Рис. 4.11. Пять тел Платона

Следующее приложение эйлеровой характеристики – доказательство того, что правильные многогранники исчерпываются телами Платона. Рис. 4.11 показывает, что по крайней мере 5 правильных многогранников существует.

Теорема 5. Пусть p – число вершин, q – число ребер, r – число граней правильного многогранника. Тогда возможен один из следующих случаев, рассмотренных в таблице 4.1.

Таблица 4.1

 

Свойства тел Платона

	p	q	r
Тетраэдр
Куб
Октаэдр
Додекаэдр
Икосаэдр

 

Доказательство. Вершины графа, состоящего из ребер и вершин фиксированного многогранника имеют одинаковую степень. Обозначим эту степень через x. Пусть y – число сторон грани этого многогранника. Получаем систему уравнений

.

Так как x,y ³ 3, а в случае x,y ³ 4 имеет место неравенство , то возможны следующие случаи: x=3 или y=3.

Рассмотрим случай x=3:

.

Получаем

x =3, y =3, ;

x =3, y =4, ;

x =3, y =5, .

Аналогично x =4, x =5 при y =3.

 

Упражнения

Свойства графов

Все графы предполагаются простыми. Графы называются изоморфными,

если существует биекция f между множествами их вершин, такая что

{u,v} ребро Û {f(u), f(v)} – ребро.

1. Доказать, что граф имеет четное число вершин с нечетными степенями.

2. При встрече студентов состоялось 15 рукопожатий, трое человек сделали по 4 рукопожатия, а другие – по 3. Сколько было студентов.

3. Может ли существовать группа из 23 человек, каждый из которых знаком с пятью другими?

4. В соревнованиях по шахматам по круговой системе участвуют 5 человек. Все, кроме Иванова и Петрова, сыграли различное число партий. Сколько партий сыграли Иванов и Петров?

5. Можно ли нарисовать без отрыва карандаша граф K₆, у которого удалено одно ребро.

6. Найти число попарно неизоморфных графов, у которых 2 вершины имеют степень 2, 2 вершины имеют степень 3, и 2 вершины имеют степень 4. Остальные вершины имеют степень 0.

7. Найти число попарно неизоморфных графов, у которых 3 вершины имеют степень 2, 3 вершины имеют степень 3, и 3 вершины имеют степень 4. Остальные вершины имеют степень 0.

8. Доказать, что в простом графе, имеющем не меньше двух вершин, всегда найдутся две вершины одинаковой степени.

9. Какие из графов, приведенных на рис. 4.12, изоморфны?

Рис. 4.12. Примеры графов

 

10. Какие из графов, приведенных на рис. 4.13, изоморфны?

 

 

Рис. 4.13. Примеры графов

11. Найти число всех попарно неизоморфных графов, имеющих 4 вершины. Нарисовать эти графы.

Ответ: существует 11 неизоморфных графов (рис.4.14).

Рис. 4.14. Графы, имеющие 4 вершины

 

12. Кратчайший путь, соединяющий вершины u и v в графе, называется геодезическим путем между вершинами. Его длина обозначается d (u, v). Диаметром D(G) графа называется длина самого длинного геодезического пути в этом графе, т.е. D(G)=max{d (u, v): u, v Î V}. Найти диаметр графа, приведенного на рис. 4.15. Найти диаметр графа K₅.

 

 

Рис. 4.15. Пример графа

 

13. Матрица смежности состоит из коэффициентов a_ij =1 Û вершины i и j смежны.

(1) Построить матрицы смежности для графов K₃ и K₄;

(2) Доказать, что сумма коэффициентов i -й строки матрицы смежности равна степени i -й вершины;

(3) Построить матрицу смежности графа, состоящего из вершин и ребер куба.

(4) С помощью матрицы смежности построить матрицу, коэффициентами которой является количества путей длины 2 из вершины i в вершину j.

(5) Как связаны след матрицы A³ с числом треугольников в графе?

14. Циклы {z₁, z₂, × × ×, z_n} называются независимыми, если z₁Dz₂D × × × Dz_n ¹ Æ Доказать, что у связного графа максимальное число независимых циклов равно q-p+1.

15. Сколько компонент связности имеет лес, содержащий 76 вершин и 53 ребра?

16. Доказать, что среди 6 человек найдется тройка знакомых, или тройка незнакомых людей.

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