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

Как уже отмечалось, теория графов своим рождением обязана следу­ющей задаче, возникшей в первой половине XVIII столетия и решенной петербургским математиком Л.Эйлером (см. рис.).

Город Кенигсберг (Калининград) расположен на берегах реки Прегель и двух островах. Различные части города были соединены 7 мостами. Можноли совершить прогулку по городу таким образом, чтобы, выйдя из дома,

вернуться обратно, пройдя по каждому мосту только один раз?

С

 

В

Изобразим карту рисунка в виде графа

С

 

В

Л.Эйлер доказал, что не существует маршрута, включающего в себя ка­ждое ребро только один раз. Л.Эйлер поставил более общий вопрос: для каких графов существует цикл (т.е. замкнутая цепь), содержащий все ре­бра графа, причем каждое ребро в точности по одному разу?

Графы, обладающие таким циклом (эйлеровой линией), называются эй­леровыми. Такой граф, очевидно, связный и степень каждой его вершины является четной.

Теорема 3. Конечный граф С = {V, Е) является эйлеровым тогда и только тогда, когда он связный и степень каждой его вершины является четной.

ДОКАЗАТЕЛЬСТВО. Если Є - эйлеров граф, то, как было отмечено, он связный и степень каждой его вершины четная. Обратно, пусть Є - связ­ный граф и степени всех его вершин являются четными числами. Возьмем некоторую вершину а Є V и рассмотрим максимальную цепь Т, исходя­щую из а. Так как граф Є связный и степень каждой вершины четная, то Т проходит через каждую вершину Є и заканчивается в а. В частности, Тявляется циклом. Если этот цикл не является эйлеровым, то Т содержит вершину 6, инцидентную ребру, не входящему в Т. Исходя из вершины 6, построим новую цепь, используя ребра, не принадлежащие Т. Это возмож­но, т.к. степень каждой вершины является четной. Новая цепь Ь должна оканчиваться в вершине Ъ. Но тогда мы можем построить больший чем Т цикл, исходящий из вершины а. Действительно, сначала следуем по Т от а к 6, затем по Ь делаем цикл и возвращаемся в 6, а затем продолжаем путь по Т. Это противоречит максимальности пути Т.

Итак, Т - эйлеров цикл. Теорема доказана.

Если же на связном конечном графе Є = (У, Е) имеется цепь, начина­ющаяся в вершине а и оканчивающаяся в вершине Ъ ф а, то предполагая, что она проходит по всем ребрам в точности по одному разу, мы видим, что а, Ь - единственные вершины нечетной степени. Обратно, если в связном конечном графе С = (У, Е) вершины а и Ъ (а ф Ь) являются единственны­ми нечетными, то, добавляя к Е новое ребро {а,Ь}, мы получим (согласно теореме 3) эйлеров граф, обладающий эйлеровым циклом Т. Удалив из Т ребро {а,Ь}, мы получим цепь, начинающуюся в а, заканчивающуюся в Ь и проходящую каждое ребро ровно один раз. Итак, доказана

Теорема 4. Конечный связный граф С = (У, Е) содержит цепь, начи­нающуюся в вершине а и оканчивающуюся в вершине 6, а также содер­жащую все ребра ровно по одиному разу тогда и только тогда, когда а, Ъ - единственные нечетные вершины этого графа.

Задача 13. Пусть Є = (У, Е) - конечный связный граф с 2к нечетны­ми вершинами. Доказать, что Є имеет семейство из к цепей, которые в совокупности содержат все ребра графа ровно по одному разу.

УКАЗАНИЕ. Пусть {а\,..., ак, Ь\,..., Ьк} - нечетные вершины. Добавим к Е новые ребра {а\, Ь\},..., {ак, Ьк}. Мы получим эйлеров граф, содержа­щий эйлеров цикл Т. Удалим из Т новые ребра. Получим искомое семейство из к цепей.

Задача 14. Конечный связный граф является эйлеровым тогда и толь­ко тогда, когда семейство его ребер можно разбить на непересекающиеся циклы.

Выходя из произвольной вершины а, идем по ребрам графа, соблюдая пра­вила:

1) стираем ребра по мере их прохождения и стираем изолированные вер­шины, которые при этом образуются;

2) на каждом этапе идем по мосту (ребро называется мостом, если его удаление нарушает связность графа) только тогда, когда нет других воз­можностей.

Указанный алгоритм действительно работает при прохождении каждой вершины Ь. Если Ь ф а, то оставшийся подграф Н связен и содержит ровно 2 вершины нечетной степени {а, Ь}. По теореме 4 существует эйлерова цепь Т из Ь в а. Удалим первое ребро этой цепи Т. Граф Н останется связным и данное рассуждение можно продолжить. Если же Ь = а, то рассуждаем аналогично.

Задача 15:

а) найти все Платоновы эйлеровы графы;

