2

3

4

2

3

4

1

1

5

6

5

6

7

7

8

9

10

8

9

10

а		б
2	3	4
1
5		6
7
8	9	10

в

Рис. 6.23

Исходный граф не эйлеров, так как в нем существует восемь вершин с нечетной степенью, а по теореме в эйлером графе все вершины имеют четную степень. Чтобы граф стал эйлеровым, необходимо, как минимум, удалить 4 ребра.

Такое решение есть: (1,2), (4,5), (7,8), (6,10). Тогда эйлеров цикл,

например, выглядит таким образом: (1,5,6,2,3,4,6,8,9,10,5,7,1).

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

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

168

Если такой цикл существует, то он называется гамильтоновым циклом (путем), а G называется гамильтоновым графом (рис. 6.24).

	Гамильтонов	Граф, в котором есть	Негамильтонов
		незамкнутая
	граф		граф
		гамильтонова цепь
		Рис. 6.24

Эйлеровы и гамильтоновы пути сходны по способу задания. Первые пути содержат все ребра, по одному разу каждое, вторые – все вершины, по одному разу каждую. Но, несмотря на внешнее сходство, задачи их поиска резко отличаются по степени трудности. Для решения вопроса о наличии эйлерова цикла в графе достаточно выяснить, все ли его вершины четны. Критерий существования гамильтонова цикла в произвольном графе еще не найден. Решение этой проблемы имеет практическую ценность, так как к игре Гамильтона близка известная задача о коммивояжере, который должен объехать несколько пунктов и вернуться обратно. Он обязан побывать в каждом пункте в точности по одному разу и заинтересован в том, чтобы затратить на поездку как можно меньше времени. А для этого требуется определить все варианты посещения городов и подсчитать в каждом случае затрату времени. По своей математической постановке игра Гамильтона близка к задаче о порядке переналадки станков, о подводке электроэнергии к рабочим местам и т.д.

Однако существует несколько достаточных условий наличия гамильтоновых циклов в графе.

Большинство известных теорем имеет вид «если граф G имеет достаточное число ребер, то граф G является гамильтоновым графом». Вероятно, самыми известными являются критерии Дирака и Оре.

169