Дискретная математика: графы и автоматы. Альпин Ю.А - 12 стр.

12                                      Глава 1. Неориентированные графы


нив её концы u и v новым ребром, получим эйлеров граф, в котором
все вершины имеют чётную степень. Учитывая, что при добавлении
ребра степени вершин u, v увеличились на 1, а степени других вершин
не изменились, получаем требуемое утверждение.
    Обратно, пусть связный граф содержит две вершины нечётной
степени. Соединив их новым ребром, получим граф, все вершины ко-
торого имеют чётную степень. С учётом теоремы 1 завершение дока-
зательства вполне очевидно. ¤
    Теперь от эйлеровых графов перейдем к понятию, внешне близ-
кому, но имевшему иную историю. Известный ирландский математик
У. Гамильтон в 1859 году опубликовал игру “Кругосветное путеше-
ствие”. Её суть в следующем. Каждой из двадцати вершин додекаэд-
ра приписано название одного из крупных городов мира. Требуется,
переходя по ребрам додекаэдра, посетить каждый город ровно один
раз и вернуться в исходный город. Разумеется, решение можно ис-
кать (попытайтесь найти его) на плоском изображении додекаэдра, а
именно на рис 5.:




                               Рис. 5


Общая постановка задачи такова: в связном графе требуется найти
простой цикл, содержащий все вершины графа. Такой цикл называ-
ется гамильтоновым, и сами графы, содержащие гамильтонов цикл,
называются гамильтоновыми.
    Несмотря на внешнее сходство, вопрос о том, как устроены га-
мильтоновы графы, в отличие от вопроса об эйлеровости, до сих пор
не имеет удовлетворительного решения. Однако известны достаточ-
ные условия гамильтоновости графа. Рассмотрим два из них.
   Теорема 2 (Дирак, 1952). Пусть дан граф с n вершинами
(n > 3). Для существования гамильтонова цикла достаточно, что-
бы степень каждой вершины была не меньше, чем n/2.
   Д о к а з а т е л ь с т в о. Предположим, что граф удовле-
творяет условиям теоремы, но не является гамильтоновым. Доба-
вим к нему новые вершины, соединяя каждую из них с каждой