б) для каких чисел га, п следующие графы будут эйлеровыми: Кп, КтіП? ОТВЕТЫ: а) октаэдр; б) п - нечетное число; га = п = 0(тоа1 2). Задача 16. Пусть С„^\ - циклический граф порядка п — 1. Тогда

]¥п = Е1 + Сп^\ (колесо с п вершинами):

Алгоритм Флери построения эйлеровой цепи в эйлеровом графе С

 

п

При каких п граф \Уп является эйлеровым?

Задача 17. Можно ли ходом шахматного коня обойти всю шахматную доску (8 х 8) так, чтобы каждый ход встречался ровно один раз? При этом ходы

мы отождествляем.

УКАЗАНИЕ. Рассмотрим граф порядка 64; две вершины его инцидент­ны, если возможен ход конем из одной в другую; заметить, что он связный и применить теорему Эйлера.

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

УКАЗАНИЕ. Предположим противное. Тогда необходимо сделать 63 хода. При каждом ходе меняется цвет клетки на противоположный. Так как диагональ одноцветна, то получаем противоречие.

Задача 19:

а) доказать, что К5 имеет 264 эйлеровы цепи;

б) найти эйлеровы цепи графов

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

ИСТОРИЧЕСКАЯ СПРАВКА. Сэр У.Р.Гамильтон (W.R.Hamilton) -ирланский математик (1805-1865), профессор Дублинского университета. Доказал т.н. теорему Гамильтона-Кэли для матриц, ввел в рассмотрение тело кватернионов (первый пример некоммутативной алгебры с делением).

Примером гамильтонова графа является граф порядка 64 из задачи 17. Укажем один из гамильтоновых циклов в нем (задача Л.Эйлера о рыцарях, 1759):

56

41

58

35

50

39

60

33

47

44

55

40

59

34

51

38

42

57

46

49

36

53

32

61

45

48

43

54

31

62

37

52

20

5

30

63

22

11

16

13

29

64

21

4

17

14

25

10

6

19

2

27

8

23

12

15

1

28

7

18

3

26

9

24

Другими примерами являются следующие графы:

 

додекаэдр, пример У. Гамильтона, 1857

 

Граф называется полугамильтоновым, если в нем существует гамильто­нова цепь. Примерами негамильтонова графа и полу гамильтонова графаявляются графы:

 

С гамильтоновыми графами связана и следующая задача о коммивоя­жере ("о бродячем торговце"). Торговый агент должен посетить какое-то количество городов, побывав в каждом городе ровно один раз. Расстоя­ния (стоимость билета) между городами известны. Необходимо выбрать кратчайший (самый дешевый) путь (с возвратом в исходный город).

Задача 20:

а) какие из Платоновых графов имеют гамильтоновы цепи (циклы)?

б) имеют ли решения задачи о рыцарях на шахматной доске п х п при п = 3,4,5,6,7?

в) для каких чисел га, п графы Кт>п, \¥п, Кп являются гамильтоновыми?

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

Теорема 5. (Г.Дирак, 1952). Пусть С = (У, Е) - простой конечный граф порядка п > 3 такой, что степень каждой вершины > п/2. Тогда С - гамильтонов граф.

ДОКАЗАТЕЛЬСТВО. Если граф С не является гамильтоновым, то его можно достроить до гамильтонова графа С?!, добавив некоторое конечное число вершин 61, 62,..., Ь]. и соединив их со всеми вершинами {ах,..., ап} графа С При этом можно считать, что к > О и к является минималь­ным с этим свойством. Пусть а\ —>• Ъ\ —>• щ —¥ • • • —¥ а\ - гамильтонов цикл в С\. Вершина щ не является смежной с а\ в графе С\, иначе бы мы не использовали вершину Ь\ (а это противоречило бы минимальности к). Предположим, что существует вершина с смежная с щ, которая следует (в нашем цикле) за вершиной х, смежной с а\ :

X с

 

(1\ —"> 6) —"> (!■; —V ■ ■ • —V X —V С —V • • • —V (! |.

Тогда заменим последний цикл на цикл

а\ —>• х —>• • • • —>• щ —>• с —>• • • • —¥ Д1,

который отличается от предыдущего обратной ориентацией прохода в вы­деленной части. Противоречие с минимальностью к (мы не использовали 61!). Число вершин графа С\, не являющихся смежными с щ, не меньше числа вершин, смежных с а\ (т.е. > п/2 + к), т.к. в нашем цикле за каждой смежной с а\ следует некоторая вершина, не являющаяся смежной с щ. С другой стороны, число вершин смежных с щ > | + к. Поэтому порядок графа 6?1 не меньше числа п + 2к. Противоречие доказывает теорему.

Задача 21. В полном графе К2п+1 найти п гамильтоновых циклов, ка­ждые два из которых не имеют общих ребер.